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

Ask Question

more tags

Active 1 Bountied Hot Week Month

15

votes

4

answers

2k

views

What would be the consequences of PH=PSPACE?

cc.complexity-theory complexity-classes conditional-results

modified Oct 8 at 6:19 user63167 3

31

votes

4

answers

4k

views

Consequences of NP=PSPACE

cc.complexity-theory complexity-classes conditional-results

modified Oct 7 at 12:23 user63167 3

3

votes

1

answer

153

views

complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)

cc.complexity-theory complexity-classes linear-algebra reductions

modified Sep 22 at 18:08 Teferi 31

-2

votes

0

answers

100

views

A query regarding relation b/w complexity classes $NP$ and $BQP$ in case of collapse of $PH$?

cc.complexity-theory complexity-classes quantum-computing

modified Sep 20 at 8:43 Mr. 11.8k

1

vote

1

answer

135

views

Is QMA known to contain Co-NP?

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

answered Aug 27 at 19:30 Lieuwe Vinkhuijzen 1,572

21

votes

4

answers

2k

views

Communication Complexity ...Classes?

cc.complexity-theory complexity-classes big-picture communication-complexity

modified Aug 25 at 14:11 Alessandro Cosentino 3,850

7

votes

1

answer

179

views

What is the complexity class of higher-order primitive recursion?

complexity-classes computability

modified Aug 22 at 12:30 Damiano Mazza 4,613

0

votes

1

answer

157

views

Lexicographic Boolean satisfiability

np-hardness complexity-classes sat np-complete

modified Aug 14 at 8:06 Reijo Jaakkola 460

29

votes

0

answers

725

views

The complexity of checking whether two DAG have the same number of topological sorts

cc.complexity-theory complexity-classes counting-complexity open-problem partial-order

modified Jul 29 at 19:17 SamiD 2,257

15

votes

2

answers

389

views

NLOGTIME versus $\exists$DLOGTIME

complexity-classes nondeterminism

answered Jun 30 at 16:16 Dmytro Taranovsky 2,202

29

votes

2

answers

1k

views

What are the consequences of Parity-L = P?

cc.complexity-theory complexity-classes conditional-results

modified Jun 13 at 11:37 Frédéric Grosshans 785

3

votes

0

answers

103

views

Complete problems for $(NP\cap CoNP)/poly$ class and universal representations

cc.complexity-theory complexity-classes circuit-complexity

asked Jun 8 at 12:33 Erfan Khaniki 302

4

votes

0

answers

189

views

What does width $4$ permutation branching program correspond to?

cc.complexity-theory complexity-classes circuit-complexity big-picture permutations

asked Jun 3 at 20:45 Mr. 11.8k

2

votes

0

answers

195

views

Simultaneous evidence for $L\neq NL$ and $P\neq NP$

cc.complexity-theory complexity-classes big-picture polynomial-time logspace

asked Jun 3 at 18:40 Mr. 11.8k

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled