Polynomial time
★ The P in the P class stands for Polynomial Time.
★ if an optimization problem is easy, its related decision problem is
easy as well
★ It is the collection of decision problems(problems with a “yes” or
“no” answer) that can be solved by a deterministic machine in
polynomial time.
Features:
● The solution to P problems is easy to find.
● P is often a class of computational problems that are solvable and
tractable. Tractable means that the problems can be solved in
theory as well as in practice.
Class P
● The class P consists of those problems that are solvable in
polynomial time.
● can be solved in time O(n^k) for some constant k, where n is the size
of the input to the problem
● The class P consists of those problems that are solvable in
polynomial time and can be solved in time O(nk) for some constant
k, where N is the size of the input to the problem
Polynomial Time Verification
● Many problems are hard to solve, but they have the property that it
easy to authenticate the solution if one is provided.
● Ex: Hamiltonian cycle problem:
● Consider the Hamiltonian cycle problem. Given an undirected graph
G, does G have a cycle that visits each vertex exactly once? There is
no known polynomial time algorithm for this dispute.
● Note: - It means you can't build a Hamiltonian cycle in a graph with
a polynomial time even if there is no specific path is given for the
Hamiltonian cycle with the particular vertex, yet you can't verify the
Hamiltonian cycle within the polynomial time
● We could then inspect the graph and check that this is indeed a legal
cycle and that it visits all of the vertices of the graph exactly once.
Thus, even though we know of no efficient way to solve the
Hamiltonian cycle problem, there is a beneficial way to verify that a
given cycle is indeed a Hamiltonian cycle.
● Note:-For the verification in the Polynomial-time of an undirected
Hamiltonian cycle graph G. There must be exact/specific/definite
path must be given of Hamiltonian cycle then you can verify in the
polynomial time.
● Almost all the algorithms we have studied thus far have been
polynomial-time algorithms: on inputs of size n, their worst-case
running time is O(nk)for some constant k
NP PROBLEM
Definition of NP class Problem: - The set of all decision-based problems
came into the division of NP Problems who can't be solved or produced an
output within polynomial time but verified in the polynomial time. NP
class contains P class as a subset. NP problems being hard to solve.
Note: - The term "NP" does not mean "not polynomial." Originally, the
term meant "non-deterministic polynomial. It means according to the one
input number of output will be produced.
Definition of P class Problem: - The set of decision-based problems come
into the division of P Problems who can be solved or produced an output
within polynomial time. P problems being easy to solve
Definition of Polynomial time: - If we produce an output according to
thegiven input within a specific amount of time such as within a minute,
hours. This is known as Polynomial time.
Definition of Non-Polynomial time: - If we produce an output according
to the given input but there are no time constraints is known as
Non-Polynomial time. But yes output will produce but time is not fixed
yet.
Definition of Decision Based Problem: - A problem is called a
decisionproblem if its output is a simple "yes" or "no" (or you may need
this of this as true/false, 0/1, accept/reject.)
Definition of NP-hard class: - Here you to satisfy the following points to
come into the division of NP-hard
▪ If we can solve this problem in polynomial time, then we can solve all
NP problems in polynomial time
▪ If you convert the issue into one form to another form within the
polynomial time
Definition of NP-complete class: - A problem is in NP-complete, if it is in
NP and it is NP-hard.
NP Class
The NP in NP class stands for Non-deterministic Polynomial Time. It is the
collection of decision problems that can be solved by a non-deterministic
machine in polynomial time.
Features:
● The solutions of the NP class are hard to find since they are being
solved by a non-deterministic machine but the solutions are easy to
verify.
● Problems of NP can be verified by a Turing machine in polynomial
time.
How to prove that a given problem is NP complete?
❖ it requires us to that show every problem in NP is polynomial time
reducible to L.
❖ there is an alternate way to prove it.
❖ The idea is to take a known NP-Complete problem and reduce it to L.
❖ If polynomial time reduction is possible, we can prove that L is
NP-Complete by transitivity of reduction
NP-completeness and reducibility
❖ If any NP-complete problem can be solved in polynomial time, then
every problem in NP has a polynomial-time solution, that is, P = NP.
Despite years of study, though, no polynomial-time algorithm has ever
been discovered for any NP-complete problem. P ≠ NP
Reducibility
❖ a problem Q can be reduced to another problem Q’ if any instance of Q
can be “easilyrephrased” as an instance of Q’, the solution to which
provides a solution to the instance of Q.
RELATION BETWEEN P AND NP PROBLEMS
Decision problems vs. optimization problems
❖ Optimization problems find a feasible solution with the best value
❖ optimization problems, which require some value to be minimized or
maximized.
❖ Decision problems, in which the answer is simply “yes” or “no” (or,
more formally,
“1” or “0”).
❖ Tractable problems vs. intractable problems
❖ Tractable Problem: a problem that is solvable by a polynomial-time
algorithm.
❖ Intractable Problem: a problem that cannot be solved by a
polynomial-time algorithm.
❖ Deterministic Algorithms vs. Non Deterministic Algorithms
❖ The algorithms in which the result of every algorithm is uniquely
defined are known as the Deterministic Algorithm
❖ On other hand, the algorithms in which the result of every algorithm is
not uniquely defined and result could be random are known as the
Non-Deterministic Algorithm
NP HARD PROBLEMS