COMP2521
Data Structures & Algorithms
Week 7.1
P, NP
1
In this lecture
Why?
We want to be able to generalise different categories of
algorithms to understand how feasible they are to solve
for a given problem.
What?
P
NP
NP-Complete
2
Solving vs Verifying
When it comes to problems we have to solve in computing, there are
two key ways we can look at the difficult of the problem:
Solving: How hard is it to find or guess the correct answer?
Verifying: Given an answer, how hard is it to verify if it is correct?
3 . 1
Solving vs Verifying
Problem to solve Solving Verifying
Sudoku Hard Easy
Hamiltonian Path Hard Easy
Euler Path Easy Easy
Traveling Salesman (H.P) Hard Easy
Spanning Tree Easy Easy
Sorting a list Easy O(n^2) Easy O(n)
Combination Lock Hard O(k^n) Easy O(n)
3 . 2
Hard problems
Problems that are hard to solve often take a ridiculous amount of
time to solve with standard computers we all use on this planet.
Most of these problems have time complexities of O(n!) or O(k^n) or
worse – essentially exponential-like problems that require extreme
amounts of time and processing to get the right answer for large
values of n.
These problems generally can’t be solved by large data sets.
3 . 3
Hard problems
These problems generally can’t be solved by large data sets by
standard computers. We describe the algorithms required to solve
hard problems as a non-deterministic polynomial time problem.
Problems that are easy we say is a polynomial time problem.
These problems can only be solved in a reasonable amount of time
by some theoretical computer (that doesn’t exist) that can simulate
many-to-all possibilities at the same time, or guess the correct
answer perfectly right away.
3 . 4
P v NP vs NP-Complete
Problems we solve can generally be described in one of some
categories of problems:
P: Polynomial
Can be solved in polynomial time
Can be verified in polynomial time
NP: Non-deterministic polynomial
Can be solved in non-deterministic polynomial time
Can be verified in polynomial time
NP-Complete:
Can be solved only in non-deterministic polynomial time
Can be verified in polynomial time
NP
P
NP-Complete
4
Polynomial Time
Polynomial time algorithms are typically in the form: n^x + …..
E.G. n, n^2, n^4, sqrt(n), log(n)
E.G. Breadth-first-search, binary search
Non-determinstic polynomial time algorithms are others:
E.G. n!, k^n
E.G. Hamiltonian Paths, combination locks
5
Feedback
6