CS计算机代考程序代写 data structure algorithm COMP2521

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