×

Algorithms Tutorial

Searching Algorithms

Dynamic Programming

Graph Algorithms

Backtracking Algorithms

Recursion

Operating System Algorithms

Miscellaneous Topics

P and NP problems and solutions | Algorithms

In this article, we learn about the concept of P problems, NP problems, NP hard problems and NP complete problems.
Submitted by Shivangi Jain, on July 29, 2018

P Problems

P is the set of all the decision problems solvable by deterministic algorithms in polynomial time.

NP Problems

NP is the set of all the decision problems that are solvable by non - deterministic algorithms in polynomial time.

Since deterministic algorithms are just the special case of non - deterministic ones, so we can conclude that P is the subset of NP.

P and NP problems

Relation between P and NP

NP Hard Problem

A problem L is the NP hard if and only if satisfiability reduces to L. A problem is NP complete if and only if L is the NP hard and L belongs to NP.

Only a decision problem can be NP complete. However, an optimization problem may be the NP hard. Furthermore if L1 is a decision problem and L2 an optimization problem, then it is possible that L1 α L2. One can trivially show that the knapsack decision problem reduces to knapsack optimization problem. For the clique problem one can easily show that the clique decision problem reduces to the clique optimization problem. In fact, one can also show that these optimization problems reduce to their corresponding decision problems.

P, NP and HNP problems

NP Completeness Problem

Polynomial time reductions provide a formal means for showing that one problem is at least as hard as another, within a polynomial time factor. This means, if L1 <= L2, then L1 is not more than a polynomial factor harder than L2. Which is why the “less than or equal to” notation for reduction is mnemonic. NP complete are the problems whose status are unknown.

Some of the examples of NP complete problems are:

1. Travelling Salesman Problem:

Given n cities, the distance between them and a number D, does exist a tor programme for a salesman to visit all the cities so that the total distance travelled is at most D.

2. Zero One Programming Problem:

Given m simultaneous equations,

Zero One Programming Problem

3. Satisfiability Problem:

Given a formula that involves propositional variables and logical connectives.

A language L is the subset [0, 1]* is NP complete if,

  1. L belongs to NP and
  2. L' ← L for every L' belongs to NP

All NP complete problems are NP hard, but some NP hard problems are not known to be NP complete.

If NP hard problems can be solved in polynomial time, then all the NP complete problems can be solved in polynomial time.


Related Tutorials



Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.