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

Ask Question

more tags

Active 1 Bountied Hot Week Month

2 votes

1 answer

120 views

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

cc.complexity-theory np-hardness complexity-classes sat

Laakeri

1,398

answered May 16 at 19:04

0 votes

0 answers

63 views

Simplify or bound using Big-O notation

cc.complexity-theory complexity-classes time-complexity asymptotics notation

wanderer

89

asked May 14 at 23:36

0 votes

0 answers

32 views

Is there an MMSNP formula for 3-colouring?

graph-theory complexity-classes

Cyriac Antony

1,603

modified May 9 at 4:07

2 votes

0 answers

75 views

Nondeterministic polynomial time languages with linearly bounded certificates

cc.complexity-theory complexity-classes fl.formal-languages automata-theory time-complexity

Alberto

91

asked May 6 at 22:29

0 votes

0 answers

73 views

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

cc.complexity-theory complexity-classes csp

Cyriac Antony

1,603

modified May 5 at 4:25

23 votes

6 answers

3k views

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

cc.complexity-theory complexity-classes p-vs-np

Martin

109

modified Apr 25 at 7:45

6 votes

1 answer

150 views

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

cc.complexity-theory complexity-classes definitions existential-theory-of-the-reals

user66277

116

modified Apr 12 at 16:20

0 votes

0 answers

77 views

What are the capabilities of current Boolean Satisfiability Solvers?

np-hardness complexity-classes p-vs-np ai.artificial-intel boolean-formulas

Nat Kar

1

asked Apr 8 at 16:20

3 votes

0 answers

65 views

Complete problems for fast-growing hierarchy classes

cc.complexity-theory complexity-classes big-picture

Ben Tom

39

asked Mar 19 at 17:37

5 votes

1 answer

320 views

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

complexity-classes promise-problems probabilistic-complexity

Turbo

12.5k

modified Mar 15 at 15:27

0 votes

0 answers

69 views

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

complexity-classes sat reductions approximation-hardness

Maria

11

asked Feb 9 at 13:58

5 votes

0 answers

283 views

Quantum computer versus Random 3-SAT?

np-hardness complexity-classes quantum-computing average-case-complexity

user1271772

540

modified Jan 27 at 8:34

3 votes

1 answer

307 views

Complexity of type inference in the simply typed lambda calculus

complexity-classes typed-lambda-calculus

Charlie Parker

262

modified Dec 20, 2021 at 17:59

Browse more Questions