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

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.
^ 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.
Stephen Cook (1971). „The Complexity of Theorem Proving Procedures”. Proceedings of the third annual ACM symposium on Theory of computing. стр. 151—158.

[1] 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.

[2] Stephen Cook (1971). „The Complexity of Theorem Proving Procedures”. Proceedings of the third annual ACM symposium on Theory of computing. стр. 151—158.

[3] Zuckerman, David (1996). „On Unapproximable Versions of NP-Complete Problems”. SIAM Journal on Computing. 25 (6): 1293—1304. doi:10.1137/S0097539794266407.

[1]

[2]

[3]