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.

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.

Pogledati još[уреди]

Reference[уреди]

  1. ^ Karp, Richard M. (1972). „Reducibility Among Combinatorial Problems“. In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. стр. 85–103. 
  2. ^ Stephen Cook (1971). „The Complexity of Theorem Proving Procedures“. Proceedings of the third annual ACM symposium on Theory of computing. стр. 151–158. 
  3. ^ David Zuckerman (1996). „On Unapproximable Versions of NP-Complete Problems“. SIAM Journal on Computing 25 (6): 1293–1304. DOI:10.1137/S0097539794266407. 

Literatura[уреди]