# 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.

**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.

### 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,

**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,

- L belongs to NP and
- 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.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions