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 [...
- 957
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 ...
- 11.1k
Top 50 recent answers are included