New answers tagged reductions
1
vote
Accepted
Showing that a modification of an NP-Complete problem is also NP-Complete
tl;dr: Showing that the Extended Knapsack problem is NP-Complete is easy through the original Knapsack, but you have to define the two problems correctly.
For a problem to be NP-Complete, it has to be ...
Top 50 recent answers are included
Related Tags
reductions × 191cc.complexity-theory × 90
np-hardness × 47
graph-theory × 22
complexity-classes × 22
sat × 21
reference-request × 16
graph-algorithms × 13
np-complete × 13
counting-complexity × 12
ds.algorithms × 9
approximation-algorithms × 7
parameterized-complexity × 7
np × 6
polynomial-time × 6
computability × 5
time-complexity × 5
big-list × 5
clique × 5
relativization × 5
graph-isomorphism × 4
oracles × 4
space-bounded × 4
partition-problem × 4
lower-bounds × 3