Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Top Questions

5 votes
1 answer
120 views

Can you define recursive predicates in 2nd order intuitionistic logic?

2 votes
1 answer
93 views

Exposition of categorical models of type theory from type-theoretic perspective

1 vote
1 answer
115 views

Computational complexity and general relativity

4 votes
0 answers
86 views

Languages recognized Counter DFA

0 votes
1 answer
63 views

On the proof of $PP = P \iff \#P = FP$ in Arora & Barak (Lemma 17.7)

2 votes
0 answers
72 views

How to implement the next type inference algorithm?

1 vote
0 answers
51 views

Is there any inherently ambiguous indexed language?

1 vote
0 answers
49 views

Clarification sought re Li & Vitanyi's Proof of Godel Incompleteness in Formal System F

0 votes
0 answers
40 views

Polynomial GCD exact complexity in terms of degree and number of variables

2 votes
0 answers
35 views

Is there any context-free language that is inherently ambiguous as an indexed language

0 votes
0 answers
26 views

What is the tightest lower bound known for the integrality gap of the Gilmore–Gomory LP for Bin Packing?

-1 votes
0 answers
24 views

NCness of unique solution fixed dimension integer programming

0 votes
0 answers
20 views

Quantifying the cost of procedures

0 votes
1 answer
12 views

What is region construction in timed automata?

0 votes
0 answers
15 views

Can the witness for an NP-search problem be distinct from the item sought?

1 vote
0 answers
12 views

Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82


Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.