FIT1045 Lecture Notes - Lecture 12: Np-Completeness, Lothar Collatz, Halting Problem
30 May 2018
School
Department
Course
Professor
WEEK12 - P Vs NP
Polynomial: a complexity if it can be bounded by O(N^k) where j is a
constant e.g. O(N^3)
Non-Polynomial: a complexity that cannot be bounded by O(N^k) e.g.
O(2^N) and O(N!) or O(N^N)
Intractable Problems
•If cannot be solved in polynomial time!
•I.e generating all subsets, generating permutations, Tower of Hanoi!
•Fibonacci numbers is NOT intractable!
◦Some algorithms!
◦Can be solved like sorting, finding minimum!
•There are problems that are still unsure if they are intractable or not!
◦Unable to prove that polynomial algorithm cannot exist!
Decision Problem: if a problem has only a yes or no output
Decidable example: did you have breakfast
Non decidable examples: what did you have for breakfast?
HAMILTONIAN CYCLE:
For a graph is a path(does not have the same vertex twice) that passes
through every vertices exactly once
Decision problem for Hamiltonian cycle:
Does there exist a Hamiltonian cycle in graph G
Vertex Cover
•Is a subset of vertices of a graph such that every edge in the graph
has at least one of its endpoints (vertices) in C!
Decision problem:
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Polynomial: a complexity if it can be bounded by o(n^k) where j is a constant e. g. o(n^3) Non-polynomial: a complexity that cannot be bounded by o(n^k) e. g. o(2^n) and o(n!) or o(n^n) I. e generating all subsets, generating permutations, tower of hanoi. Some algorithms: can be solved like sorting, finding minimum. There are problems that are still unsure if they are intractable or not: unable to prove that polynomial algorithm cannot exist. Decision problem: if a problem has only a yes or no output. For a graph is a path(does not have the same vertex twice) that passes through every vertices exactly once. Does there exist a hamiltonian cycle in graph g. Is a subset of vertices of a graph such that every edge in the graph has at least one of its endpoints (vertices) in c. Is there a vertex cover of k or less vertices of g. Subgraph where there is an edge between every two vertices.
