P and NP

Difference between P and NP.

P and NP

P is the set of problems solvable in polynomial time. NP is the set where a given solution can be verified in polynomial time.

Every P problem is in NP. But is all of NP in P? This is the biggest open question in computer science.

Verification example

Checking whether an array is sorted is O(n): compare each adjacent pair. So sorting verification is in P.

A function that checks whether an array is sorted is an example of the P class. Give it a solution (sorted array), and it verifies instantly.

Exercise is_sorted function

Write is_sorted(arr). Return whether the array is sorted. Print True with print(is_sorted([1, 2, 3])).

Show example solution

def is_sorted(arr):
    # Is array sorted
    for i in range(len(arr) - 1):
        if arr[i] > arr[i + 1]:
            return False
    return True
print(is_sorted([1, 2, 3]))

Test yourself

What is the common property of NP problems?
- Solvable in polynomial time
- Solution verifiable in polynomial time
- No solution exists
- Only contains loops
Show answer

Solution verifiable in polynomial time — NP solutions are verifiable in polynomial time.

Sorted condition

if arr[i] > arr[i + ____]:

Show answer

if arr[i] > arr[i + 1]:

P and NP: match the terms

P

Solvable
NP

Verifiable
P=NP

Open question
polynomial

Fast

Next lesson: NP-complete

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies