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

2

votes

2

answers

97

views

Status of certain problems in knot theory

reference-request np-hardness cg.comp-geom topology

answered Oct 12 at 12:46 Arnaud 790

0

votes

0

answers

27

views

Bounded-Frequency Minimum Set Cover Problem

graph-theory np-hardness np-complete set-cover upper-bounds

asked Oct 12 at 5:06 Garrett 101

1

vote

1

answer

51

views

Maximize the absolute value of connected nodes after $k$ modifications

np-hardness optimization

modified Oct 8 at 18:46 Neal Young 7,397

2

votes

1

answer

72

views

Can this special case of Node Weighted Steiner Tree be solved in polynomial time?

graph-theory graph-algorithms np-hardness approximation-algorithms

modified Oct 7 at 2:24 Karagounis Z 473

0

votes

0

answers

108

views

Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?

np-hardness sat reductions boolean-formulas

asked Oct 1 at 21:23 ferris 1

1

vote

0

answers

120

views

For what parameters is minimum distance hard?

np-hardness approximation-hardness np-complete coding-theory

modified Sep 30 at 1:09 Root 305

-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

6

votes

1

answer

192

views

Uniformly sampling or counting connected graph partitions with any number of blocks

graph-algorithms np-hardness counting-complexity randomized-algorithms partition-problem

modified Sep 18 at 0:08 CommunityBot 1

134

votes

29

answers

22k

views

Problems Between P and NPC

cc.complexity-theory np-hardness big-list np-intermediate

modified Sep 17 at 22:49 Clement C. 4,083

1

vote

1

answer

135

views

Is QMA known to contain Co-NP?

cc.complexity-theory np-hardness complexity-classes complexity qma

answered Aug 27 at 19:30 Lieuwe Vinkhuijzen 1,572

0

votes

1

answer

157

views

Lexicographic Boolean satisfiability

np-hardness complexity-classes sat np-complete

modified Aug 14 at 8:06 Reijo Jaakkola 460

0

votes

0

answers

49

views

Is p-dimensional matching with (p−1)n edges NP-hard? What about 3n edges?

np-hardness matching

asked Jul 29 at 14:59 Ernie Vigelan 1

4

votes

0

answers

122

views

An NP-hard Hidden Subgroup Problem

cc.complexity-theory np-hardness hiddensubgroupproblem

modified Jul 28 at 7:02 Shaull 4,967

3

votes

1

answer

188

views

$\rho OPT + k$ approximation for bin packing (Unpublished result of David P. Williamson)

np-hardness approximation-algorithms packing extremal-combinatorics chernoff-bound

modified Jul 22 at 1:00 CommunityBot 1

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled