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

5

votes

1

answer

130

views

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

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

modified 6 hours ago Community♦ 1

11

votes

0

answers

261

views

NP complete problem help

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

modified 2 days ago Mohsen Ghorbani 317

-3

votes

0

answers

36

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

0

votes

0

answers

33

views

Hardness of Approximation for Hypergraph Vertex Cover for Non-constant $k$

graph-algorithms np-hardness approximation-hardness complexity vertex-cover

asked Jan 13 at 2:30 Daniel Wu 1

-1

votes

2

answers

90

views

Knowing if there are two solutions to the subset sum problem

np-hardness counting-complexity reductions

answered Jan 8 at 15:59 Marzio De Biasi 21.7k

14

votes

0

answers

307

views

NP-hardness for one-dimensional facility location problem with entrance fee for each customer

ds.algorithms np-hardness cg.comp-geom polynomial-time

modified Jan 5 at 3:45 asdfqwer 99

0

votes

0

answers

78

views

Is the traveling salesman problem still NP-hard if all edges need to be covered as well?

cc.complexity-theory np-hardness tsp

asked Nov 23 '20 at 7:15 Sebastian Schmidt 1

0

votes

1

answer

55

views

How hard is deciding the existence of a polygonization with prescribed perimeter?

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

answered Nov 21 '20 at 18:17 Gamow 5,457

6

votes

1

answer

197

views

Why does Dinur's proof of the PCP theorem fail to work for unique games?

cc.complexity-theory np-hardness approximation-hardness pcp unique-games-conjecture

answered Nov 20 '20 at 22:10 Or Meir 4,910

7

votes

1

answer

301

views

Is solving the following system of boolean equations NP-hard?

np-hardness sat reductions

modified Nov 18 '20 at 16:40 Joshua Grochow 33.7k

9

votes

1

answer

200

views

Recent progress on the next-to-shortest-path problem for directed graphs?

np-hardness shortest-path

modified Nov 5 '20 at 14:00 Community♦ 1

1

vote

0

answers

143

views

What does it mean by the statement: “a problem is hard to approximate ”?

cc.complexity-theory np-hardness approximation-hardness terminology

modified Nov 2 '20 at 16:33 Inuyasha yagami 665

27

votes

5

answers

4k

views

Implications of unprovability of $P\neq NP$

cc.complexity-theory np-hardness big-picture proofs p-vs-np

modified Oct 22 '20 at 9:07 Jozef Mikušinec 3

1

vote

0

answers

97

views

reordering a DAG with the minimum changes

np-hardness directed-acyclic-graph topological-sorting

modified Oct 19 '20 at 3:31 2016310588 33

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled