Why LP Cannot Solve Large Instances of NP-complete Problems in Polynomial Time.
Radoslaw HofmanPublished in: IMECS (2007)
Keyphrases
- np complete problems
- np complete
- graph coloring
- phase transition
- suboptimal solutions
- random instances
- computational complexity
- linear programming
- special case
- hard problems
- randomly generated
- optimal solution
- combinatorial problems
- linear program
- timetabling problem
- constraint satisfaction problems
- upper bound
- search space
- neural network