P vs. NP: A Comprehensive Overview
NP – HARD
JAYASRI JETTI
CHINMAYA KRISHNA SURYADEVARA
P and NP
P – The set of all problems solvable in polynomial
time by a deterministic Turing Machine (DTM).
Example: Sorting and searching.
P and NP
•
NP- the set of all problems solvable in
polynomial time by non deterministic Turing
Machine (NDTM)
•
Example Partition.
P is a subset of NP
NP complete
•
NP – Complete (NP – C): the set of all problems in
NP “at least as hard” as every other problem in
NP.
•
To prove a problem x is NP complete
–
Show that x is in NP
–
Show that some other NP - C problem reduces to x
•
If an NP hard problem can be solved in
polynomial time, then all NP complete problems
can be solved in polynomial time.
•
NP – H includes all NP - C problems
Deterministic and non deterministic
problems
•
Algorithm is deterministic if for a given input
the output generated is same for function.
•
A mathematical function is deterministic
hence the state is known at every step of
algorithm.
•
Algorithm is nondeterministic if there are
more than one path the algorithm can take.
Due to this one cannot determine the next
state of the machine running the algorithm.
•
To specify such algorithms we introduce three
statements
–
Choice(s)
- arbitrary choose one of the elements of
the set S
–
Failure
- signals an unsuccessful completion
–
Success
- signals a successful completion
•
Whenever there is a set of choices that leads
to a successful completion than one search set
of choices is always made and the algorithm
terminates.
•
A nondeterministic algorithm terminates
unsuccessfully iff there exists no set of choices
leading to a successful signal
•
A machine capable of executing a
nondeterministic algorithm is called a
nondeterministic machine.
•
While nondeterministic machine do not exist
in practice they will provide strong reason to
conclude that certain problems cannot be
solved by fast deterministic algorithms
•
Example of nondeterministic algorithm
// the problem is to search for an element X//
//output j such that A(j) = x; or j = 0 if x is not in A//
j -> choice (1:n)
If A(j)= x then print (j); success end if
Print (‘0’); failure
Complexity O(1);
Nondeterministic decision algorithms generate a
zero or 1 as their output.
Definition of classes NP - hard and
NP - complete
•
P is a set of all decision problems solvable by a
deterministic algorithm in polynomial time.
•
NP is a set of all decision problems solvable by
a nondeterministic algorithm in polynomial
time.
•
Since deterministic algorithms are special case
of nondeterministic ones, we can conclude
that
P
NP
Reducibility
Let L1 and L2 be problems. L1 reduces to L2 (L1
L2) if and only if there is a deterministic
polynomial time algorithm to solve L1 that
solves L2 in polynomial time
If L1
L2 and L2
L3 then L1
L3
Definition: NP-Hard problem: a problem L is NP
hard iff satisfiability reduces to L
Definition : NP-complete Problem
:
•
A problem L is NP-complete if and only if L is NP-hard
and L
є
NP.
•
There are NP-hard problems that are not NP-complete.
Example :
•
Halting problem is NP-hard decision problem, but it is
not NP-complete.
Halting Problem
:
•
To determine for an arbitrary deterministic algorithm A
and an input I whether algorithm A with input I ever
terminates (or enters an infinite loop).
Halting problem is not NP-complete;
but NP-hard
•
Halting problem is un-decidable.
- Hence there exists no algorithm to solve this
problem.
- So, it is not in NP.
- So, it is not NP-complete.
Halting problem is NP-hard
•
To show that Halting problem is NP-hard, we
show that satisfiability is
halting problem.
•
For this let us construct an algorithm A whose
input is a prepositional formula X.
- Suppose X has n variables.
- Algorithm A tries out all 2
n
possible truth
assignments and verifies if X is satisfiable.
Halting problem is NP-hard
(Contd..)
- If it is satisfied then A stops.
- If X is not satisfiable, then A enters an infinite
loop.
- Hence A halts on input iff X is satisfiable.
- If we had a polynomial time algorithm for the
halting problem, then we could solve the
satisfiability problem in polynomial time using A
and X as input to the algorithm for the halting
problem .
- Hence the halting problem is an NP-hard problem
which is not in NP.
- So it is not NP-complete.
NP-HARD GRAPH AND SCHEDULING
PROBLEMS (CONTD..)
1.
Chromatic Number Decision Problem (CNP)
•
A coloring of a graph G = (V,E) is a function
f : V
{ 1,2, …, k}
i
V .
•
If (U,V)
E then f(u)
f(v).
•
The CNP is to determine if G has a coloring
for a given K.
•
Satisfiability with at most three literals per
clause
chromatic number problem.
CNP is NP-hard.
NP-HARD GRAPH AND SCHEDULING
PROBLEMS (contd..)
2.
Directed Hamiltonian Cycle (DHC)
•
Let G = (V,E) be a directed graph and length n =
V
•
The DHC is a cycle that goes through every
vertex exactly once and then returns to the
starting vertex.
•
The DHC problem is to determine if G has a
directed Hamiltonian Cycle.
Theorem
: CNF (Conjunctive Normal Form)
satisfiability
DHC
DHC is NP-hard.
NP-HARD GRAPH AND SCHEDULING
PROBLEMS (CONTD..)
3.
Travelling Salesperson Decision Problem
(TSP) :
•
The problem is to determine if a complete
directed graph G = (V,E) with edge costs
C(u, v) has a tour of cost at most M.
Theorem
: Directed Hamiltonian Cycle (DHC)
TSP
TSP is NP-hard.
SOME SIMPLIIFIED NP-HARD
PROBLEMS
•
An NP-hard problem L cannot be solved in
deterministic polynomial time.
•
By placing enough restrictions on any NP
hard problem, we can arrive at a polynomial
solvable problem.
Examples.
(i) CNF(conjuctive normal form)- Satisfiability
with at most three literals per clause is NP-
hard.
If each clause is restricted to have at most
two literals then CNF-satisfiability is
polynomial solvable
(ii)Generating optimal code for a parallel
assignment statement is NP-hard,
- however if the expressions are restricted
to be simple variables, then optimal code can
be generated in polynomial time.
(iii)Generating optimal code for level one
directed a- cyclic graphs is NP-hard but
optimal code for trees can be generated in
polynomial time.
(iv)Determining if a planner graph is three
colorable is NP-Hard
- To determine if it is two colorable is a
polynomial complexity problem.
•
https://www.youtube.com/watch?v=CY_klh5u
D-E
THANK YOU
Delve into the complexities of computational problem-solving with insights on P, NP, NP-complete, determinism, and non-determinism. Explore the distinctions between deterministic and non-deterministic algorithms and the implications they have on problem-solving capabilities. Gain a deeper understanding of the essential concepts that underpin the P vs. NP debate.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
NP HARD JAYASRI JETTI CHINMAYA KRISHNA SURYADEVARA
P and NP P The set of all problems solvable in polynomial time by a deterministic Turing Machine (DTM). Example: Sorting and searching.
P and NP NP- the set of all problems solvable in polynomial time by non deterministic Turing Machine (NDTM) Example Partition. P is a subset of NP
NP complete NP Complete (NP C): the set of all problems in NP at least as hard as every other problem in NP. To prove a problem x is NP complete Show that x is in NP Show that some other NP - C problem reduces to x If an NP hard problem can be solved in polynomial time, then all NP complete problems can be solved in polynomial time. NP H includes all NP - C problems
Deterministic and non deterministic problems Algorithm is deterministic if for a given input the output generated is same for function. A mathematical function is deterministic hence the state is known at every step of algorithm.
Algorithm is nondeterministic if there are more than one path the algorithm can take. Due to this one cannot determine the next state of the machine running the algorithm. To specify such algorithms we introduce three statements Choice(s) - arbitrary choose one of the elements of the set S Failure - signals an unsuccessful completion Success - signals a successful completion
Whenever there is a set of choices that leads to a successful completion than one search set of choices is always made and the algorithm terminates. A nondeterministic algorithm terminates unsuccessfully iff there exists no set of choices leading to a successful signal
A machine capable of executing a nondeterministic algorithm is called a nondeterministic machine. While nondeterministic machine do not exist in practice they will provide strong reason to conclude that certain problems cannot be solved by fast deterministic algorithms
Example of nondeterministic algorithm // the problem is to search for an element X// //output j such that A(j) = x; or j = 0 if x is not in A// j -> choice (1:n) If A(j)= x then print (j); success end if Print ( 0 ); failure Complexity O(1); Nondeterministic decision algorithms generate a zero or 1 as their output.
Definition of classes NP - hard and NP - complete P is a set of all decision problems solvable by a deterministic algorithm in polynomial time. NP is a set of all decision problems solvable by a nondeterministic algorithm in polynomial time. Since deterministic algorithms are special case of nondeterministic ones, we can conclude that P NP
Reducibility Let L1 and L2 be problems. L1 reduces to L2 (L1 L2) if and only if there is a deterministic polynomial time algorithm to solve L1 that solves L2 in polynomial time If L1 L2 and L2 L3 then L1 L3 Definition: NP-Hard problem: a problem L is NP hard iff satisfiability reduces to L
Definition : NP-complete Problem : A problem L is NP-complete if and only if L is NP-hard and L NP. There are NP-hard problems that are not NP-complete. Example : Halting problem is NP-hard decision problem, but it is not NP-complete. Halting Problem : To determine for an arbitrary deterministic algorithm A and an input I whether algorithm A with input I ever terminates (or enters an infinite loop).
Halting problem is not NP-complete; but NP-hard Halting problem is un-decidable. - Hence there exists no algorithm to solve this problem. - So, it is not in NP. - So, it is not NP-complete. Halting problem is NP-hard To show that Halting problem is NP-hard, we show that satisfiability is halting problem. For this let us construct an algorithm A whose input is a prepositional formula X. - Suppose X has n variables. - Algorithm A tries out all 2npossible truth assignments and verifies if X is satisfiable.
Halting problem is NP-hard (Contd..) - If it is satisfied then A stops. - If X is not satisfiable, then A enters an infinite loop. - Hence A halts on input iff X is satisfiable. - If we had a polynomial time algorithm for the halting problem, then we could solve the satisfiability problem in polynomial time using A and X as input to the algorithm for the halting problem . - Hence the halting problem is an NP-hard problem which is not in NP. - So it is not NP-complete.
NP-HARD GRAPH AND SCHEDULING PROBLEMS (CONTD..) 1. Chromatic Number Decision Problem (CNP) A coloring of a graph G = (V,E) is a function f : V { 1,2, , k} i V . If (U,V) E then f(u) f(v). The CNP is to determine if G has a coloring for a given K. Satisfiability with at most three literals per clause chromatic number problem. CNP is NP-hard.
NP-HARD GRAPH AND SCHEDULING PROBLEMS (contd..) 2. Directed Hamiltonian Cycle (DHC) Let G = (V,E) be a directed graph and length n = V The DHC is a cycle that goes through every vertex exactly once and then returns to the starting vertex. The DHC problem is to determine if G has a directed Hamiltonian Cycle. Theorem : CNF (Conjunctive satisfiability DHC DHC is NP-hard. Normal Form)
NP-HARD GRAPH AND SCHEDULING PROBLEMS (CONTD..) 3. Travelling Salesperson Decision Problem (TSP) : The problem is to determine if a complete directed graph G = (V,E) with edge costs C(u, v) has a tour of cost at most M. Theorem : Directed Hamiltonian Cycle (DHC) TSP TSP is NP-hard.
SOME SIMPLIIFIED NP-HARD PROBLEMS An NP-hard problem L cannot be solved in deterministic polynomial time. By placing enough restrictions on any NP hard problem, we can arrive at a polynomial solvable problem.
Examples. (i) CNF(conjuctive normal form)- Satisfiability with at most three literals per clause is NP- hard. If each clause is restricted to have at most two literals then polynomial solvable (ii)Generating optimal code for a parallel assignment statement is NP-hard, - however if the expressions are restricted to be simple variables, then optimal code can be generated in polynomial time. CNF-satisfiability is
(iii)Generating optimal code for level one directed a- cyclic graphs is NP-hard but optimal code for trees can be generated in polynomial time. (iv)Determining if a planner graph is three colorable is NP-Hard - To determine if it is two colorable is a polynomial complexity problem.
