Understanding P vs. NP: A Comprehensive Overview
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.
