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

0 votes
0 answers
15 views

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

0 votes
1 answer
12 views

What is region construction in timed automata?

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

0 votes
0 answers
10 views

Dual of cut of embedded graph disconnects surface

4 votes
1 answer
106 views
+50

Natural hard communication problems with both nondeterministic and co-nondeterministic complexity of $\sqrt{n}$?

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?

5 votes
1 answer
120 views

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

4 votes
0 answers
86 views

Languages recognized Counter DFA

27 votes
6 answers
3k views

Are there NP-complete problems with polynomial expected time solutions?

0 votes
0 answers
40 views

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

-1 votes
0 answers
24 views

NCness of unique solution fixed dimension integer programming

4 votes
0 answers
117 views

Problems which will be in $NC$ if fixed dimension Linear Integer Programming in $NC$

0 votes
0 answers
20 views

Quantifying the cost of procedures

2 votes
1 answer
93 views

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

2 votes
0 answers
35 views

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

1 vote
0 answers
51 views

Is there any inherently ambiguous 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?

-2 votes
0 answers
106 views

Is this theorem correct? [closed]

1 vote
1 answer
115 views

Computational complexity and general relativity

1 vote
0 answers
49 views

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

11 votes
7 answers
3k views

How does Theoretical Computer Science relate to security?

16 votes
4 answers
3k views

What would be the consequences of PH=PSPACE?

16 votes
2 answers
2k views

How is Lambda Calculus a specific type of Term Writing system?

2 votes
0 answers
54 views

Efficient algorithm for finding closest point for rotated and scaled $\mathbb{Z}_n$ lattice

0 votes
0 answers
118 views

Is orthogonal polygon with crossings count NP-complete?

1 vote
0 answers
60 views

Generalizing Fano's inequality

1 vote
1 answer
191 views

Is it proved that error rate of quantum computation is bounded by constant rather than a function dependent on time and environment by quantum theory

3 votes
2 answers
215 views

Classes between PH and PSPACE

-1 votes
0 answers
69 views

Theorems about integrality gap for set cover linear programs

0 votes
1 answer
63 views

Number of stable matchings

10 votes
2 answers
382 views

Is there a definitive reference for Turing machines with multiple oracle tapes?

229 votes
60 answers
95k views

Major unsolved problems in theoretical computer science?

4 votes
2 answers
343 views

Random self reducibility and NP

4 votes
0 answers
80 views

Time Complexity of Pairwise Graph Connectedness

10 votes
3 answers
543 views

Is uniform convergence faster for low-entropy distributions?

0 votes
1 answer
64 views

Factoring random selfreducibility analogy from discrete logarithm

12 votes
2 answers
361 views

On $n$ dimensional manifolds and lattices

0 votes
0 answers
60 views

What is the right notion of reduction for 2EXPTIME?

0 votes
1 answer
37 views

Complexity and Applications of performing $N$ divisions with "similar" results?

2 votes
0 answers
86 views

How far is the distance between Mahlo Universe and Mahlo Cardinal?

-1 votes
1 answer
46 views

Flow of value lower bounded by $X$

16 votes
0 answers
410 views

Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?

0 votes
0 answers
66 views

Interactive proofs with computation bounded Merlin

1 vote
2 answers
66 views

Examples of promise search problems that are easier than their non-promise variants?

0 votes
1 answer
51 views

Running time of SAT and other EXPTIME algorithms [closed]

-1 votes
0 answers
47 views

What would be a canonical programming language?


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