User tparker

6 votes

1 answer

273 views

Are any "standard" complexity classes uncountably infinite?

asked Dec 9, 2023 at 19:37

1 vote

0 answers

86 views

At what precision are GPT's parameters stored?

asked Jul 1, 2023 at 2:00

6 votes

1 answer

100 views

Do relativized relations between complexity classes tell us anything about the nonrelativized relation?

asked Aug 10, 2019 at 1:20

0 votes

2 answers

162 views

Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$?

asked Apr 23, 2021 at 21:50

6 votes

1 answer

322 views

Have any natural complexity classes been proven not to be closed under complement?

asked Jun 13, 2018 at 20:29

4 votes

1 answer

136 views

Is there a complexity class QPP?

asked Mar 28, 2020 at 0:12

2 votes

2 answers

119 views

Does the word "efficient" usually refer to polynomial time or polylogarithmic time?

asked Mar 27, 2020 at 3:24

1 vote

0 answers

55 views

Which is harder, an NP-complete problem or the Raz-Tal oracle problem?

asked Aug 10, 2019 at 18:10

5 votes

4 answers

776 views

Are there deterministic and/or non-interactive zero-knowledge proofs?

asked Sep 15, 2018 at 16:46

1 vote

2 answers

230 views

Defining decision-problem complexity classes by counting branches of a polynomial-time NTM

asked Jun 14, 2018 at 1:22

1 vote

1 answer

518 views

Is the existence of an oracle such that $P^O = NP^O$ nontrivial? [duplicate]

asked Jun 6, 2018 at 21:12

3 votes

1 answer

106 views

Specific example of a problem that shows why NP isn't low for itself

asked Jun 6, 2018 at 20:28

2 votes

0 answers

67 views

Are there problems for which quantum computers don't even give a (nontrivial) polynomial speedup?

asked Mar 26, 2018 at 18:41

4 votes

2 answers

188 views

Should we always think of problems higher in the polynomial hierarchy as harder than problems lower in the hierarchy?

asked Mar 15, 2018 at 22:16

1 vote

0 answers

77 views

What do we know about the reciprocal busy beaver series? [closed]

asked Oct 12, 2017 at 0:57

3 votes

1 answer

155 views

Relationship between PP and PH

asked Aug 22, 2016 at 4:43

4 votes

2 answers

541 views

Are there any useful deterministic quantum algorithms for decision problems?

asked May 12, 2016 at 0:42

8 votes

1 answer

1k views

Known problems in BQP \ NP?

asked May 9, 2016 at 4:59

3 votes

0 answers

92 views

Are there theoretical reasons for believing that P=NP is harder than other complexity problems? [duplicate]

asked Apr 23, 2016 at 0:58

17 votes

1 answer

8k views

Why is NP in EXPTIME?

asked Apr 22, 2016 at 1:36

Stack Exchange Network

20 Questions

Are any "standard" complexity classes uncountably infinite?

At what precision are GPT's parameters stored?

Do relativized relations between complexity classes tell us anything about the nonrelativized relation?

Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$?

Have any natural complexity classes been proven not to be closed under complement?

Is there a complexity class QPP?

Does the word "efficient" usually refer to polynomial time or polylogarithmic time?

Which is harder, an NP-complete problem or the Raz-Tal oracle problem?

Are there deterministic and/or non-interactive zero-knowledge proofs?

Defining decision-problem complexity classes by counting branches of a polynomial-time NTM

Is the existence of an oracle such that $P^O = NP^O$ nontrivial? [duplicate]

Specific example of a problem that shows why NP isn't low for itself

Are there problems for which quantum computers don't even give a (nontrivial) polynomial speedup?

Should we always think of problems higher in the polynomial hierarchy as harder than problems lower in the hierarchy?

What do we know about the reciprocal busy beaver series? [closed]

Relationship between PP and PH

Are there any useful deterministic quantum algorithms for decision problems?

Known problems in BQP \ NP?

Are there theoretical reasons for believing that P=NP is harder than other complexity problems? [duplicate]

Why is NP in EXPTIME?