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

1

vote

1

answer

33

views

Graph classes where giving a q-clique edge cover makes testing for q-colouring easy

cc.complexity-theory graph-theory time-complexity graph-colouring

answered yesterday Gamow 5,573

28

votes

0

answers

711

views

The complexity of checking whether two DAG have the same number of topological sorts

cc.complexity-theory complexity-classes counting-complexity open-problem partial-order

modified Jul 29 at 19:17 SamiD 2,257

4

votes

0

answers

101

views

An NP-hard Hidden Subgroup Problem

cc.complexity-theory np-hardness hiddensubgroupproblem

modified Jul 28 at 7:02 Shaull 4,805

-3

votes

0

answers

117

views

BPP version of a problem related to #P completeness

cc.complexity-theory counting-complexity randomness

asked Jul 21 at 1:58 PP vs BPP 1

57

votes

6

answers

3k

views

Theoretical explanations for practical success of SAT solvers?

cc.complexity-theory ds.algorithms sat big-picture heuristics

modified Jul 18 at 9:54 Claude Chaunier 101

2

votes

1

answer

118

views

Minimum cut with size bounds $k\leq |S| \leq |V|-k$

cc.complexity-theory max-flow-min-cut max-cut

modified Jul 16 at 16:18 Mohammad Al-Turkistany 20.3k

-3

votes

0

answers

64

views

Would this type of circular reference problem be in P or NP?

cc.complexity-theory np polynomial-time

asked Jul 11 at 9:22 Anders Gustafson 95

5

votes

0

answers

216

views

$\#$P hardness of computing weighted sum of degree $2$ polynomials

cc.complexity-theory counting-complexity approximation-hardness polynomials finite-fields

modified Jul 10 at 18:21 AngryLion 51

2

votes

0

answers

77

views

Result showing that DTIME[T] is strictly contained in random-access NTIME[T]

cc.complexity-theory nondeterminism

asked Jul 9 at 23:15 exfret 623

-1

votes

0

answers

31

views

Simple Reduction from ILP to slightly modified Integer Minimisation Problems?

cc.complexity-theory linear-programming reductions

asked Jul 9 at 10:35 Isaac 1

1

vote

0

answers

70

views

Parametrization of context-sensitive language in polynomial time

cc.complexity-theory ds.algorithms fl.formal-languages

modified Jul 6 at 9:03 deryll 11

6

votes

1

answer

270

views

Hardness of maximizing $x^TAy$ with $\{-1,1\}$ entries

cc.complexity-theory np-hardness co.combinatorics optimization

modified Jun 28 at 8:19 Rodrigo de Azevedo 227

2

votes

3

answers

110

views

Cost of Numerically Solving a System of P polynomials, each of V variables, and degree D to a Specific Accuracy

cc.complexity-theory polynomials na.numerical-analysis

modified Jun 27 at 13:35 Peter Shor 23.2k

-2

votes

1

answer

49

views

Is time-slot matchmaking NP-hard?

cc.complexity-theory np-hardness scheduling

answered Jun 23 at 18:04 user1543037 116

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled