Please enable JavaScript.
Coggle requires JavaScript to display documents.
P, NP and NP-Complete Problems - Coggle Diagram
P, NP and NP-Complete Problems
-
Class of P problems
Class P is a class of decision problems that can be solved in polynomial time by (deterministic) algorithms. This class of problems is called polynomial.
-
-
Class of NP problems
Class NP is the class of decision problems that can be solved by nondeterministic polynomial algorithms. This class of problems is called nondeterministic polynomial.
-
-
NP-complete problems
Informally, an NP-complete problem is a problem in NP that is as difficult as any other problem in this class, because by definition, any other problem in NP can be reduced to it in polynomial time.
A decision problem D is said to be NP-complete if:
• 1. it belongs to class NP
• 2. every problem in NP is polynomially reducible to D
Polynomially reducible
A decision problem D1 is said to be polynomially reducible to a decision problem D2, if there exists a function t that transforms instances of D1 to instances of D2 such that:
• 1. t maps all yes instances of D1 to yes instances of D2 and all no instances of D1 to no instances of D2
• 2. t is computable by a polynomial time algorithm
-
-