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

3

votes

1

answer

270

views

Complexity of type inference in the simply typed lambda calculus

complexity-classes typed-lambda-calculus

modified Dec 20 '21 at 17:59 Charlie Parker 262

23

votes

1

answer

2k

views

Tardos Function Counterexample to Blum's $P\neq NP$ Claim

cc.complexity-theory np-hardness complexity-classes

modified Dec 16 '21 at 10:01 Stasys 6,555

12

votes

2

answers

2k

views

Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?

cc.complexity-theory complexity-classes counting-complexity open-problem oracles

modified Dec 14 '21 at 16:40 Casey Lacey Hadley 1

9

votes

2

answers

2k

views

Reducing #SAT to #MONOTONE-2SAT

cc.complexity-theory ds.algorithms complexity-classes sat

modified Dec 12 '21 at 17:27 daniel pehoushek 95

6

votes

1

answer

197

views

Complexity of reachability in directed rooted forests

complexity-classes reductions tree directed-acyclic-graph complexity-theory

modified Nov 16 '21 at 13:00 Emil Jeřábek 14.1k

6

votes

1

answer

269

views

What is the complexity of HORN-2CNF entailment?

complexity-classes complexity-theory p-hardness

modified Nov 15 '21 at 13:52 Reijo Jaakkola 636

0

votes

0

answers

78

views

Query about P/poly and Polynomial Hierarchy Collapse to $\Sigma _{2}$

cc.complexity-theory complexity-classes

modified Oct 31 '21 at 10:58 TheoryQuest1 759

8

votes

1

answer

194

views

Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$

complexity-classes polynomial-hierarchy

answered Oct 25 '21 at 15:31 Emil Jeřábek 14.1k

15

votes

4

answers

3k

views

What would be the consequences of PH=PSPACE?

cc.complexity-theory complexity-classes conditional-results

modified Oct 8 '21 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 '21 at 12:23 user63167 3

3

votes

1

answer

157

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 '21 at 18:08 Teferi 31

1

vote

1

answer

136

views

Is QMA known to contain Co-NP?

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

answered Aug 27 '21 at 19:30 Lieuwe Vinkhuijzen 1,584

21

votes

4

answers

2k

views

Communication Complexity ...Classes?

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

modified Aug 25 '21 at 14:11 Alessandro Cosentino 3,860

7

votes

1

answer

195

views

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

complexity-classes computability

modified Aug 22 '21 at 12:30 Damiano Mazza 4,663

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled