Theoretical Computer Science Stack Exchange

3 votes

0 answers

102 views

Is it known that $\mathsf{E} \subset \mathsf{NP} \subset \mathsf{SIZE}[n^k]$ is false?

Stefan G.

271

modified Aug 30 at 3:39

1 vote

1 answer

74 views

Norm in the definition of sampling computational complexity class SampP

D.W.

12.3k

modified Aug 21 at 6:46

5 votes

0 answers

144 views

Is this class between BPP and PP?

Doriano Brogioli

83

asked Aug 12 at 15:25

1 vote

1 answer

129 views

Graph canonization vs. NP

Arnaud Casteigts

378

modified Aug 10 at 18:21

0 votes

0 answers

37 views

Integration of analytic function

D.W.

12.3k

modified Jul 23 at 21:04

5 votes

1 answer

262 views

Complexity of finding graph automorphism group vs. canonization

Joshua Grochow

37.8k

answered Jul 23 at 15:34

18 votes

4 answers

4k views

What would be the consequences of $\mathsf{PH=PSPACE}$?

Misha Brukman

107

modified Jul 21 at 23:53

1 vote

2 answers

153 views

Use of transitive closure in proof of NC hierarchy collapse

Eric Allender

2,271

answered Jul 9 at 19:24

0 votes

1 answer

120 views

Are there NPO (NP Optimization) problems that would require more than polynomial time even on a non-deterministic machine?

NaturalLogZ

442

modified Jun 20 at 16:58

2 votes

1 answer

108 views

On the power of QMA(2)

Hermann Gruber

6,665

modified Jun 20 at 9:46

1 vote

1 answer

139 views

Where does a problem lie which is NP-hard but not QMA-hard?

Lieuwe Vinkhuijzen

2,159

answered May 31 at 19:44

0 votes

1 answer

126 views

Is the protocol perfect zero knowledge?

lamontap

1,010

answered May 30 at 19:51

15 votes

3 answers

877 views

Is Parity-P contained in PP?

Tayfun Pay

2,628

answered May 30 at 14:27

7 votes

2 answers

401 views

Problems where "maximal" is hard, but "maximum" is easy?

Neal Young

10.9k

modified May 14 at 10:05

Stack Exchange Network

Explore our questions

Is it known that $\mathsf{E} \subset \mathsf{NP} \subset \mathsf{SIZE}[n^k]$ is false?

Norm in the definition of sampling computational complexity class SampP

Is this class between BPP and PP?

Graph canonization vs. NP

Integration of analytic function

Complexity of finding graph automorphism group vs. canonization

What would be the consequences of $\mathsf{PH=PSPACE}$?

Use of transitive closure in proof of NC hierarchy collapse

Are there NPO (NP Optimization) problems that would require more than polynomial time even on a non-deterministic machine?

On the power of QMA(2)

Where does a problem lie which is NP-hard but not QMA-hard?

Is the protocol perfect zero knowledge?

Is Parity-P contained in PP?

Problems where "maximal" is hard, but "maximum" is easy?

Hot Network Questions