Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time
<|reference_start|>Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time: This article discusses ability of Linear Programming models to be used as solvers of NP-complete problems. Integer Linear Programming is known as NP-complete problem, but non-integer Linear Programming problems can be solved in polynomial time, what places them in P class. During past three years there appeared some articles using LP to solve NP-complete problems. This methods use large number of variables (O(n^9)) solving correctly almost all instances that can be solved in reasonable time. Can they solve infinitively large instances? This article gives answer to this question.<|reference_end|>
@article{hofman2006why,
    title={Why Linear Programming cannot solve large instances of NP-complete
  problems in polynomial time},
    author={Radoslaw Hofman},
    journal={arXiv preprint arXiv:cs/0611008},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0611008},
    primaryClass={cs.CC cs.DM cs.DS cs.NA}
}