Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2006
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915559920107520 |
|---|---|
| author | Hofman, Radoslaw |
| author_facet | Hofman, Radoslaw |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_cs_0611008 |
| institution | arXiv |
| publishDate | 2006 |
| record_format | arxiv |
| spellingShingle | Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time Hofman, Radoslaw Computational Complexity Discrete Mathematics Data Structures and Algorithms Numerical Analysis F.1; F.2 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. |
| title | Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms Numerical Analysis F.1; F.2 |
| url | https://arxiv.org/abs/cs/0611008 |