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

1

vote

0

answers

50

views

+100

Fastest Known Algorithm for $k$-Dimensional Matching and $k$-Exact Cover

cc.complexity-theory ds.algorithms graph-algorithms parameterized-complexity exp-time-algorithms

modified 8 hours ago Naysh 312

0

votes

1

answer

82

views

Derandomizing arbitrary width read-many and ordered branching programs?

cc.complexity-theory randomness derandomization space-bounded pseudorandom-generators

modified 2 days ago Mr. 11.8k

5

votes

0

answers

64

views

Fine-Grained Hardness for Undirected Hamiltonicity

cc.complexity-theory ds.algorithms graph-algorithms hamiltonian-paths fine-grained

asked Oct 12 at 19:04 Naysh 312

6

votes

1

answer

247

views

Cook inspiration for NP completeness

cc.complexity-theory np-complete cook-levin

modified Oct 12 at 7:41 Rodrigo 717

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

70

votes

8

answers

9k

views

Are runtime bounds in P decidable? (answer: no)

cc.complexity-theory approximation-hardness

modified Oct 1 at 5:18 John Landon Miller 1

1

vote

0

answers

147

views

Is polynomial-time the same in all classical computational models?

cc.complexity-theory polynomial-time

modified Sep 28 at 13:52 Dylan Thurston 119

-1

votes

0

answers

68

views

How exactly does derandomization of BPP imply lower bounds on NEXP

cc.complexity-theory derandomization

modified Sep 25 at 12:35 Yonatan N 1,616

0

votes

1

answer

92

views

Diophantine equations with bounds on variables

cc.complexity-theory reference-request

modified Sep 24 at 17:11 GMB 2,073

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

-1

votes

1

answer

83

views

Is finding the shortest consistent term to fill a missing line in a truth table still NP-hard?

cc.complexity-theory np-hardness circuit-complexity minimization

answered Sep 22 at 16:15 Neal Young 7,397

0

votes

0

answers

52

views

EXPSPACE-complete problems involving numbers

cc.complexity-theory reference-request

asked Sep 22 at 15:26 gigabytes 1,042

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled