New answers tagged optimization
4
votes
Accepted
What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?
Regarding the title of the question:
What is the reason to believe that quantum heuristic [algorithms] can solve NP-Complete problems?
and in particular the statement in the body:
There is an ever [...
8
votes
Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable
The answer to the second question is no. Here is an example when the integer-output optimization problem is polynomial-time solvable, yet its fractional relaxation is NP-complete:
In complements of ...
Top 50 recent answers are included
Related Tags
optimization × 436ds.algorithms × 111
graph-theory × 66
reference-request × 63
cc.complexity-theory × 60
approximation-algorithms × 58
np-hardness × 48
linear-programming × 48
graph-algorithms × 47
convex-optimization × 40
co.combinatorics × 38
machine-learning × 21
integer-programming × 19
time-complexity × 14
cg.comp-geom × 14
linear-algebra × 14
scheduling × 11
quantum-computing × 10
approximation-hardness × 10
heuristics × 10
packing × 10
submodularity × 10
computational-geometry × 9
partition-problem × 9
semidefinite-programming × 8