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 Hot Week Month

2

votes

1

answer

100

views

Consequences/existence of problems without any “optimal” algorithm

ds.algorithms complexity-classes time-complexity

answered Aug 21 at 3:43 Will Angley 146

-2

votes

0

answers

68

views

Is BQP upper bounded by the class of problems computable by an exponential number of GPUs?

cc.complexity-theory complexity-classes quantum-computing time-complexity

asked Aug 10 at 12:34 Jsevillamol 97

2

votes

1

answer

143

views

Possibility of hierarchy with $UP$ class?

cc.complexity-theory reference-request complexity-classes oracles polynomial-hierarchy

modified Aug 8 at 20:01 Community♦ 1

4

votes

0

answers

140

views

A game on several graphs

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

asked Aug 8 at 19:14 Alexey Milovanov 593

9

votes

2

answers

299

views

Consequences of OWFs for Complexity

cc.complexity-theory reference-request complexity-classes cr.crypto-security one-way-function

answered Aug 8 at 16:27 user17164 341

-1

votes

0

answers

137

views

Complexity and completeness of certain problems resembling $BPP$ and $PP$?

complexity-classes sat counting-complexity randomized-algorithms promise-problems

modified Jul 31 at 9:38 T.... 5,213

6

votes

1

answer

93

views

Separation of AM and SZK

cc.complexity-theory complexity-classes interactive-proofs

answered Jul 14 at 4:16 Robin Kothari 11k

0

votes

1

answer

158

views

Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?

cc.complexity-theory complexity-classes counting-complexity

modified Jun 23 at 13:44 Lieuwe Vinkhuijzen 1,010

2

votes

0

answers

58

views

$XP_{\text{uniform}}=FPT$ and update to $EPTAS$ section in complexity zoo?

cc.complexity-theory reference-request complexity-classes approximation-algorithms parameterized-complexity

modified May 22 at 15:57 Martin Berger 9,470

2

votes

0

answers

133

views

Is the following problem in $coNP$?

cc.complexity-theory complexity-classes np convex-geometry determinant

modified May 21 at 17:39 T.... 5,213

17

votes

4

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

modified Apr 26 at 7:46 Jan Johannsen 3,974

7

votes

1

answer

210

views

Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?

complexity-classes time-complexity p-vs-np

answered Apr 20 at 20:35 Ryan Williams 23.2k

3

votes

1

answer

166

views

String theory based computations

complexity-classes quantum-computing

answered Apr 12 at 11:19 Peter Shor 21.5k

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled