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

16

votes

10

answers

1k

views

What are some problems where we know we have an optimal algorithm?

cc.complexity-theory ds.algorithms complexity-classes

modified 2 hours ago Glorfindel 209

9

votes

2

answers

479

views

Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

cc.complexity-theory reference-request automata-theory dfa enumeration

modified 2 hours ago a3nm 7,005

-1

votes

0

answers

104

views

What progress has been towards $ZPL=L$?

cc.complexity-theory randomized-algorithms

modified 10 hours ago 1.. 11.7k

0

votes

0

answers

104

views

An $O(n^2\log^c{n})$ algorithm for matrix multiplication in this paper?

cc.complexity-theory matrix-product

asked yesterday Mengfan Ma 431

10

votes

1

answer

242

views

Complexity of unique coloring of graphs

cc.complexity-theory graph-theory graph-algorithms complexity-classes

answered yesterday Austin Buchanan 1,616

20

votes

4

answers

1k

views

Complexity of finding a second solution given a correct solution to an NP-complete problem

cc.complexity-theory reference-request np-hardness unique-solution

modified Apr 18 at 14:59 Mohammad Al-Turkistany 20.3k

3

votes

1

answer

206

views

Proof and computational complexity

cc.complexity-theory reference-request lo.logic computability

modified Apr 17 at 21:07 Denis 6,890

19

votes

1

answer

1k

views

Consequences of UP equals NP

cc.complexity-theory complexity-classes conditional-results unique-solution

modified Apr 14 at 21:05 User2021 81

4

votes

1

answer

189

views

Complexity of relaxed edge colouring

cc.complexity-theory graph-theory np-hardness graph-colouring

modified Apr 13 at 13:50 Cyriac Antony 1,251

0

votes

0

answers

70

views

Cook-Levin for parallel classes

cc.complexity-theory reference-request dc.parallel-comp ac0 cook-levin

modified Apr 12 at 8:17 User2021 81

1

vote

1

answer

137

views

KRW Conjecture: separation of NC^1 and P

cc.complexity-theory complexity-classes boolean-functions boolean-circuits

modified Apr 11 at 21:15 StanleyIpkiss 13

0

votes

1

answer

66

views

Given a partition and an element, find the subset that includes this element

cc.complexity-theory ds.algorithms reference-request set-theory

answered Apr 6 at 3:21 D.W. 9,716

12

votes

2

answers

860

views

Enumerating topological sorts of a vertex-labeled DAG

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

modified Apr 2 at 19:59 Gregory Morse 9

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled