Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

p hard
np hard

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

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.

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)
  • O(n2)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

    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