Explore Our Questions

active hot week month

more tags

1

vote

0

answers

54

views

Complexity of enumerating over promise problems and circuits?

cc.complexity-theory complexity-classes quantum-computing promise-problems enumeration

modified Dec 1 at 13:33 user138901 45

11

votes

1

answer

221

views

Is DSPACE(n) = DSPACE(1.5n)?

cc.complexity-theory complexity-classes

modified Nov 23 at 10:24 domotorp 8,729

2

votes

1

answer

85

views

What is the best approximation and exact algorithm for vertex cover on cubic graphs?

cc.complexity-theory ds.algorithms np-hardness complexity-classes approximation-algorithms

answered Nov 22 at 20:32 Mohemnist 93

6

votes

1

answer

150

views

Does Max Planar 3-SAT admit a PTAS?

reference-request complexity-classes approximation-algorithms approximation-hardness planar-graphs

answered Nov 20 at 15:14 Gamow 3,824

3

votes

1

answer

228

views

Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

complexity-classes oracles nexp

modified Nov 11 at 8:01 Community♦ 1

1

vote

1

answer

233

views

$P=BPP$ without good PRGs?

cc.complexity-theory complexity-classes

answered Nov 6 at 21:47 Lance Fortnow 6,766

7

votes

1

answer

315

views

“Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes” — Worthy of arXiv.org?

complexity-classes np research-practice conditional-results halting-problem

answered Nov 2 at 21:36 Lance Fortnow 6,766

9

votes

1

answer

323

views

What is the complexity of this game?

cc.complexity-theory complexity-classes gt.game-theory

answered Oct 27 at 22:02 domotorp 8,729

7

votes

1

answer

150

views

Type theory and computational complexity

complexity-classes type-theory

answered Oct 25 at 10:30 gallais 536

13

votes

1

answer

344

views

Problems in NC not known to lie in NC2

complexity-classes dc.parallel-comp

modified Oct 20 at 1:50 Geoffroy Couteau 303

3

votes

2

answers

394

views

Is there a non-deterministic version of the complexity class PP?

cc.complexity-theory complexity-classes time-complexity

modified Oct 15 at 12:43 Emil Jeřábek 10.4k

8

votes

0

answers

109

views

Complexity of fractional SAT

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

asked Oct 14 at 1:21 Dmytro Taranovsky 1,422

5

votes

1

answer

175

views

Boolean circuits which correspond to L/poly

cc.complexity-theory reference-request complexity-classes circuit-complexity space-bounded

modified Oct 8 at 8:11 Jan Johannsen 3,864

0

votes

1

answer

315

views

What are the problems in EXPSPACE \ EXPTIME?

cc.complexity-theory complexity-classes polynomial-hierarchy

modified Oct 2 at 17:33 Jango 12

Browse More Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled