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

2 votes
1 answer
120 views

Complexity of the Complete (3,2) SAT problem?

0 votes
0 answers
63 views

Simplify or bound using Big-O notation

0 votes
0 answers
32 views

Is there an MMSNP formula for 3-colouring?

2 votes
0 answers
75 views

Nondeterministic polynomial time languages with linearly bounded certificates

0 votes
0 answers
73 views

Does NP-completeness in one graph class imply not NP-intermediate in another graph class?

23 votes
6 answers
3k views

Statements that imply $\mathbf{P}\neq \mathbf{NP}$

6 votes
1 answer
150 views

Reductions weaker than polynomial-time for $\exists \mathbb{R}$

0 votes
0 answers
77 views

What are the capabilities of current Boolean Satisfiability Solvers?

3 votes
0 answers
65 views

Complete problems for fast-growing hierarchy classes

5 votes
1 answer
320 views

Where is $MA$ more relevant than $\exists BPP$?

0 votes
0 answers
69 views

APX-hardness of Max-3-SAT(5)

5 votes
0 answers
283 views

Quantum computer versus Random 3-SAT?

3 votes
1 answer
307 views

Complexity of type inference in the simply typed lambda calculus

Browse more Questions