We’re rewarding the question askers & reputations are being recalculated! Read more.

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

more tags

Active 1 Bountied Hot Week Month

0

votes

0

answers

11

views

Does stronger non-$\mathsf{SETH}$ statement imply $\mathsf{P=NP}$?

cc.complexity-theory complexity-classes circuit-complexity lower-bounds exp-time-algorithms

modified 1 hour ago T.... 10.7k

3

votes

1

answer

247

views

Complexity classes not closed under intersection and union

cc.complexity-theory

modified Nov 12 at 18:40 Hermann Gruber 4,210

30

votes

3

answers

1k

views

Is this variation of TQBF still PSPACE-complete?

cc.complexity-theory sat gt.game-theory pspace

modified Nov 11 at 19:46 Lutfar Rahman Milu 101

13

votes

1

answer

556

views

Consequences of sub-exponential proofs/algorithms for SAT

cc.complexity-theory sat proof-complexity

modified Nov 10 at 19:19 Hermann Gruber 4,210

4

votes

1

answer

271

views

Which complexity class does this problem belong to?

cc.complexity-theory complexity-classes

modified Nov 9 at 21:56 Neal Young 4,583

-1

votes

0

answers

31

views

Understanding Computability of a Function

cc.complexity-theory computability computable-analysis

asked Nov 8 at 10:25 aomerk 107

5

votes

0

answers

56

views

What are some examples of algorithmic applications of noncommutative rational identity testing?

cc.complexity-theory ds.algorithms graph-algorithms polynomials algebraic-complexity

asked Nov 7 at 18:16 Naysh 233

4

votes

1

answer

77

views

Is the isomorphism problem between posets represented by DAGs GI-complete?

cc.complexity-theory graph-isomorphism directed-acyclic-graph partial-order

modified Nov 7 at 6:47 Laakeri 390

3

votes

1

answer

167

views

Qubit gates in google supremacy

cc.complexity-theory quantum-computing big-picture dc.parallel-comp sample-complexity

modified Nov 6 at 13:50 Peter Shor 22.4k

21

votes

6

answers

2k

views

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

cc.complexity-theory complexity-classes np-complete polynomial-time np-intermediate

answered Nov 5 at 13:38 Shaull 3,767

5

votes

1

answer

171

views

Document references describing weaknesses for cutting planes and algebraic proof system?

cc.complexity-theory cg.comp-geom proofs proof-complexity

modified Nov 4 at 7:50 notautogenerated 166

-2

votes

0

answers

17

views

Vertex k-coloring on Weighted 3-regular Graph allowing Conflict Edges

cc.complexity-theory np-complete graph-colouring

asked Nov 1 at 22:30 PeaBrane 97

10

votes

0

answers

291

views

Is unary $\Pi_2$-SUBSETSUM coNP-complete?

cc.complexity-theory np-hardness complexity-classes lo.logic

modified Oct 31 at 13:14 Alexey Milovanov 1,457

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled