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

6

votes

1

answer

205

views

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

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

modified yesterday CommunityBot 1

1

vote

0

answers

32

views

Is the following special case of multiway number partitioning NP-hard?

np-hardness time-complexity partition-problem

asked Jan 13 at 16:49 Ryoshun Oba 11

1

vote

0

answers

30

views

What type of Problems (Class and types) Can Be Solved Effectively with Quantum Computers?

np-hardness quantum-computing matrices

modified Jan 12 at 22:21 VenomFangs 111

1

vote

1

answer

160

views

How to show that Color Tiles is NP-Complete

graph-theory np-hardness np-complete

modified Jan 8 at 20:29 Marzio De Biasi 22.2k

1

vote

2

answers

242

views

Node-weighted steiner problem with few terminals

graph-algorithms np-hardness parameterized-complexity fixed-parameter-tractable

answered Jan 5 at 17:18 Austin Buchanan 1,136

4

votes

0

answers

289

views

Computational Complexity of cycle double cover

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

modified Jan 2 at 14:54 domotorp 13.5k

1

vote

1

answer

66

views

Set cover with rewards

np-hardness set-cover

modified Dec 20 '21 at 15:26 Mary Eiven 13

23

votes

1

answer

2k

views

Tardos Function Counterexample to Blum's $P\neq NP$ Claim

cc.complexity-theory np-hardness complexity-classes

modified Dec 16 '21 at 10:01 Stasys 6,555

2

votes

0

answers

74

views

NP-hardness of Euclidean k-Median for k = 2

reference-request np-hardness clustering

asked Dec 15 '21 at 15:37 Inuyasha Yagami 1,369

4

votes

0

answers

89

views

Analogue of Chow-Liu tree for $L_1$

np-hardness optimization approximation-hardness

modified Dec 15 '21 at 15:23 Aryeh 9,844

16

votes

1

answer

524

views

Natural candidates for the hierarchy inside NPI

cc.complexity-theory np-hardness np-intermediate

modified Dec 10 '21 at 19:59 daniel pehoushek 95

1

vote

1

answer

197

views

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

np-hardness sat reductions boolean-formulas

modified Nov 25 '21 at 8:22 ferris 11

5

votes

1

answer

229

views

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

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

modified Nov 19 '21 at 1:00 CommunityBot 1

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled