5 Difference Between NP Hard And NP Complete Problem

What Is NP Problem?

These are the decision problems which can be verified in polynomial time. That means, if I claim that there is a polynomial time solution for a particular problem, you ask me to prove it. Then, I will give you a proof which you can easily verify in polynomial time. These kind of problems are called NP problems. Note that, here we are not talking about whether there is a polynomial time solution for this problem or not. But we are talking about verifying the solution to a given problem in polynomial time.

To answer the rest of question, you first need to understand which NP-hard problems are also NP-complete. If an NP-hard problem belongs to set NP, then it is NP-complete. To belong to set NP, a problem needs to be

(i) A decision problem,
(ii) The number of solutions to the problem should be finite and each solution should be of polynomial length, and
(iii) Given a polynomial length solution, we should be able to say whether the answer to the problem is yes/no.

What Is NP Complete Problem?

These are the problems which are both NP and NP-Hard. That means, if we can solve these problems, we can solve any other NP problem and the solutions to these problems can be verified in polynomial time.

In other words, NP-Complete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time.

Intuitively this means that we can solve Y quickly if we know how to solve X quickly. Precisely, Y is reducible to X, if there is a polynomial time algorithm f to transform instances y of Y to instances x = f(y) of X in polynomial time, with the property that the answer to y is yes, if and only if the answer to f(y) is yes.

Example

3-SAT. This is the problem wherein we are given a conjunction (ANDs) of 3-clause disjunctions (ORs), statements of the form

(x_v11 OR x_v21 OR x_v31) AND (x_v12 OR x_v22 OR x_v32) AND ... AND (x_v1n OR x_v2n OR x_v3n) 

where each x_vij is a boolean variable or the negation of a variable from a finite predefined list (x_1, x_2, ... x_n).

It can be shown that every NP problem can be reduced to 3-SAT. The proof of this is technical and requires use of the technical definition of NP (based on non-deterministic Turing machines). This is known as Cook’s theorem.

What makes NP-complete problems important is that if a deterministic polynomial time algorithm can be found to solve one of them, every NP problem is solvable in polynomial time (one problem to rule them all).

What You Need To Know About NP Complete

• NP-Complete problems can be solved by deterministic algorithm in polynomial time.
• To solve this problem, it must be both NP and NP-hard problem.
• It is exclusively a decision problem.
• Examples include: Minesweeper problem, Determining whether a graph has a Hamiltonian cycle, Determining whether Boolean formula is satisfiable or not etc.

Also Read: Difference Between Deterministic And Non-deterministic Algorithms

What Is NP Hard Problem?

These are at least as hard as the hardest problems in NP. If we can solve these problems in polynomial time, we can solve any NP problem that can possibly exist. Note that these problems are not necessarily NP problems. That means, we may/may-not verify the solution to these problems in polynomial time.

Intuitively, these are the problems that are at least as hard as the NP-complete problems. Note that NP-hard problems do not have to be in NP, and they do not have to be decision problems.

The precise definition here is that a problem X is NP-hard, if there is an NP-complete problem Y, such that Y is reducible to X in polynomial time.

But since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then, if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time.

Example

The halting problem is an NP-hard problem. This is the problem that given a program P and input I, will it halt? This is a decision problem but it is not in NP. It is clear that any NP-complete problem can be reduced to this one. As another example, any NP-complete problem is NP-hard.

What You Need To Know About NP Hard Problem  

• NP-Hard problems (say X) can be solved if and only if there is a NP-Complete problem (say Y) can be reducible into X in polynomial time.
• To solve this problem, it must be a NP problem.
• It is not a decision problem.
• Examples include: Halting problem, Vertex cover problem, Circuit-satisfiability problem etc.

Also Read: Difference Between P And NP Problems

Difference Between NP Hard And NP Complete Problem In Tabular Form

ncG1vNJzZmiumauupbXFn5yrnZ6YsrR6wqikaJyZm7OmvsSnmp5lkprBuLHEp2SnqF2drrOwjJqlnWWepXqku8ypo56slWK9s7vBpZymZw%3D%3D