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

38

votes

3

answers

2k

views

Is there a backup/replacement for the Complexity Zoo?

cc.complexity-theory reference-request soft-question

modified 15 hours ago Emil Jeřábek 11.4k

4

votes

1

answer

191

views

Witness verifiable quantum advantage

cc.complexity-theory quantum-computing ce.computational-finance

modified 20 hours ago Mark S 712

1

vote

2

answers

37

views

Disjoint subsets problem complexity

cc.complexity-theory np-complete

answered 23 hours ago Stephane Bersier 191

0

votes

1

answer

90

views

+100

Diagonalization arguments for QMA type proof systems

cc.complexity-theory reference-request complexity-classes quantum-computing

modified May 23 at 8:04 AngryLion 17

5

votes

1

answer

117

views

Topological sorting of a DAG where special vertices have to come in even groups

cc.complexity-theory graph-algorithms np-hardness topological-sorting

modified May 20 at 17:19 Gara Pruesse 252

0

votes

0

answers

26

views

Encrypt an explicit circuit

cc.complexity-theory cryptography

modified May 16 at 7:52 Lwins 365

11

votes

1

answer

749

views

Enumerating topological sorts of a vertex-labeled DAG

cc.complexity-theory sorting directed-acyclic-graph partial-order topological-sorting

modified May 15 at 15:50 a3nm 6,664

13

votes

2

answers

3k

views

Lexicographically minimal topological sort of a labeled DAG

cc.complexity-theory np-hardness directed-acyclic-graph order-theory topological-sorting

modified May 15 at 15:50 a3nm 6,664

4

votes

0

answers

180

views

NP-completeness of a specific topological sorting problem

cc.complexity-theory np-hardness directed-acyclic-graph partial-order topological-sorting

modified May 15 at 15:46 a3nm 6,664

20

votes

2

answers

1k

views

Is feedback vertex set problem is solvable in polynomial time for 3-degree bounded graphs?

cc.complexity-theory graph-theory graph-algorithms np-hardness bounded-degree

modified May 15 at 15:41 Yixin Cao 2,215

11

votes

2

answers

224

views

Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

cc.complexity-theory complexity-classes randomness

modified May 5 at 1:00 Ryan Williams 24.8k

7

votes

1

answer

143

views

Complexity class of efficient streaming algorithms

cc.complexity-theory reference-request complexity-classes space-bounded streaming-algorithms

modified May 3 at 20:36 Hermann Gruber 4,464

1

vote

0

answers

33

views

Efficient algorithm for finding segregators in a directed acyclic graph

cc.complexity-theory graph-algorithms approximation-algorithms np-complete

asked Apr 26 at 17:57 exfret 603

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled