P and NP
- Algorithms course
- Expert
- Lesson 5/41
- 4 min
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.
Practice is_sorted function
Write is_sorted(arr). Return whether the array is sorted. Print True with print(is_sorted([1, 2, 3])).
Starter code
def is_sorted(arr):
# Is array sortedSample 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]))Expected output
True
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is the common property of NP problems?
- Solvable in polynomial time
- Solution verifiable in polynomial time Correct answer
- No solution exists
- Only contains loops
Explanation: NP solutions are verifiable in polynomial time.
2 Sorted condition
if arr[i] > arr[i + ____]:if arr[i] > arr[i + 1]:Explanation: 1 is right.
3 P and NP: match the terms
| Term | Meaning |
|---|---|
P |
Solvable |
NP |
Verifiable |
P=NP |
Open question |
polynomial |
Fast |