Explain in brief about the classes P, NP, and NP complete with examples.

Question

Bipin Tiwari · Accepted Answer

P Class The P in the P class stands for Polynomial Time. 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. eatures: 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. But the problems that can be solved in theory but not in practice are known as intractable. This class contains many natural problems like: Calculating the greatest common divisor. Finding a maximum matching. Decision versions of linear programming. 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. This class contains many problems that one would like to be able to solve effectively: Boolean Satisfiability Problem (SAT). Hamiltonian Path Problem. Graph coloring. NP-complete class A problem is NP-complete if it is both NP and NP-hard. NP-complete problems are the hard problems in NP. Features: NP-complete problems are special as any problem in NP class can be transformed or reduced into NP-complete problems in polynomial time. If one could solve an NP-complete problem in polynomial time, then one could also solve any NP problem in polynomial time. Some example problems include: Decision version of 0/1 Knapsack. Hamiltonian Cycle. Satisfiability. Vertex cover.

Explain in brief about the classes P, NP, and NP complete with examples.

Leave your Answer:

Hits Counter

Question

Explain in brief about the classes P, NP, and NP complete with examples.

Leave your Answer: