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

more tags

Active Hot Week Month

0

votes

1

answer

70

views

Is the counting version of 1-in-3 Sat #P-complete?

cc.complexity-theory np-hardness counting-complexity

modified Jan 20 at 18:04 Gamow 4,647

6

votes

1

answer

72

views

Determining if a word of specific length exists that is not accepted by a NFA

np-hardness time-complexity nondeterminism nfa

modified Jan 19 at 19:20 D.W. 8,836

0

votes

0

answers

73

views

NP-Hard Knapsack Instances

np-hardness optimization

asked Jan 18 at 23:54 FiB 141

24

votes

5

answers

3k

views

Implications of unprovability of $P\neq NP$

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

modified Jan 14 at 11:01 Yu Li 1

0

votes

0

answers

44

views

Complexity of multi-objective optimization problems

np-hardness optimization time-complexity np-complete complexity

asked Dec 31 '19 at 1:32 Iago Carvalho 175

1

vote

0

answers

92

views

how to model community detection into np-hard problem

np-hardness clustering

modified Dec 27 '19 at 7:13 Refrain 21

1

vote

1

answer

70

views

The decision procedure of theory of closed real field is in NP-hard?

cc.complexity-theory np-hardness complexity-classes computational-geometry

answered Dec 21 '19 at 7:32 David Eppstein 47.6k

4

votes

1

answer

114

views

Hardness of finding if a vertex lies on a simple directed path between two vertices

graph-theory graph-algorithms np-hardness disjoint-paths

modified Dec 19 '19 at 12:15 narek Bojikian 201

6

votes

2

answers

143

views

$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$

reference-request graph-theory np-hardness partition-problem

answered Dec 14 '19 at 21:36 Timon Knigge 73

9

votes

2

answers

111

views

Complexity of finding an edge set yielding specified vertex degrees

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

answered Dec 14 '19 at 2:27 user55551 31

37

votes

16

answers

6k

views

Everyday encounters with NP-complete problems

np-hardness big-list

answered Dec 10 '19 at 16:26 Massimo Cafaro 2,156

12

votes

0

answers

120

views

NP-Hardness of 4-cycle packing problem in complete bipartite digraph?

graph-theory np-hardness

modified Dec 10 '19 at 12:47 John 343

10

votes

1

answer

691

views

Relationship between two graph optimization problems

graph-algorithms np-hardness np-complete

answered Nov 18 '19 at 10:51 Antti Röyskö 551

2

votes

1

answer

134

views

What Is the Complexity of This Two-to-One Matching Problem?

np-hardness reductions

modified Nov 15 '19 at 13:36 Antti Röyskö 551

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled