NP-CompleteOverviewRelated Concepts and TermsOrigins and Terminology of NP-CCook’s ContributionsKarp’s RefinementsLevin and modern terminologyNP-C FactsRelations of NPNP-Complete Proof StepsWorking with NP-CompleteFuture of NP-CompleteReferencesNP-Complete William StricklandCOT4810 Spring 2008February 7, 2008OverviewRelated Concepts and TermsOrigins and Terminology of NP-CNP-C FactsRelations of NPNP Complete Proof StepsWorking with NP-CompleteFuture of NP-CompleteRelated Concepts and TermsNon-deterministic Machine Accelerates problem solution over deterministic machine.Branches computation at choice points.Machine can process infinite number of choices in parallel.Usually ‘implemented’ as Turing machine.Deterministic machine is non-deterministic without choices.Problem characteristicsProblem complexity equals best known solution complexity.Intractable if no polynomial solution.Is complete if it is hardest member of its own class.Origins and Terminology of NP-CRelated Concepts and TermsCook’s ContributionsKarp’s RefinementsLevin and modern terminologyCook’s ContributionsConcept of NP-complete originates with Steven Cook in 1971Class P and NP defined:P defined as problem that can be solved in polynomial time on deterministic machine.NP defined as problems that have Polynomial solutions on non-deterministic machines.Proved Satisfiability problem to be hardest in NP class.Demonstrated reductions using polynomial time Turing machine.Karp’s RefinementsIn 1972, Richard Karp defined NP-complete as we know it todaySimplified reduction to polynomial transformationMany more NP-complete problems provenCreated the “Polynomial Complete” class (now known as NP-C)Levin and modern terminologyIn 1973, Leonid Levin provided showed alternate theorem similar to Cook’s.Largely due to efforts of Donald Knuth modern terms are accepted in 1974.NP-complete Coined.NP-hard coined to describe problems at least as hard as NP-Complete. In 1978, Strong NP-C coined by Michael Garey and Donald Johnson as problems still NP-C when using unary language.NP-C FactsHardest problems in NP class.Any NP problem can be reduced to NP-C problem in polynomial time.Any NP-Complete problem can be reduced to any other NP-C problem in polynomial time.If Polynomial solution found for one, there is polynomial solution to all NP problems and P=NP.If NP problem proven to be intractable then NP-C intractable and P≠NP.Relations of NPPNP-CcoNP-CcoNP NP*Assuming P≠NP and NP≠coNPAdapted from [Garey 157]NP-Complete Proof StepsFour steps to prove is NP-CShow is NP.Select known NP-C.Transform known NP-C to NP-C in question. Prove transformation is polynomial. Typical proof if is by restriction; show known NP-C as special case.Working with NP-Complete 5 methods to find solutions to NP-complete in reasonable timeSpecial case – determine if special case, if so attempt to find polynomial solution to this case only.Dynamic programming and Branch-and-Bound – search intelligently for a solution in exponential set. Probabilistic – write the algorithm be written in such a way as the common case will have polynomial time even if other cases remain exponential. Approximation – find acceptable approximation of the answer be found in polynomial time. Heuristic – sacrifice provable accuracy for fast generation of a ‘good’ approximate solution.Future of NP-CompleteIf proven intractable:NP-C based cryptography validated.Continued efforts on approximation algorithms.More approximation support in hardware. If polynomial solution found: All NP problems (most practical problems) are polynomial.One algorithm solves all solution to almost any problem.Hardware to accelerate algorithm.NP-C based cryptography no longer viable.ReferencesBlum, Lenore, et al. Complexity and Real Computation. New York: Springer-Verlag, 1998Dewdney, A.K.. The New Turing Omnibus. 1989. 1st. New York: Henry Holt and Company, 1993.Garey, Michael R., and Johnson, David S. Computers and Intractability. New York: W. H. Freeman and Company, 1979.Mehlhoun, Kurt. Data Structures and Algorithms. Graphing Algorithms and NP-Completeness 2. Berlin: Springer-Verlag, 1984.Rothe, Jörg. Complexity Theory and Cryptography. Berlin: Springer-Verlag, 2005.Smith, Carl H. A Recursive Introduction to Theory of Computation. New York: Springer-Verlag, 1994.Wilf, Herbert S. Algorithms and Complexity. Englewood Cliffs, New York: Prentice-Hall, 1986.Questions:1) The Selection sort algorithm solves the sequential sorting problem. True or False, This problem is a NP class problem.2) Using what technique can an algorithm always produce the exact solution to a NP-C problem, yet average polynomial
View Full Document
Unlocking...