Related Tags

p hard
np hard

# What is the difference between P and NP-hard problems?

Ali Zeeshan

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

## Overview

The various problems in computer science can be divided into two major kinds:

• P problems
• NP problems

P problems are those that can be solved in polynomial time. NP problems can be both NP-complete and NP-hard.

Venn diagram representation

### P problems

These are easier problems to solve. In scientific terms, the problems that can be solved in a polynomial time are called P problems. The polynomial here means that the time complexity can be any polynomial function instead of an exponential one.

There are several common problems in computer science that have been solved and tested in polynomial time.

Examples of polynomial time include:

• $O(n)$
• $O(n^2)$ etc.
1 of 3

### NP problems

NP problems do not have a deterministic solution such that they can be solved in polynomial time. Hence, it is known as a non-deterministic polynomial problem.

A polynomial solution to such a problem can only be achieved using a non-deterministic Turing machine. NP problems are a superset of P problems.

### NP-hard problems

One kind of NP problem is the NP-hard problem. NP-hard problems are equally hard or harder than NP problems. This implies that they can be more complex and don't need to be a part of the set of NP problems at all.

The problems in computer science can be termed as NP-hard if there is an NP-complete problem that can be reduced to that problem in any polynomial time.

NP-complete problems are ones that are both NP and NP-Hard. In a Venn diagram, it is the intersection of both NP and NP-hard problems.

1 of 3

### Conclusion

 P NP Are solved deterministically in polynomial time Can only be solved non-deterministically for a polynomial solution Use a deterministic Turing machine They can only be solved deterministically in exponential time Includes string matching, palindrome, Dijkstra, Bellman Ford, and so on Includes halting, decision subset sum, and so on

RELATED TAGS

p hard
np hard

CONTRIBUTOR

Ali Zeeshan