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", Ričard Karp iskoristio je Stiven Kukovu teoremu iz 1971. da je SAT problem NP-kompletan (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. 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

Literatura 
 
 

НП-комплетни проблеми
U teoriji kompleksnosti , KarpovNP-kompletan problem je skup računskih problema koji su NP-kompletni . U svom radu " Reducibility Among Combinatorial Problems " , Ričard Karp iskoristio je Stiven Kukovu teoremu iz da je SAT problem NP-kompletan ( takodje zvana Kuk-Levinova teorema ) da pokaže da postoji polinomijalno vreme smanjivanja svakog odkombinatorna 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 Karpovproblem , mnogi sa svojim originalnim imenima , su pokazani dole . SAT problem : problem zadovoljivosti konjuktivne normalne forme integer programming Clique Set packing Vertex cover Set covering Feedback node set Feedback arc set Problem Hamiltonovog puta Satisfiability with at mostliterals per clause Chromatic number ( takođe zvan i Graph Coloring Problem ) Clique cover Exact cover Hitting set Steiner tree 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 da je svaki od ovihproblema 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 . 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 Literatura НП-комплетни проблеми