chap limits to computation exponential time problems toh problems -complete problems traveling salesman problems sorting figure our knowledge regarding the world of problems requiring exponential time or less some of these problems are solvable in polynomial time by non-deterministic computer of thesesome are known to be -completeand some are known to be solvable in polynomial time on regular computer howeverwhen we reduce known hard problem to candidate problem xthat means we are using as step to solve and if we know that is hardthat means must also be hard so crucial first step to getting this whole theory off the ground is finding one problem that is -hard the first proof that problem is -hard (and because it is in ptherefore -completewas done by stephen cook for this featcook won the first turing awardwhich is the closest computer science equivalent to the nobel prize the "grand-daddyn -complete problem that cook used is call satisfiability (or sat for shorta boolean expression includes boolean variables combined using the operators and (*)or (+)and not (to negate boolean variable we write xa literal is boolean variable or its negation clause is one or more literals or'ed together let be boolean expression over variables xn then we define conjunctive normal form (cnfto be boolean expression written as series of clauses that are and'ed together for examplee ( ( ( is in cnfand has three clauses now we can define the problem sat