Trusted answers to developer questions

Ali Zeeshan

Grokking Modern System Design Interview for Engineers & Managers

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.

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.

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.

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

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.

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 |

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

Grokking Modern System Design Interview for Engineers & Managers

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.

Keep Exploring

Related Courses