Class p v.s. Class NP P stands for what? Polynomial! Class p: Problems solvable in deterministic polynomial time What about np? ☆ No Prob|em? 8 Not Polynomial (i.e. polynomial time unsolvable Nondeterministic Polynomial! Class Np: Problems solvable in nondeterministic polynomial time
Class P V.S. Class NP • P stands for what? Polynomial! • Class P: Problems solvable in deterministic polynomial time • What about NP? ❖ No Problem? ❖ Not Polynomial (i.e. polynomial time unsolvable)? Nondeterministic Polynomial ! • Class NP: Problems solvable in nondeterministic polynomial time 6
Deterministic/Nondeterministic Polynomial time? Where do these terms come from? They're based on different computation models Deterministic Turing Machine 4 Nondeterministic Turing Machine We will not talk about Turing Machine in this course Details of these computation models please refer to the following course A CSCI3130 (Formal Languages and Automata Theory)
Deterministic/Nondeterministic Polynomial time? • Where do these terms come from? • They’re based on different computation models ❖ Deterministic Turing Machine ❖ Nondeterministic Turing Machine • We will NOT talk about Turing Machine in this course • Details of these computation models, please refer to the following course ❖ CSCI3130 (Formal Languages and Automata Theory) 7