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

10

votes

3

answers

730

views

Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

cc.complexity-theory ho.history-overview exp-time-algorithms

answered 9 hours ago Joshua Grochow 33.7k

36

votes

5

answers

2k

views

Integer multiplication when one integer is fixed

cc.complexity-theory ds.algorithms circuit-complexity algebraic-complexity arithmetic-circuits

modified 21 hours ago 1.. 11.3k

4

votes

0

answers

222

views

NP Intermediate problems over Reals

cc.complexity-theory computing-over-reals

modified 2 days ago user3483902 923

2

votes

0

answers

38

views

Does the awards budget cut problem support a sub $O(n\log n)$ time solution?

cc.complexity-theory time-complexity greedy-algorithms

asked Jan 23 at 17:23 frogeyedpeas 299

1

vote

0

answers

27

views

Complexity Lower Bounds for 3D Sparse Gaussian Elimination

cc.complexity-theory lower-bounds linear-algebra

asked Jan 22 at 23:29 eepperly16 111

11

votes

0

answers

296

views

NP complete problem help

cc.complexity-theory np-hardness complexity-classes cg.comp-geom

modified Jan 18 at 18:34 Mohsen Ghorbani 317

8

votes

1

answer

842

views

canonical complete problems for $\Delta^P_n$

cc.complexity-theory alternating-hierarchy polynomial-hierarchy

modified Jan 18 at 9:58 MikeChav 3

-3

votes

0

answers

68

views

Complexity implications of impossibility of direct Diffie-Hellman compromise

cc.complexity-theory complexity-classes

modified Jan 17 at 9:53 1.. 11.3k

1

vote

0

answers

59

views

Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains

cc.complexity-theory lo.logic terminology descriptive-complexity finite-model-theory

asked Jan 14 at 19:58 Erfan Khaniki 272

-3

votes

0

answers

39

views

A variant of the Generalized Assignment problem

cc.complexity-theory np-hardness np-complete matching bipartite-graphs

modified Jan 14 at 0:16 MarsPlus 137

1

vote

0

answers

199

views

Is there a known lower-bound on what the exponent could be, even if it turned out that P=NP?

cc.complexity-theory time-complexity lower-bounds

modified Jan 7 at 12:49 Lieuwe Vinkhuijzen 1,532

14

votes

1

answer

550

views

Minimizing residual finite state automata

cc.complexity-theory ds.algorithms automata-theory lg.learning minimization

modified Jan 3 at 15:44 Hermann Gruber 5,039

2

votes

0

answers

42

views

Computational complexity problem book with solution recommendation?

cc.complexity-theory

asked Jan 2 at 1:57 user852687 41

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled