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

Explore our questions

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
1 answer
64 views

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

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$

16 votes
4 answers
3k views

What would be the consequences of PH=PSPACE?

0 votes
0 answers
118 views

Is orthogonal polygon with crossings count NP-complete?

3 votes
2 answers
215 views

Classes between PH and PSPACE

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?

1 vote
1 answer
139 views

Complexity of "discrete-time" SAT

2 votes
1 answer
295 views

Is any computational complexity question solved by injury priority method except Post problem?

Browse more Questions