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
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 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
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