Karpov 21 NP-kompletan problem
U teoriji kompleksnosti, Karpov 21 NP-kompletan problem je skup računskih problema koji su NP-kompletni. U svom radu 1972. "Reducibility Among Combinatorial Problems",[1] Ričard Karp iskoristio je Stiven Kukovu teoremu iz 1971. da je SAT problem NP-kompletan[2] (takodje zvana Kuk-Levinova teorema) da pokaže da postoji polinomijalno vreme smanjivanja svakog od 21 kombinatorna i grafovska računska problema, pokazujući time da su svi NP-kompletni. Ovo je bila jedna od prvih demonstracija od mnogo računskih problema koji se dešavaju u informatici koji su kompleksni. Ova demonstracija budi interesovanje za proučavanje NP-kompletnosti i P=NP problem.
Problemi
Karpov 21 problem, mnogi sa svojim originalnim imenima, su pokazani dole.
- SAT problem: problem zadovoljivosti konjuktivne normalne forme
- 0-1 integer programming
- Clique
- Set packing
- Vertex cover
- Set covering
- Feedback node set
- Feedback arc set
- Problem Hamiltonovog puta
- Satisfiability with at most 3 literals per clause
- Chromatic number (takođe zvan i Graph Coloring Problem)
- Clique cover
- Exact cover
- Hitting set
- Steiner tree
- 3-dimensional matching
- Knapsack
- Job sequencing
- Partition
- Max cut
- Chromatic number (takođe zvan i Graph Coloring Problem)
Kako je vreme prolazilo je otkriveno da su mnogi problemi mogu efikasno rešavati, ako ih ograničimo na posebne slučajeve. Međutim, David Zuckerman je pokazao 1996. da je svaki od ovih 21 problema ima ograničenu optimizovanu verziju koja je nemoguće približiti stalnom faktoru osim P = NP,pokazujući da je Karpov pristup smanjenju generalizuje na određenu vrstu aproksimacije smanjenja.[3] Imajte na umu, međutim, da oni mogu da se razlikuju od standardne verzije optimizacije problema koji mogu imati algoritmi aproksimacija.
Vidi još
- List of NP-complete problems
Reference
- ^ Karp, Richard M. (1972). „Reducibility Among Combinatorial Problems” (PDF). Ур.: R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. стр. 85—103. Архивирано из оригинала (PDF) 29. 06. 2011. г. Приступљено 04. 06. 2013. CS1 одржавање: Текст вишка: списак уредника (веза)
- ^ Stephen Cook (1971). „The Complexity of Theorem Proving Procedures”. Proceedings of the third annual ACM symposium on Theory of computing. стр. 151—158.
- ^ Zuckerman, David (1996). „On Unapproximable Versions of NP-Complete Problems”. SIAM Journal on Computing. 25 (6): 1293—1304. doi:10.1137/S0097539794266407.
Literatura
- Karp, Richard M. (1972). „Reducibility Among Combinatorial Problems” (PDF). Ур.: R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. стр. 85—103. Архивирано из оригинала (PDF) 29. 06. 2011. г. Приступљено 04. 06. 2013. CS1 одржавање: Текст вишка: списак уредника (веза)
- Stephen Cook (1971). „The Complexity of Theorem Proving Procedures”. Proceedings of the third annual ACM symposium on Theory of computing. стр. 151—158.