Please enable JavaScript.
Coggle requires JavaScript to display documents.
P, NP, and NP-Complete Problems - Coggle Diagram
P, NP, and NP-Complete Problems
In the study of the computational complexity of problems, the first concern of both
computer scientists and computing professionals is whether a given problem can be solved in polynomial time by some algorithm
We say that an algorithm solves a problem in polynomial time
if its worst-case time efficiency belongs to O(p(n)) where p(n) is a polynomial of the problem’s input size n
Problems that can be solved in polynomial time are called tractable, and problems that cannot be solved in polynomial time are called intractable
We cannot solve arbitrary instances of intractable problems in a reasonable amount of time
unless such instances are very small
Polynomial functions possess many convenient properties; in particular, both the sum and composition of two polynomials are always polynomials too. the choice of this class has led to a development of an extensive theory
called computational complexity, which seeks to classify problems according to their inherent difficulty
A problem’s intractability remains the same for all principal models of computations and all reasonable
input-encoding schemes for the problem under consideration
Most basic problems studied so far, like sorting a list, searching for a key in a list or for a pattern in a text
string, checking connectivity and acyclicity of a graph, finding a minimum spanning tree and shortest paths in a weighted graph can be solved in polynomial time by some algorithm
-
A nondeterministic algorithm is a two-stage procedure that
takes as its input an instance I of a decision problem and has a guessing and a verification stage
We say that a nondeterministic algorithm solves a decision problem if and
only if for every yes instance of the problem it returns yes on some execution
A nondeterministic algorithm is said to
be nondeterministic polynomial if the time efficiency of its verification stage is polynomial
Class NP is the class of decision problems that can be solved by
nondeterministic polynomial algorithms
NP-Complete Programs
It 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 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:
t maps all yes instances of D1 to yes instances of D2 and all no instances of D1
to no instances of D2
-
-