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

4

votes

1

answer

94

views

Neighborly properties in a bipartite graph

graph-theory graph-algorithms np-hardness

modified yesterday Laakeri 896

8

votes

1

answer

130

views

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

np-hardness shortest-path

modified Jul 8 at 13:03 Community♦ 1

-1

votes

0

answers

30

views

Reduce a decision problem to an optimization problem

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

asked Jul 6 at 12:46 BrianH 1

0

votes

1

answer

71

views

Minimizing the gaps with incremental capacity

ds.algorithms np-hardness dynamic-programming

modified Jul 6 at 2:56 Neal Young 6,025

-3

votes

0

answers

69

views

Is mathematical proof itself NP-hard?

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

asked Jun 30 at 16:33 Atsina 103

1

vote

1

answer

85

views

On the paper “Quantum Computing Hamiltonian cycles”

graph-theory np-hardness quantum-computing hamiltonian-paths

answered Jun 23 at 16:45 joro 1,817

9

votes

2

answers

3k

views

What are good approximation algorithms for the subset sum problem so far?

ds.algorithms np-hardness approximation-algorithms approximation-hardness subset-sum

answered Jun 16 at 18:18 dohmatob 151

39

votes

3

answers

3k

views

Is the integer factorization problem harder than RSA factorization: $n = pq$?

cc.complexity-theory reference-request np-hardness cr.crypto-security factoring

modified Jun 16 at 8:39 Community♦ 1

7

votes

2

answers

585

views

Is this vertex ordering optimization NP-Hard?

graph-theory np-hardness permutations

modified Jun 13 at 19:26 Mohammad Al-Turkistany 19.8k

5

votes

2

answers

145

views

Topological sorting of a DAG where special vertices have to come in even groups

cc.complexity-theory graph-algorithms np-hardness topological-sorting

modified Jun 11 at 13:20 a3nm 6,766

3

votes

3

answers

439

views

Best parameterized algorithm for maximum clique

ds.algorithms reference-request np-hardness fixed-parameter-tractable

answered Jun 5 at 20:33 Christian Komusiewicz 866

1

vote

1

answer

78

views

Choosing one number from each set so that the sum of squares of each distinct number counts is minimized

cc.complexity-theory np-hardness np-complete

modified Jun 4 at 5:40 Yonatan N 1,435

-1

votes

1

answer

176

views

Conjecture about ASP reductions between NP-complete problems

cc.complexity-theory np-hardness

answered May 31 at 20:56 Marzio De Biasi 21.4k

1

vote

1

answer

192

views

Is $\{0,1\}$-Vector bin packing NP-Hard when vectors have constant dimension?

reference-request np-hardness packing

modified May 20 at 13:22 Neal Young 6,025

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled