New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Hertha Tremblay


Hertha Tremblay
GPA 3.59

James Arvo

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

James Arvo
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 61 page Class Notes was uploaded by Hertha Tremblay on Saturday September 12, 2015. The Class Notes belongs to CompSci 162 at University of California - Irvine taught by James Arvo in Fall. Since its upload, it has received 10 views. For similar materials see /class/201900/compsci-162-university-of-california-irvine in ComputerScienence at University of California - Irvine.

Similar to CompSci 162 at UCI

Popular in ComputerScienence


Reviews for FORMAL LANG & AUTM


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/12/15
Chapter 6 Grammars and Pushdown Automata In this chapter we will examine the concept of a grammar which is a very powerful tool for generating strings and thereby de ning languages The languages generated by most grammars go well beyond what is expressible via regular expressions We will begin by de ning a general grammar then examine several restricted forms of grammars contextfree and right lineari We will then describe a new type of automaton known as a pushdown automata that is intimately related to contextfree grammars in essentially the same manner that nite automata are related to regular expressions We will also see that contextfree languages that is languages generated by contextfree grammars all exhibit a fundamental pattern that is analogous to that exhibited by regular languages This will lead to a version of the pumping lemma for contextfree languages which can be used to show that a language is not contextfreer 61 Grammars A grammar is a practical and powerful mechanism for deriving or generating languages that is a mechanism for directly constructing the strings of a language just as regular expressions provide a mechanism to construct the strings of a regular language We begin with a formal settheoretic de nition of a grammar De nition 16 A grammar G is a 4 tuple EF7H where 1 E is a nite nonempty set called the terminal alphabet 2 F is a nite nonempty set called the the nonterminal alphabet 3i 7 is an element of F called the start symbol 77 78 CHAPTER 6 GRAMMARS AND PUSHDOWN AUTOMATA 4 H is a nite subset of E U lquotX o lquot o E U F X E U F known as the praductizms1 where the only additional constraint on these sets is that 2 N F 0 The elements of E are called terminals and the elements of F are called nonterminals Formally the elements of H are ordered pairs of strings 16 where both a and B may consist of terminals and nonterminals intermixed in any order the only restriction is that a must contain at least one non terminali This restriction on 1 makes the formal de nition above somewhat cumbersome requiring the concatenation of three sets of strings the middle one being 1quot Note that B is allowed to be 5 the empty string as it is simply an element of E U lquoti It is customary to denote a production 15 6 Has a A 5 61 Thus the productions of the grammar G mb 7 A73 7A A 1407 147 AaBL 37 abb 62 would be written as A A aAb aA A AaB B A abbi We say that a string 1 can be derived in one step from a string u according to the grammar G if and only if there exists a production a A B in H such that 1 occurs as a substring one or more times in u and replacing some occurrence of a in u by 6 results in the string vi In this case we then write u gt v or u gtG 1 when we wish to emphasize the grammar we are utilizingi For example it follows that abzaz gt abzzzaz 63 if the production I A 222 is in Hi Observe that only one I in the string abzaz is replaced by 222 The above derivation would also hold if either the production bra A bzzza or the production abzaz A abzzzaz were in Hi The symbol gt technically denotes a binary relation on 2 which is analogous to the b relation on DFA con gurations Moreover as with the yields relation of DFAs we extend the derives in one step77 relation to its re exive transitive closure which means derives in zero or more steps77 as follows 1 ifu gt 1 then u 3 1 Extension 2 if u gt u for all u E 2 Reflexivity 3i ifu gt v and v gt w then u 3 w Transitivity 1Productions are also frequently referred to as rewrite rules 61 GRAMMARS 79 De nition 17 The language L generated by a grammar G EF7H is the set of all strings in 2 that can be generated by G starting from the symbol 7 6 Fl That is G weE lywm Note carefully that the language generated by a grammar consists of strings of terminals only for any w E G w E 2 Thus nonterminal symbols are used only as intermediate symbols in the derivation of the nal strings they never appear in the nal strings As an example of a grammar let G1 2 12711 where E ab F S 7 S and H S aSa S bSb S a S b S Thus using the more intuitive notation for the productions the grammar G1 can be expressed as S A aSa S A bSb S A a S A b S A 5 where S is understood to be the start symboll Thus ababa E G1 because S gt aSa gt abSba gt ababal In fact G1 generates all strings in the language w E 2 l w 10R which is the set of all palindromes over 2 a palindrome is a word whose spelling is the same forwards and backwards like radar The above list of productions can be written more compactly as S A aSaleb S A alble where the vertical bar represents a choice of righthand sides In fact in this example we can fold all ve productions into a single line since there is only one nonterminal symboll A contextfree grammar is a grammar in which the lefthand side of each production is restricted to consist of a single nonterminall More formally the grammar G 1quot 711 is contextfree if and only if Hcrxaur in addition to meeting all the other constraints for general grammarsl In particular H must be nite 7 E F and 2 N F 0 An example of a contextfree grammar is S A AB A A aAb l 5 B A Bc l 5 which generates the language anbnck l n 2 0 h 2 0 Another example of a contextfree grammar is the one for palindromes given previously The term contextfree means that the string substi tutions are carried out independent of the context in which they are found In contrast a general grammar can include productions such as aAb A aBBb which replaces A with BB but only when the A has an a 0n the left and a b 0n the right that is only when the A is in the context aAbl 80 CHAPTER 6 GRAMMARS AND PUSHDOWNAUTOMATA We call a language contextfree if there exists some contextfree grammar that generates it We shall see that the contextfree languages are exactly the languages that are accepted by nondeterministic pushdown automatai Contextfree languages are extremely important as nearly all programming languages are contextfree that is the syntax of most programming languages can be completely described by a contextfree grammari A 7ight linear grammar is a contextfree grammar in which the righthand side of each production is restricted to consist of a string of terminals followed by zero or one nonterminali More formally the grammar G 2127 H is right linear if and only if HCI X 2 0FU5 in addition to meeting all the other constraints for contextfree grammarsi In particular the left hand side of every production consists of a single nonterminali An example ofa rightlinear grammar is S A aS l 5 S A A A A 12A l 5 which generates the language anbk l n 2 0 k 2 0 We call a language rightlinear if there exists some rightlinear grammar that generates it We have already encountered the class of rightlinear languages but by a different name as the next theorem shows Theorem 23 A language is right linear and only if it is regular Proof To be supplied D 62 The Pumping Lemma for ContextFree Languages Just as with regular languages contextfree languages possess symmetries that result from limita tions of the mechanisms that generate themi In the case of regular languages all suf ciently long strings would force the machine back into a state it had already Visited this leads to the rst pump ing property a distinguishing feature of all regular languagesi While contextfree languages are somewhat more complex than regular languages they also possess a similar property which we will call the second pumping property De nition 18 Let k be a natural number and let L be a language Then we shall say that w E L has the second pumping property of length k with respect to the language L if and only if there exist strings u v z y and 2 not necessarily in the language L such that w uvzyz lvzyl S k lvyl 21 and uvnzynz E L for all n 2 0 The second pumping property is somewhat more complicated than the rst pumping property but is directly analogousi Here instead of partitioning a string into three pieces we partition it into ve 63 CLOSURE PROPERTIES OF CON TEXT FREE LANGUAGES 81 pieces We constrain the middle three pieces to be no longer than k and we do not allow both the second and fourth pieces to be empty although one of them may be With this de nition we may now state the Second Pumping Lemma which is identical in form to the First Pumping Lemma Lemma 5 Second Pumping Lemma Let L be a contextfree language Then for some h E N every w E L with 2 It has the second pumping property of length h Proof See for example Kozen 15 page 148 D Example 1 The language L1 anbncn l n E N is not ContextFreer Let h E N be given Let w ambmcm where m h 1 Suppose that w uvzyz with lvzyl S h and lvyl 2 1 We will consider several possible cases Case I If either 1 or y contains two distinct symbols then the string uv21y22 will contain an a that is preceded by a b or a b that is preceded by a c neither of these can occur in any of the strings of Lli Case II If both 1 and y consist of a single possibly repeated letter then the string uv21y22 will be apchf where p q and r are not all equal this is another pattern that does not occur in the strings of Lli Therefore in either case the string uv21y22 fails to be in L1 so w does not have the second pumping property of length hi Since h was arbitrary we conclude that L1 is not contextfreer D Example 2 The language L2 a l n E N n is prime is not contextfreer Proving this is almost identical to the proof that L2 is not regular Let h E N be given and let w up w ere p is prime and p 2 i w uvzyz with lvyl 21t en luvnzynzl lzyzuvl n7 1 w 10 n Um where m We must now show that for some n E N p n 7 lm is not prime from which it follows that uvnzynz g Lgi Letting n p l the proof follows exactly as it did in showing that anbn is nonregular We have luvnzynzl 10an pm I But since both p and m 1 are greater than 1 pm l is a composite numberi Therefore for any h E N and any partition w uvzyz where w 6 L2 2 0 and lvyl gt 0 we can nd an n such that uvnzynz g Lgi Therefore L2 is not contextfreer D 63 Closure Properties of ContextFree Languages Previously we showed that regular languages are closed under all the common set operations We shall now show that contextfree languages are also closed under certain set operations but not all of themi 82 CHAPTER 6 GRAMMARS AND PUSHDOWNAUTOMATA Theorem 24 ContextFree languages are closed under union concatenation and Kleene star Proof Closure under union and concatenation can be easily demonstrated by combining two contextfree grammars to obtain a new contextfree grammari Let L1 and L2 be arbitrary context free languages over the same alphabet 2 Then there exist two contextfree grammars G1 27 F17 717 H1 G2 27 F27 727 H2 that generate L1 and L2 respectively Without loss of generality let us assume that Fl rg 0 since we can always relabel the nonterminals of a grammar without changing the language it generates Now let 5 denote some symbol that is not in F1 or F2 and de ne the three following grammars G3 EF1UF2USSH1UH2USgt71Sgt72 G4 EFlUF2USSH1UH2US7172 G5 ET 1USSH1USgt571Sgt8 It is easy to see that G3 G4 and G5 are all contextfree as the only new productions are of the correct form ie they all have exactly one nonterminal on the left Furthermore it is also easy to see that ass L1UL2 G4 LloLg Gs L01 consequently these languages are contextfree since there is a contextfree grammar that generates themi It follows that contextfree languages are closed under all three of these operations D However unlike regular languages contextfree languages are not closed under all of the typical set operations In particular both 39 quot and 39 of t t f languages can result in languages that are notcontext freer Theorem 25 ContextFree languages are not closed under intersection or complementation Proof That contextfree languages are not closed under intersection follows easily by observing that both L1 anbnck l n 2 0 k 2 0 and L2 akbncn l n 2 0 k 2 0 are context free However the language L1 Lg anbncn l n 2 0 is not context freer That contextfree languages are not closed under complementation now follows from the fact that Lng ELM Thus if contextfree languages were closed under complementation they would also be closed under intersection which we have just shown is not the case B 64 PUSHDOWN AUTOMATA 83 input tape read head finite control unit reject indicator accept indicator stack marker Figure 61 Conceptually apushdoum automaton FDA is very similar to a nite automaton the di erence is that it is also equipped with an in nite capacity stack At each transition the machine uses the current state the symbol under the read head and the symbol on top of the stack to determine its next action Each transition optionally moves the read head one cell to the right pops the top symbol from the stack and pushes zero or more symbols back onto the stack 64 Pushdown Automata As With DFAs and NFAs the machine reads the symbols of a string Which we imagine to be printed on a tape that extends from left to right beginning in its initial states The difference is that the Pushdown Automaton also pops symbols from its stack at each step and these symbols in uence the action of the machine Moreover the machine may push any nite number of symbols onto the stack at each step To summarize When the machines starts 1 The current state is 40 2 The read head is positioned over the leftmost rst symbol of the string on the tape 3 The symbol 7 is the only symbol on the stack Each transition of the machine is determined by l The current state 2 The symbol currently under the read head this is optional 3 The symbol currently on top of the stack 84 CHAPTER 6 GRAMMARS AND PUSHDOWNAUTOMATA At each transition the following changes occur 1 The machine is put into a new state possibly the same as before 2 The read head either stays xed or moves exactly one cell to the right 3 The top symbol is removed iiei popped from the stack 4 A string of zero or more symbols is added iiei pushed onto the stack This process continues until one of two events occurs 1 The last symbol on the tape has been read and there are no more null transitions to followi 2 An unde ned transition is encountered After reading the last symbol on the tape the read head is positioned over the blank symbol just past the end of the string When an unde ned transition is encountered the string is rejected by de nition which is the same policy used in NFAsi De nition 19 A Pushdown Automaton PDA is formally speci ed by the 6tuple E F 7 Q 40 A A where most of the elements retain the meanings they were given in the context of nite automata 1 E is a nite nonempty set called the input alphabet to i F is a nite nonempty set called the stack alphabet 9 7 is the stack marker g i Q is a nite nonempty set of states 5 go is the state of the machine before reading each string or the initial state 6 A Q Q is a special set of states called the accept states and 7 A is the transition relation which is a nite subset of X E U X F X X Fquot where 5 in this context denotes the null symbo i The ordered pairs p a s q in A determine the new state to move to and the symbols to push onto the stac as a function of the current state the current symbol being read and the symbol on the top of the stack The tape symbol may also be substituted by a which indicates that no symbol is read and the read head remains xed Let M denote the machine 271quot QqoA A and let w E 2 be some string We shall use the notation SM to denote the set of states reachable by machine M after reading string w which is 2Here we have retained the structure of the Cartesian product rather than denoting the elements of A as Setuples ie as in NFAs where we denoted the elements of A by Setuples This is nothing more than a stylistic choice 64 PUSHDOWN AUTOMATA 85 Figure 62 This is a deterministic PDA that accepts the language aquotbquot l n 2 O The stack marker is J9 and E is the empty string Note that state 13 will be entered for all strings anbk where k 2 71 however if k gt n then the machine will reject while in state 13 since there are no transitions de ned for that case consistent with our previous usage of this notation As before if SM N A Z we say that the machine accepts or recognizes the string w The set of all recognized strings constitutes a language associated with M More precisely we de ne M 12 w e 2 sMaJ nA y 0 64 to be the language accepted or recognized by the machine M In keeping with previous terminology we will call a language FDAacceptable if and only if there exists some PDA that accepts it 641 State Diagrams As with NFAs and DFAs PDAs both deterministic and nondeterministic have an obvious repre sentation in terms of a state diagram We retain all of the same conventions as with DFAs regarding the representation of states transitions and designating the start state and accept states The only difference is how we label the arrows of the diagram In the state diagram of a PDA the transi tion 10 a s qw is denoted by an arrow from state p to state 4 bearing the label a s w This transition means that when the machine is in state p the read head is over the symbol a and s is on top of the stack then the machine is put into state 4 the read head moves to the right by one cell the s is popped off the stack and the string w is pushed onto the stack so that its rst symbol appears on top of the stack ie the last symbol of the string is pushed rst There is no explicit representation of the stack the operation of the stack is implicit in the de nition of a PDA and the sequence of transitions followed completely determines the stack contents at all times We also allow transitions of the form 10 53 qw in which no symbol is read from the tape and the read head does not move Note that exactly one symbol is always popped from the stack Figure 62 depicts a state diagram for a PDA that accepts the language anbn l n 2 0 Here the tape and stack alphabets both contain the letters a and I he machine pushes a s onto the stack to remember how many it encountered If it then reads a string of bls it can compare the number of bls to the number of as by popping an a from the stack for each I that is read When exactly as many bls have been read as as the stack marker will be on the top of the stack and the machine can enter state 43 If there are still more symbols on the tape the machine will reject since there are no transitions leaving state 43 Observe that the stack alphabet could be replaced with any two distinct symbols plus the stack marker without changing the language that is accepted 86 CHAPTER 6 GRAMMARS AND PUSHDOWN AUTOMATA aa bb 61 b ba aaaa b bbb Figure 63 This is a nondeterministic PDA that accepts the language 11 6 ab w a bulb The machine is nondeterministic because of the E 53 E transition out of state ql which could always be chosen instead of b 53 17 or a 53 a Several of the arrows are marked with sets of labels as a notational convenience This language can also be recognized by a deterministic PDA 642 Con gurations and the Yields Relation 643 Deterministic Pushdown Automata A PDA is deterministic if two conditions hold First7 there cannot be multiple transitions that begin with the same Stuple That is7 there cannot be two distinct elements 1t77a737 41101 and p7 a7 s7 12 102 in the transition relation A This clearly leads to a nondeterministic choice when the machine is in state p reading a7 with s on top of the stack However7 there is also another condition that leads to nondeterminism if there is a transition of the form 1t77a737 41101 and also of the form 1788 42102 in the relation A In this case7 the leading Stuples are in fact different7 but still lead to a nondeterministic choice7 as the symbol a may or may not be read from the tape Thus7 in a deterministic PDA7 where there is an epsilon transition leading out of state 417 there can be no other transitions out of L that pop the same symbol The machine shown in Figure 62 is deterministic7 and the machine shown in Figure 63 is nondeterministic since any transition of the form a a or b b while in state ql could also trigger the transition 8 5 thus7 it is a nondeterministic choice Unless otherwise stated7 when we will assume that a PDA is nondeterministic If the distinction is important7 we will refer to a deterministic PDA as a DPDA7 and a nondeterministic PDA as an NPDA Note that all PDAs7 deterministic or not7 have their transitions encoded as a A relation rather than a function this is simply a matter of convention7 since most PDAs are nondeterministic anyway 65 CONTEXT FREE LANGUAGES AND PDA S 87 65 ContextFree Languages and PDA s Theorem 26 A language is contextfree and only if it is accepted by some nondeterministic pushdown automaton Proof To be supplied D 66 An Intersection Theorem for ContextFree Languages Although we have shown that contextfree languages are not closed under intersection it is possible to impose a constraint on one of the languages so that the intersection does remain contextfreer The following theorem can be useful in proving that a given language is contextfreer Theorem 27 The intersection of a contextfree language and a regular language is contextfree Proof Let M1 and M2 be a PDA and a DFA respectively over the same alphabetl In terms of tuples we shall denote them as M1 27F7Q1741777A17A1 M2 27Q27427A2752 We will show how to construct another machine M3 which is also a PDA that accepts M1 M2l First denote the components of M3 by M3 27 F7 Q37 437 77143 As The strategy is to create a PDA that behaves exactly the same way as M1 with respect to reading the tape and managing the stack but simultaneously keeps track of how the DFA M2 would behave given the same inputl Thus each state of the new machine will record two things the state of the original PDA M1 and the state of the NFA M2 which we imagine to be running in lockstep with M1 ilel reading the same symbols from the tape at the same time To do this we introduce many more states into M3 in particular the new machine will have states corresponding to the Cartesian product of Q1 and Q2 that is Q3 Q1 gtlt le Given this strategy it is relatively straightforward to de ne the transition relation A3 of Mg We need only two ru es H For each 10 a s qw 6 A1 and each 7 6 Q2 add Pyaysb ll710 t0 A37 where 101070731101 4 47520700 For each p5s qw 6 A1 and each 7 6 Q2 add 14878 710 to A3 where p 1M and q LN E0 88 CHAPTER 6 GRAMMARS AND PUSHDOWNAUTOMATA To complete the de nition of M3 we let qg 41 L12 and A3 A1 gtlt Agi Now if we look at the rst coordinate of the states visited by M3 while processing a string they exactly match what M1 would do Similarly if we look at the second coordinate of the states visited while processing a string they match what M2 would do except for possibly the addition of one or more null transitionsi Finally we observe that a string would be accepted by both M1 and M2 if and only if M3 is left in a state that is in A1 gtlt A2 which consists of both an accept state of M1 and an accept state of Mg D 67 Exercises H E0 9 F 5 533 Given the set of terminals 2 a 1 construct a contextfree grammar for each of the following languages You need only list the productions provided that you adhere to the convention that uppercase letters are nonterminals lowercase letters are terminals and S is the start symbol a L1 b ab ab That is all strings in 2 with exactly two as b L2 anbkubkan l n 212 21u E 2 c L3 ambk l m 2 2k For each of the following nonregular languages over the alphabet E a b 0 de ne a PDA that accepts themi You need only show the state diagram for each machine a anbkcn c l n 2 0i 2 0 b anbnk52k l n 2 0i 2 0 c anbk l n f 16 Let L be the language anb2n l n 2 0 a Give a contextfree grammar that generates L b Give the state diagram of a deterministic PDA that accepts the language L Show that for any regular language there exists a deterministic PDA that accepts it Use the pumping lemma for contextfree languages to show that the following languages are not contextfreer a anbna2n l n 2 0 b a l n is a power of two Demonstrate that a PDA with a nite stack is equivalent to an NFAi That is for any given PDA and constant k the collection of all strings that are accepted by the PDA without ever exceeding k symbols on the stack including the stack marker de nes a new language that is a subset of the original language that is we now reject any string that causes the nite stack to over ow at any point Show that this new language is regular for any i 6 7 EXERCISES 7 00 89 Show that the class of contextfree languages over a terminal alphabet E with exactly one symbol is regulari Consider a modi ed PDA that has two stacksi At each transition it pops both stacks and pushes possibly different strings back onto both stacksi The new state is determined by the current state the symbol under the read head and the symbols at the top of both stacksi Diagrammatically a transition would be labeled like this a b c u v where a is on the tape 12 is on stack 1 c is on stack 2 and u and 1 get pushed onto stacks 1 and 2 respectively In all other respects this modi ed PDA behaves like a lstack PDAi Discuss the languages accepted by such a machine Can it accept languages that are not contextfree Justify your answer Bibliography 1 Wilhelm Ackermanni On Hilbert7s construction of the real numbers ln 1 van Heijenoort E ET E E E editor From Frege to Co39del A Source Book in Mathematical Logic 187971931 pages 4937507 Harvard University Press Cambridge Massachusetts 1967 Alfred Vi Aho John E Hopcroft and Jeffrey Di Ullmani The Design and Analysis of Computer Algorithms AddisonWesley Reading Massachusetts 1974 Rudolf Carnapi Introduction to Symbolic Logic and its Applications Dover Publications New York 1958 Stephen A Cook The p of p ACM Symposium on the Theory of Computing vo 1 In Proceedings of the Annual lume 3 pages 1517158 Ohio May 1971 Thomas Hi Cormen Charles E Leiserson and Ronald L Rivesti Introduction to Algorithms McGrawHill New York 1990 Martin Di Davis Ron Sigal and Elaine Ji Weyukeri Computability Complexity and Languages Fundamentals of Theoretical Computer Science Academic Press New York second edition 1994 Michael 1 Fischer and Michael Oi Rabini Superexponential complexity of Presburger arith metici In Proceedings of the SIAMAMS Symposium in Applied Mathematics volume 7 pages 2741 1974 Michael R Garey and David S Johnson Computers and Intractability A Guide to the Theory of NP Completenessi W1 Hi Freeeman and Company San Francisco 1979 9 Paul R Halmos Naive Set Theory SpringerVerlag New York 1998 10 Fred Henniei Introduction to Computability AddisonWesley Reading Massachusetts 1977 11 John Mi Howie Automata and Languages Oxford University Press New York 1991 12 Richard Mi Karpi Reducibility among combinatorial problems In Ri E Miller and 1 W1 Thatcher editors Complexity of Computer Computations pages 8571031 Plenum Press New York 1972 13 Stephen C Kleenei Origins of recursive function theory In 20th Annual Symposium on the Foundations of Computer Science pages 3717382 San Juan Puerto Rico October 1979 173 Chapter 9 The Theory of NPCompleteness The birth of the theory of NPCompleteness is usually identi ed with the publication of an important theorem by Stephen Cook in 1971 In this section we will examine some of the fundamental ideas of the theory of NPCompleteness including Cook7s fundamental theoremi Cook7s theorem has been re expressed and re proven in many forms since 1971 the proof provided in these notes is most similar to that given by Aho Hopcroft and Ullman 91 Introduction Let7s begin by posing a question that we already know the answer to it will be a short step from there to posing a much more interesting question Question 1 If there exists a nondeterministic Turing machine that can decide a language L is there also a deterministic Turing machine that can decide 9 The answer to question 1 is yes since we have already determined that a deterministic Turing machine can compute anything that a nondeterministic machine can compute However this says nothing about the time it takes to carry out the computation When time is taken into consideration the question becomes much more difficult to answer As we shall see by placing time constraints on Turing machine computations the class of Turing decidable languages splits into numerous subsets with important properties one of the most important being the set know as NPCompletei The theory of NPCompleteness deals with a particular class of problems that are seemingly in tractable that is a class of problems that clearly can be solved algorithmically yet for which there are no known reasonable or ef cient algorithms By reasonable in this context we mean al gorithms that run in polynomial timel algorithms that do not fall into this category rapidly become mmtion that can be solved by a Turing machine in at most pn steps where p is some polynomial and n is the length of the input string Here the polynomial is xed for all input strings but may depend on the language 123 124 CHAPTER 9 THE THEORY OF NP COMPLETENESS useless as the size of the problem instances grow to even modest sizei While there are many problems that can be proven to require exponential time and therefore do not t our de nition of reasonable there are others for which no such proof has ever been constructed nor have any polynomialtime algorithms been discovered The class NP contains many such decision pro Nondeterminism does not make a Turing machine any more powerful in one respect it does not allow it to decide any languages that would be otherwise undecidablei However the situation appears to be quite different with respect to timecomplexity that is nondeterminism may indeed have a profound effect on the power of a Turing machine when the number of steps to perform a computation is limited in certain ways As yet however this is not a proven fact The open question ist is Question 2 If there exists a nondeterministic Turing machine that can decide a language L in polynomial time is there also a deterministic Turing machine that can decide L in polynomial time Note that question 2 differs from question 1 only by the inclusion of the underlined text This question can be expressed more succinctly as follows Question 3 Is it the case that P NP This is the most tantalizing open question in computer science While there is almost universal agreement that the answer is very likely no until it is proven there will be a shadow of doubt The widespread feeling that P NP is the result of an evergrowing catalog of problems in NP for which nobody has been able to invent a polynomialtime algorithm despite massive effort and immense economic incentives Moreover these problems are all connected in a very intriguing way rst noticed by Stephen Cooki lnformally Cook discovered that Theorem 43 Informal Statement of Cook s Theorem Among all the languages in the class NP the language CNF SAT is the hardest to decide By hardest we mean the highest 1 39 time A 39 to within 1 T with a poly nomial In particular Cook showed that if we could come up with a polynomialtime algorithm for determining the satis ability of boolean formulas in CNF form ie if CNF SAT E P then we could solve all decision problems in NP in polynomial time In other words P NPi We will now develop the machinery necessary to prove this formally and investigate a few of the many profound consequences of this fact 92 PolynomialTime Reductions De nition 27 Let L1 and L2 be languages over the alphabets El and 22 respectively We de ne the relation L1 5 L2 to mean that there exists a polynomialtime algorithm for computing a function f Eli A 2 where w 6 L1 if and only if 6 L2 93 NP COMPLETENESS 125 If L1 SP L2 holds we say that L1 is polynomialtime manytoone reduciblez or simply reducible when the rest is clear from context to L2 lntuitively this means that L2 is at least as di cult to decide as L1 or that L1 is no more di cult to decide than L2 modulo a polynomial3 The symbol S is very appropriate for this relation as it connotes an ordering in terms of dif culty Moreover the relation S5 is oth re exive and transitive and is exactly analogous to the Sm relation we studied in the context of undecidable languages The importance of this relation is made evident by the following theorem which is trivial to prove Theorem 44 Let L1 and L2 be languages If L2 6 P then L1 5 L2 implies that L1 6 P Stated informally if L2 is easy77 and L1 is no more dif cult than L2 then L1 is also easy77 The proof of theorem 44 follows immediately from the fact that the composition of any two polynomials is again a polynomial that is polynomials are closed under compositioni 93 NPCompleteness We begin by formally defining the class of languages known as NPComplete and observing some important properties of the languages in this set We shall also prove that this set is not empty which will require a rather elaborate proof De nition 28 Let class NPcomplete consists of those languages in NP to which every language in NP is reducible in polynomial time That is L E NPcomplete if and only if L 5 L for all L 6 NR Thus NPcomplete consists of the very hardest77 problems in NP in the sense that if a polynomial time algorithm could be found for any language in NPcomplete then every language in NP would be decidable in polynomial time We will frequently say that language L is NPcomplete77 or that decision problem P is NPcomplete77 rather than saying that they are elements of this set Theorem 45 Let L E NPcomplete and L E NP be two languages such that L S L Then L E NPcomplete 2The modi er manyetoeone simply emphasizes the fact that the function needn7t be and is generally not injective ie oneetoeone In theory the function f need only have a range consisting of two distinct strings one that is in L2 and one that is not Then f could map all the strings that are in L1 to the single string that is in L2 and all the strings that are not in L1 to the single string that is not in L2 This would ful ll the requirement of the function f In practice however we generally make use of in nitely many problem instances in L2 whether or not the function f ends up being injective is immaterial 3In the context of NPecompleteness polynomials are routinely ignored For example an algorithm that runs in 0n5 time is not distinguished from an algorithm that runs in On time While this difference is generally very signi cant in practice we shall be concerned here with a much more drastic distinction polynomial VS nonepolynomial As composition with an arbitrary polynomial does not remove this distinction we are justi ed in completely ignoring any such composition ie one polynomial being composed with or fed into another This is what we mean by modulo a polynomial 126 CHAPTER 9 THE THEORY OF NP COMPLETENESS Proof This follows from the transitivity of the 5 relation Let L E NPcomplete and suppose that L 5 L where L E NPi Then for all L E NP P P L m L m L which implies that L SP L by transitivityi Therefore L E NPcompletei D Thus given a single element of NPcomplete we can establish that other languages are also NPcomplete using polynomialtime reductions However at this point we have not yet shown that anything at all is in NPcompletei The rst such result was established by Stephen Cook in 1971 We can now give a precise and succinct statement of Cooks s theoremi Theorem 46 Cook 1971 CNF SAT E NPcomplete Proof We will show that if there is a nondeterministic Turing machine M that decides a language L then for each w E 2 we can construct a boolean expression in CNF form that is satis able if and only if w 6 Li Moreover we shall show that this construction can be carried out in polynomial time as a function of the length of the input string The upshot of this construction is that determining membership in L is no harder than determining satis ability of CNF formulas modulo a polynomial that is ignoring the polynomial cost of creating the CNF formula from the nondeterministic Turing machine and any polynomial increase in the complexity of determining the satis ability of the CNF formula versus running the Turing machine In general we shall consider any such polynomial costs to be inconsequential even though in practice such costs could be quite substantial Let M be a nondeterministic Turing machine that decides the language L C 2 in polynomial time We will show that L 5 CNF SATi It will then follow that CNF SAT E NPcomplete since there exists such a machine for every language in NP and hence every language in NP reduces to CNF SATi The essence of the proof is to show that a boolean formula can be constructed in polynomial time directly from the de nition of the Turing machine M and the input string w that is satis able if and only if w E Moreover we will show that such a formula can be constructed in CNF formi Let p denote the worstcase timecomplexity function of M that is p is a polynomial such that M will always halt within pn steps on input strings of length n The boolean formula 7 that we will construct must admit a satisfying truth assignment if and only if there is a sequence of valid con gurations that the nondeterministic machine M can follow given input w that leads to an accept state after at most pn steps where n We rst examine how a satisfying truth assignment of f can encode a legal sequence of con gurations of the machine M run on wi Let t denote time by which we mean a count of the discrete steps of M with the initial con guration corresponding to t 0 Then we must enforce the following properties to faithfully simulate the behavior of M as it is run on input w 1 The readwrite head of M is over exactly one cell at any time ti 2 The machine M is in exactly one state 4 at any time ti 3 Each cell of the tape has exactly one symbol in it at every time t 93 NP COMPLETENESS 127 F The machine starts in the initial state with readwrite head over the leftmost cell which is cell 1 and with w written at the start of an otherwise blank lled tape 5 Only the symbol under the readwrite head at time t can change at time t ll 6 The state position of the head and symbol being scanned at time t determine the state position of the head and symbol last written at time t 1 according to the transition relation AofMi An essential ingredient that enables us to model all of these properties with a nite in fact polyno mially bounded boolean formula is the fact that the machine must halt after pn steps therefore the machine can access at most pn cells of its taper To simplify the construction we rst e ne a function f TJn A TJ such that fzli 1n is T if and only if exactly one of its arguments is Ti The function f is easy to construct Amway 9 1 1 k fzluizk if z i1 The rst bracketed expression on the right of Equation 91 ensures that at least one of the argu ments is T while the second bracketed expression ensures that at most one argument is T since no two arguments can be true Observe that f is in CNF form and that its size ie the number of literals and clauses is 0062 where k is the number of arguments Without loss of generality we shall assume that M has tape alphabet F 0 l i i i 7 with 0 being the blank symbol and states Q 1 2 i i i q with 1 being the initial state and 4 being the single accept statei Furthermore we shall modify M so that it remains in its accept state forever once it accepts that is we will add transitions that keep M in state 4 once it has reached that state We now introduce a large number of boolean variables that will allow us to enforce all of the properties enumerated above during the entire operation of the machine which will entail up to pn stepsi Let m pn and de ne the m2 l 7 mq boolean variables for t0uim iluim 92 t 7 Sj for t70uim 71Hiq 93 Oil for t0uim iluim 31Hi7 94 which we shall interpret as follows T if and only if the readwrite head of M is over cell i at time t S T if and on y if M is in statej at time t and it T if and only if cell 239 contains the 128 CHAPTER 9 THE THEORY OF NP COMPLETENESS symbol 8 at time t We now de ne the following boolean formulas using only these variables EH fHLH wHi 9 5 Es 3 fSLS m755 96 10 Ec fltOZ170Z27wC gt 97 10 11 E1 59 AHfA 02w A 0 10 98 11 jn1 m1 7 EW V H v 0c v og A H v ogk v 013 99 10 i1 160 ET Hg A 0 A s Ami A egg A 551 910 1011 paqb6eA EA m 3 911 where A is the transition relation of Mr Expression 95 ensures that the readwrite head is positioned over exactly one cell at each time 1 expression 96 ensures that the machine is in exactly one state at each time 1 expression 97 ensures that each cell on the tape contains exactly one symbol expression 98 ensures that the machine starts in the initial con guration with w on its tape expression 99 ensures that only the symbol under the read head can change at each time step expression 9 10 ensures that each time step corresponds to some transition in the transition relation of M where left and righ 77 are encoded by 6 1 and 6 1 respectively and nally expression 9 11 ensures that the accept state is eventually reachedi Observe that the innermost bracketed expression in Equation 99 is equivalent to V1 i mV0 t m7131 kgy Hv0k ngly 912 That is at each cell i and time 1 either the readwrite head is over that cell or the symbol in the cell remains unchanged from time t to time 1 1 Thus the boolean formula f EHAESAECAEWAETAEIAEA 913 is satis able if and only if the machine M has a sequence of valid con gurations leading to an accept state given input w that is if and only if w E Note that nondeterministic branches of M pose no problem here they simply lead to multiple truth assignments that model valid computations of the machine All the subexpressions are already in CNF form except for equations 99 and 910 for the latter cases it is only the expressions in the braces that remain to be put into CNF formi We needn t convert these explicitly however since both of these expressions depend only on the speci cs of M ie the tape alphabet and transition relation and therefore do not depend on the size of the input wi Consequently we need only observe that any boolean formula can be converted into CNF form and that doing so here will result in CNF formulas of xed size determined by Mr 93 NP COMPLETENESS 129 All that remains is to determine the total size of the expression 913 since the time required to construct this formula is clearly proportional to its size as there is no searching of any kind involved in its construction from Mr Expressions 96 and 98 are linear in m while expressions 9 5 9 7 9 9 and 910 are quadratic in mi Thus the entire formula is 0p2lwl which is clearly polynomial in the size of the input wi We have demonstrated that L 5 CNF SATi Since we have previously shown that CNF SAT is in fact in NP we have established that CNF SAT is NPcomplete D Many important languages with practical applications are NPcompletei We will typically talk about these languages in the guise of their equivalent decision problems since the decision problems seem more natural and are closer to actual applications It should be understood however that each class of decision problems that we describe is technically a language 1 SATISFIABILITY Given a boolean formula 7 determine whether 7 is satis ablei 2i SCNF SAT Given a boolean formula 7 in conjunctive normal form CNF that has exactly three literals per clause determine whether 7 is satis ablei 3i 3 COLOR Given a graph G determine whether G can be 3 coloredi That is given an undi rected graph G determine whether there is a way to assign one of three colors to each vertex in such a way that no two adjacent vertices have the same color 4 PLANAR S COLOR Given a planar graph G determine whether G can be 3coloredi This is the same as the previous problem but with the extra constraint that it must be possible to draw the graph in such a way that no edges cross 5 VERTEX COVER Given a graph G V E and k E N determine whether there exists a subset of vertices V C V such that lV l S k and each edge in E is incident upon some vertex in V i We think of the subset V as covering the edges of Gr 6 CLIQUE Given a graph G and k E N determine whether G has a subgraph of size k or larger that is a cliquei 7i HAMILTONIAN CIRCUIT Given a graph G determine whether G has a Hamiltonian circuit that is a circuit cycle that passes through each vertex exactly once 8 PARTITION Given a list of natural numbers a1 a2 i i an determine whether the list can be split into two sublists that have the same sumi 9i SUBSET SUM Given a list of natural numbers a1 a2 i i an and k E K determine whether there is a sublist that sums to ki 10 SUBGRAPH ISOMORPHISM Given two graphs G1 and G2 and k E N determine whether there exist subgraphs G l Q G and C Q G such that G3 and G are isomorphic and have at least k verticesi 11 TRAVELING SALESMAN Given a function d 12 l i in A N and k E N determine whether there is a permutation p1p2i pn of 12 l i such that ELI dpipi1 S k where we def de ne pn1 pli We think of the numbers 1 2 i i i n as cities and dij as the distance from city 239 to city ji We call the permutation a tour of the cities 130 12 H 9 H H H 01 H 533 H 7 H 00 H 50 to O CHAPTER 9 THE THEORY OF NP COMPLETENESS EUCLIDEAN TRAVELING SALESMAN Given a nite set of 2D integer coordinates C C N x N and k E N determine whether there is a simple circuit connecting all the points whose total Euclidean length is less than or equal to k This is simply TRAVELING SALESMAN where the distance function dij is constrained to be the standard Euclidean distance between two points dP7Q l ltPVQEgt2ltPyergt2l where P P75 Py and Q Q75 Qy are elements of N2 NESFRE NonEquivalence of StarFree Regular Expressions Given two regular expressions R1 and R2 neither containing the Kleene star symbol determine whether there exists a string that is generated by one but not the other In other words determine whether R1 and R2 are nonequivalent NERE NonEquivalence of Regular Expressions Given two regular expressions R1 and R2 determine whether there exists a string that is generated by one but not the other In other words determine whether R1 and R2 are nonequivalent EXACT S COVER Given a nite set S and a nite collection C C 25 of subsets of 5 each consisting of exactly three elements determine whether C contains an exact cover of S that is a collection of disjoint sets whose union is S KNAPSACK Given 5 w1v1w2v2wnvn C N2 and WV E N determine whether there is a subset Squot C S such that 2004065 w S W and 290 65 v 2 V We think of the set S as a collection of items with given weights and Valuesl e wish to stuff items whose combined value is at least V into a knapsack that can hold at most a weight of W BIN PACKING Given 5 3132sn E N and 1612 6 N determine whether there is a partition of S into k disjoint subsets such that the sum of the numbers in each subset is less than or equal to b GEOMETRIC SEPARATION Given a collection of simple nonoverlapping orthogonal polygons in the plane P1 P2 P7 and an integer k determ1ne whether polygon P1 can be separated from the others by a sequence of k or fewer vertical or horizontal translations applied to any of the polygons in such a way that the shapes never overlap ART GALLERY Given a simple polygon P in the plane with n vertices and k E N determine whether the edges of P can be guarded by k or fewer of the vertices We think of the polygon as the oor plan of an art gallery The guards must be able to see every inch of every wall to watch over the paintings Each guard is assumed to be able to view 360 degrees INTEGER PROGRAMMING Given bc e N and A e NWk that is A is an n x k matrix of integers determine whether there exists an x E N such that C x 2 0 and Ax S b According to de nition 28 a language is NPcomplete if it is in NP and every other language in NP can be reduced to it in polynomial time Although Cook7s theorem theorem 46 requires a very direct and tedious proof that CNF SAT possesses these properties thanks to theorem 45 we needn t go to all that trouble every time we wish to show that some other language is NPcomplete To prove that some language L is NPcomplete we need only establish two things that L E NP 93 NP COMPLETENESS 131 and that L SP L for some language L that is already known to be NPcompletei In practice we typically proceed in three distinct steps to prove that a given language L is NPcomplete 1 Show that L E NPi 2 Show that L can be reduced to L for some L E NPcompletei 3 Show that the reduction can be performed in polynomial time Very frequently steps 1 and 3 are easy in fact usually trivial while step 2 is extremely challenging requiring some creativityi Finding an actual reduction requires us to rephrase one language the one that is already known to be NPcomplete using only the vocabulary of another language the one we wish to prove is NPcomplete Figure 91 shows how we will establish the NPCompleteness of a few important problems Once a language is shown to be NPcomplete we can then use it as a tool for showing that other languages are NPcompletei You can see how we will use this strategy in Figure 9ili To show that a problem is in NP we must show that some nondeterministic Turing machine can solve it in polynomial time By solve we mean decide iiei answer yes or no so this definition of NP can only apply directly to decision problems As we will see the implications extend well beyond decision problems however We typically proceed in three steps using the concept of an easily verifiable certi cate as described earlier 1 Describe how to phrase a succinct proof that a given yes answer is correct 2 Show that no such proof can exist for a no answer 3 Show that such a proof can be verified or rejected in polynomial time For example given a boolean formula in CNF SAT a succinct proof that it belongs to this language is simply a satisfying truth assignmenti No such truth assignment can exist for an unsatisfiable boolean formula and the validity of the truth assignment is very easy to check 7 we simply plug in the values and verify that they satisfy the formula which can be done in linear time We now provide detailed NPCompleteness proofs for an assortment of wellknown decision prob lems Each proof will be structured according to the three steps outlined above although steps 1 and 3 will often be treated in a very cursory fashion if they are very obvious Things to keep in mind reductions do not solve the original problem they merely translate the question from one vocabulary into another that is they map one problem instance into another problem instance without regard to whether the answer to the original instance is yes or nor 1 in your reduction you appeal in any way to the solution of the original problem eg the satisfying truth assignment of a SCNF SAT instance or the subsets in a PARTITION instance then you have made a fundamental error Your reduction is invalid since that information is unavailable within the polynomial time budget that the reduction must adhere to The set of all problem instances generated by the reduction need not be typical in any obvi ous sense within the language being reduced to For example the reduction of SCNF SAT to 132 CHAPTER 9 THE THEORY OF NP COMPLETENESS INTEGER PROGRAMMING See section 109 generates instances with numerical entries consisting of only 07 17 and 17 despite the fact that an integer program can accommodate arbitrary integers within the matrices and vectors What this tells us is that even problem instances with very re stricted numerical entries are already sufficiently hard to solve that we needn t use the full power of integer programming to solve satis ability problems 94 Straightforward PolynomialTime Reductions We will assume that the following languages have already been shown to be in NP complete PARTITION7 3COLOR7 CLIQUE7 NESFRE7 HAMILTONIANCIRCUIT 941 Subset Sum Proof by reduction from PARTITION Given an instance of PARTITION7 which is simply a finite subset S C N we can easily determine what the equal partitions must sum to it is simply half of the sum of all the numbers in S which we shall denote by 25 If the sum 25 is odd7 then we know immediately that such a partition is impossible This leads to the following reduction 07 1 otherwise 914 S 25 when 25 is even f 5 Note that when 25 is odd7 the mapping must still produce an instance of SUBSET SUM7 so we simply pick one for which we know a pn39orz39 that the answer is no such as 2517 since the empty set has no subset that sums to 1 Another possibility would be 51 ES since the requires sum is larger than can be attained In the former case7 all instances in which 25 is odd get mapped to the same problem instance7 clearly making the mapping manytoone In the latter case7 the mapping is onetoone 942 Bin Packing Proof by reduction from PARTITION Need to map the set S to a 3tuple7 5quot 161 where k E N is the number of bins7 and b E N is their capacity S72 25 when 25 is even f5 915 1 7271 otherwise 94 STRAIGHTFORWARD POLYNOMIAL TIME REDUCTIONS 133 943 Knapsack Proof by reduction from SUBSET SUM Let 5716 be an instance of SUBSET SUM Suppose S 81 82 H316 We de ne an instance of KNAPSACK as 8131sk73kmm 916 where m 25 Since the sum of the weights is to be bounded above by m7 and the sum of the values is to be bounded below by m7 they must sum to exactly m 944 4Color Proof by reduction from 3 COLOR We de ne a mapping from instances of 3 COLOR to instances of 4 COLOR such that fG 0 917 where G is 3colorable if and only if G is 4colorable Notice that if G G then G E 4 COLOR whenever G E 3 COLOR7 but that the latter may be true while the former is false That is7 yes answers are preserved7 but no answers may not be To remedy this7 we must ensure that if G is not 3colorable7 then G will not be 4colorable We accomplish this by ensuring that xG xG l Thus7 we de ne G V 7E such that V V U v7 where v is a new vertex7 and E E U u7 1 l u E V That is7 the new vertex v is adjacent to each of the original vertices in G Consequently7 whatever the chromatic number of G G will require exactly one more color to color the vertex v 945 Subgraph Isomorphism The language SUBGRAPH ISOMORPHISM consists of threetuples G1 G2 16 such that graphs G1 and G2 have subgraphs G l Q G1 and C Q G2 where G3 and G are isomorphic an have k or more vertices First SUBGRAPH ISOMORPHISM e NP because each element of SUBGRAPH ISOMORPHISM has a concise certi cate of membership7 which consists of the two subgraphs7 plus the correspondence between the vertices Such a certi cate is trivial to veri Next7 we show that SUBGRAPH ISOMORPHISM is NPcomplete by reduction from CLIQUE We de ne a mapping from instances of CLIQUE7 GJL7 to instance of SUBGRAPH ISOMORPHISM7 G1 G2 k such that G has a clique of size n or greater as a subgraph if and only if G1 and G2 have an isomorphic subgraph of size k or greater We simply let f 6371 G7 Own7 918 where On is the clique with n vertices Thus7 we have very directly rephrased the question of membership in CLIQUE as a special case of SUBGRAPH ISOMORPHISM This mapping clearly requires only linear time Therefore7 SUBGRAPH ISOMORPHISM is NPcomplete 134 CHAPTER 9 THE THEORY OF NP COMPLETENESS 946 NonEquivalent Regular Expressions The language of nonequivalent regular expressions or NERE is the language consisting of pairs of regular expressions that generate different regular languages The only difference between NERE and NESFRE is that we allow the use of the Kleene star operator in the former but not the latter Thus NERE is simply a generalization of NESFRE that is any algorithm that decides NERE also decides NESFRE As a consequence the reduction NESFRE 5 NERE is immediate being accomplished by the identity function It follows that NERE is NPcomplete 947 Traveling Salesman The Traveling Salesman decision problem or TRAVELING SALESMAN can be expressed as follows Given a complete graph4 G V E a distance function d V X V A N that assigns each edge in E a natural number and a number k E N determine whether there exists tour of all the vertices that is a circuit or loop whose total distance is k or less TRAVELING SALESMAN is clearly in NP as it is possible to guess a solution which is simply a permutation of the vertices then verify that its length is less than k in polynomial time A Hamiltonian circuit of a graph is a circuit or loop that passes through each vertex of the graph exactly once Given that the Hamiltonian circuit decision problem or HAMILTONIAN CIRCUIT is NPcomplete we can show that TRAVELING SALESMAN is also NPcomplete by polynomialtime reduction from HAMILTONIAN CIRCUIT This is in fact quite easy to do given the great similarity between the two problems Given a graph G E with V n we can determine whether it has a Hamiltonian circuit by transforming it into an instance of the traveling salesman problem Gdk as follows Let G V E be the graph G with each missing edge added that is G is the smallest clique containing G as a subgraph We then de ne the distance function d V X V A N as follows dlt 7 1 if uvEE 919 u7v 7 n1 ifuvEE 7E Finally we let the target length of the tour 16 be the number of vertices n In other words there exists a Hamiltonian Circuit in G if and only if G has a tour of length n or less The mapping G A G dn is therefore a manyto one reduction of HAMILTONIAN CIRCUIT to TRAVELING SALESMAN Since this mapping can clearly be computed in polynomial time this shows that TRAVELING SALESMAN is NPcomplete 95 Further Reading See Gary and Johnson 7 for a more detailed discussion of the classes P NP NPcomplete etc along with the history of their development The book by Gary and Johnson 7 is also an 4A complete graph also known as a clique is a graph in which every pair of vertices has an edge connecting them 96 EXERCISES 135 extraordinarily useful reference as it contains a catalog of hundreds of NPComplete problems Having such a catalog generally simpli es the process of determining whether some unknown problem is NPcomplete or not as one can generally choose a problem that is somewhat similar to perform the reduction fromi 96 Exercises 1 E0 CA3 g 5 Each element of the language SUBSET SUM consists of a nite multiset S ahagp I I an of natural numbers and a constant k E N such that some subset possibly a multiset of S sums to In Let us de ne a variant of SUBSET SUM which we will call INTERVAL SUBSET SUM each of whose elements is a nite multiset S of natural numbers and a constant k E N such that some subset possibly a multiset of S sums to any value between k and 216 inclusive a Show that the decision problem SUBSET SUM is NPcomplete using the NPcomplete problem PARTITION b Is INTERVAL SUBSET SUM NPcomplete Justify your answer by giving a polynomialtime algorithm for deciding it or by reducing some known NPcomplete problem to it The NPcomplete problem known as PARTITION is as follows Given a nite multiset of natural numbers 5 11 12 I I I In determine whether there is a subset possibly a multiset Squot C S such that 21 Z 1 aces 16579 a Explain why the obvious bruteforce method of solving the PARTITION problem requires exponential time in the worst case That is show that there is a sequence of problem instances for which the timecomplexity is exponential b Let K be a xed positive integer Show that PARTITION can be solved in polynomial time if the numbers in the multiset are bounded above by KI Describe the algorithm with pesudocode and explain why it runs in polynomial time You need not nd an ef cient algorithm any polynomial algorithm wil doi c Why must we require that K be a xed constant That is why is your algorithm no longer polynomialtime if we simply set K to be the maximum of all the numbers in a given list I Show that the relation Sm is transitive I Let HAMILTONIAN CIRCUIT CONSTRUCTION denote the problem of nding a Hamiltonian cir cuit in a graph or determining that no such circuit existsi Prove that this problem is NPequivalent but not NPcompletei Clearly label and explain all the steps Let us de ne a variant of SUBSET SUM called SUBSET SUM PLUS Z as follows Each instance of SUBSET SUM PLUS 2 consists of a nite set S of natural numbers and a constant k E N such that some subset of S sums to k or kl or k 2 Thus we are no longer looking for a speci c sum but any of three possible sumsi Show that SUBSET SUM PLUS 2 is NPcomplete using a polynomialtime manytoone reduction from SUBSET SUMI 136 CHAPTER 9 THE THEORY OF NP COMPLETENESS 6 Let us de ne a variant of SUBSET SUM7 which we will call SUBSET SUM TIMES 27 each instance of which is a nite set S of natural numbers and a constant k E N such that some subset of S sums to any value between k and 216 inclusive ls SUBSET SUM TIMES 2 NPcomplete Justify your answer by giving a polynomialtime algorithm for deciding it or by reduction from some known NPcomplete prob emi 96 EXERCISES 137 SATISFIABILITY NONAEQUIVALENCE OF 0 REGULAR EXPRESSIONS SUBGRAPH ISOMORPIIISM CNESAT NONAEQUIVALENCE OF STARAFREE CLIQUE REGULAR EXPRESSIONS 3CNESAT EXACT INTEGER 3COVER PROGRAMMING 37C0L0R PARTITION VERTEX COVER PLANAR 47C0L0R 37C0L0R IIAMILTONIAN CIRCUIT SUBSET SUM giggi ART GALLERY TRAVELING SALESMAN KNAPSACK BIN PACKING EUCLIDEAN TRAVELING SALESMAN Figure 91 This gure shows the strategy we will follow in proving a wide variety of problems to be NPComplete Starting from CNFESAT at the top the arrows indicate the polynomialitime reductions that we will study For example we will show how to reduce BCNFESAT to BECOLOR in polynomial time thus proving BECOLOR to be NPComplete The asterisks indicate relatively straightforward reductions 138 CHAPTER 9 THE THEORY OF NP COMPLETENESS Chapter 10 Challenging PolynomialTime Reductions This chapter supplements the previous chapter on the theory of NPCompletenessi Provided here are fairly detailed reductions showing that SCNF SAT 3 COLOR PLANAR S COLOR NESFRE NERE and TRAVELING SALESMAN are all NPcompletei Moreover we show that the Chromatic Number problem is NPhard that is it is just as hard as anything in NPcomplete but without being in NP itself as it is an optimization problem rather than a decision problemi These problems all involve the invention of gadgets that allow us to capture the essence of one problem in the vocabulary of another For example a recurring idea is that of mimicking the characteristics of a truth assignment in the context of something altogether different from boolean logic such as a graph or a set of natural numbers In particular any legitimate truth assignment will assign one of two values to each boolean variable and must assign di ferent values to the variable and its negationi In the context of 3 COLOR we achieve this behavior by creating a set of vertices in which any valid 3 coloring will assign them one of two colors and ensure that a node representing a given variable will have a different color than the one representing its negationi The gadgets used in these reductions are often very clever While the asserted behavior and ultimate role of a gadget may be easy to grasp supplying the details of such a thing can be a substantial puzzle in itself and there is no general strategy by which such puzzles can be solved Each reduction seems to be a unique invention crafted for the express purpose of proving the NPcompleteness of a speci c language Many of these problems were rst shown to be NPcomplete by Richard Karp in 197211i 139 140 CHAPTER 10 CHALLENGING POLYNOMIAL TIME REDUCTIONS 101 3CNF SAT We shall show that SCNF SAT is NPcomplete by reduction from CNF SATi Clearly SCNF SAT E NP since it is a proper subset of CNF SAT which is in NPi Given a formula F E CNF SAT we must show how to construct another formula F E SCNF SAT which has exactly three literals per clause that is satis able if and only if F is This transformation must be accomplished in polynomialtime which is insuf cient time to actually test the satis ability of Fl Thus we must perform the transformation without knowing whether F is satis able or not What we shall do is to successively reduce the size of clauses in F that have more than three literals and also increase the size of clauses in F that have fewer than three literalsl all the while retaining the satis ability or unsatis ability of the original formula Let f be any CNF formulai Then consider the formulas f1 f Zlv gvigvnVin 101 f1 f zvzlvm lVZgVHVZn 102 where n gt 3 the symbols Zlfg i i Zn denote literals iiei either Boolean variables or the negation of Boolean variables and 1 denotes a Boolean variable that does not appear anywhere in formula fli We claim that 71 is satis able if and only if fl is satis ablei To see this suppose that a truth assignment A satis es 71 which we denote by A l 71 Then A l i for some 1 S i S n since A must satisfy at least one literal in the last clausei lfi lt 3 then A U z L is a truth assignment that satis es fell On the other hand ifi 2 3 then A U z T satis es fell Therefore fl is satis ablei Now suppose that A l f1 Then A l 71 since A l i for some 1 S i S n Therefore 71 is satis ablei While the above procedure introduces more clauses it reduces the size of the last clause by one literali In a similar fashion we can add new variables to clauses that have fewer than three literals either by simply repeating literals or by introducing new variables as we have done abovei Consider the following two formulas f2 7 Z1VZ2 103 g f zvzlvzg WWWZ2 104 where again 1 denotes a Bookan variable that does not appear in formula 72 It is easy to see that 72 is satis able if and only if 72 is satis ablei These two operations can be used repeatedly to create an equivalent Boolean formula of the desired formi The algorithm is summarized in Figure 101 The rst loop replaces a clause with n gt 3 literals with a clause of length 3 and a clause of length n 7 1 Similarly the second while loop replaces a clause of length n lt 3 with two clauses of length n 1 Therefore both while loops are guaranteed to terminate eventually as each iteration makes progress toward reducing or increasing the size of clauses that have more or fewer than three literalsi The function returns a new CNF formula that is satis able if and only if the original formula 7 1We wish to end up with exactly three literals per clause rather than three or fewer because this is often convenient in constructing reductions from SCNFASAT That is it often simpli es the bookkeeping if we can assume that all clauses have the same number of literals The reduction of SCNFASAT to SACOLOR for example requires only one type of gadget because each clause has exactly the same form 102 3 COLOR 141 function CNFSAT to 3CNFSAT F Whlle F has a clause C containing more than three literals do I lt7 a new variable name replace C with I VZ1 V 2 or V 3 V V Zn endwhile While F has a clause C containing fewer than three literals do I lt7 a new variable name replace Cwith I VZ1V zVil endwhile return F m1 mgtgtwmgta Figure 101 An polynomialetz39me algorithm that converts a formula in CNFisAT into an equivalent formula in BCNFisAT that is the new formula is satis able 2f and only 2f the original formula is is but in which each clause has exactly three distinct literals This function computes a many to one reduction from CNF SAT to SCNF SATl Since the loops each iterate no more than kn times where k is the number of clauses and n is the number of distinct variable names this reduction is clearly computable in polynomial time Therefore CNF SAT 5 SCNF SAT which establishes that SCNF SAT is NPcomplete 102 3Color The language known as 3 COLOR consists of graphs that can be colored using three or fewer colors that is graphs in which each vertex can be assigned one of three colors in such a way that no two adjacent vertices are assigned the same color The corresponding decision problem can be stated thus Given a graph G can it be colored using three of fewer colors77 We shall show that 3 COLOR is NPComplete by reduction from SCNF SATl In this example we will spell out all the steps in detail Step 1 First we verify that 3 COLOR is in NPl Observe that if we are given an assignment of colors to the vertices of a given graph G then it is an easy matter to check that this assignment constitutes a valid 3coloring we need only verify that the endpoints of each edge are assigned different colors and that only three colors are used altogetherl This can clearly be accomplished in polynomial in fact linear time We also observe that no such assignment of colors can exist for graphs that are not in 3 COLORl Step 2 Next we show that we can reduce a problem that is already known to be NPcomplete to 3 COLORl In particular we will show that SCNF SAT 5 3 COLORl That is we will show how to convert an arbitrary instance of SCNF SAT into an instance of 3 COLOR in such a way that the yesno answer is preserved and requiring only polynomial time Thus the resulting graph G will be threecolorable if and only if the given 3 CNF formula is satis ablel Let F be any propositional formula in SCNF form with n distinct propositional variables and k clausesl Let X 11 12 l l In denote the set ofvariables appearing in F let 7 E1T2 l l l En denote the set of their negations and let C 01 02 l l ck denote the set of clauses in F each containing exactly three literals from X Uyl 142 CHAPTER 10 CHALLENGING POLYNOMIAL TIME REDUCTIONS b Figure 102 These graphs illustrate the reduction from BCNFisAT to BicOLOR a This graph is 37colorable if and only if at least one of the two vertices in the dashed circle is the same color as vertex a b By similar reasoning this graph is 37 colorable if and only if at least one of the three vertices in the circle is the same color as vertex a Once we interpret the color of vertex a as true this idea can be used to ensure that the graph can be 37colored if and only if at least one literal in each clause can be satis ed Consider the undirected graph G V E that is constructed from F as follows Let the vertex set V consist of the union of these sets abc and for i 12Hln and djej fjgjhj for j 12 l i i k The resulting vertices are to be connected as shown in Figure 103 which shows a portion of the construction corresponding to the 3CNF formula 11 V zg V 13 11 V 13 V z4 12 V z4 V 105 Figure 102 shows several simpler graphs illustrating how the construction in Figure 103 works We claim that G will have the desired property that is G will be 3colorable if and only if F is satis ablel Suppose that G is 3colorablel Then all three colors must appear in the triangle formed by vertices a b and c Let us refer to these colors T L and O respectively as this will make clear the interpretation that we will be giving the coloring Since each of the vertices representing the literals is connected to the vertex with color O and each literal is connected to its negation this means that each literal is colored either T or L with its negation colored appropriately that is one is T and the other is L The gadget shown on the right of Figure 102 is designed in such a way that in any valid 3 coloring at least one of the vertices in the dashed circle must be colored T this fact is used to ensure that each clause will have a minimum of one true literal Thus a valid 3 coloring indicates the existence of a valid truthassignment such that at least one literal per clause is true which implies that the formula F is satis ablel A similar argument shows that if F is satis able there is a valid 3 coloring of the graph G Step 3 Finally we verify that the manytoone reduction from SCNF SAT to 3 COLOR can be computed in polynomial time But this is almost immediate The vertex set V of the graph G that we have constructed will have 1 three special vertices a b and c 102 3COLOR 143 Figure 103 This is the complete construction corresponding to aformula in 3CNF with n distinct variables and k clauses The graph is 3ecolorable if and only if the original formula is satis able Shown is a portion of the construction for the formula I1 V xz V m x1 V as V xi I2 V n V an 2 a vertex for each variable in F 3 a vertex for the negation of each variable F 4 vertices djejfjgj and hi for j 12Hlh for a total of 2n 516 3 verticesl If E is the edge set of G then E consists of 1 ab bc ca 2i acheI2cmznc 3i EhcEgcminc 4i mil12E2iuznin 5 the ve edges for each gadget as shown by the dark lines in Figure 103 for each of the k clauses in F 6 dja and eja for j 12Hlkl 7 The three edges connecting each of ej 9 and hj to a single literal for j 12l l l kl These are shown as dashed lines in Figure 102 for a total of 3n 1016 3 edges in El Typically this level of accounting is unnecessary as we are only obliged to demonstrate that the construction can take place in polynomial time Thus all that 144 CHAPTER 10 CHALLENGING POLYNOMIAL TIME REDUCTIONS P 1 1 Figure 104 Planar gadgets used in the reduction of BeCOLOR to PLANAReBeCOLOR Left If this graph is 3ecolored vertices u and 2 must have the same color If the color of q is di erent from that ofu and 2 then p must be the same color as 1 However if q is the same color as u and 2 then p can be assigned any of the three colors Center This graph is built by combining two copies of graph on the left which completes the constraints That is if it is 3ecolored then the colors of u and 2 must match and the colors ofp and 1 must match However the colors ofp and u are independent Right This is a somewhat simpler gadget due to Michael Fischer that has the same properties as the one in the center is relevant is that we are constructing a copy of a particular gadget for each clause another for each variable and adding another xed collection of vertices and edges the triangle abc We have therefore shown that 3 COLOR is NPcomplete by reduction from SCNF SAT The word om77 is crucial here as it emphasizes that instances of SCNF SAT were rephrased as instances of 3 COLOR not the other way around Performing the reduction in the other direction would not have shown anything usequ yet this is a common mistake 10 3 Planar 3Color A planar graph is a graph that can be drawn in such a way that no edges cross The famous four color theorem77 assures us four colors always suffice to color a planar graph However three colors do not always suffice and determining whether a given planar graph is 3 colorable is intractable When one places additional restrictions on the form of a problem it often makes the problem easier For example if we place the additional restriction on instances of SCNF SAT that each clause is to have at most two literals rather than three the problem becomes solvable in polynomial time Thus when we restrict the problem instances it is generally necessary to either reestablish NP Completeness or conclude that the restricted problem is now solvable in polynomial time In the case of restricting the 3coloring problem to planar graphs it so happens that the problem remains just as hard 2In fact we already know that SrCOLOR g5 CNFrSAT by virtue of the fact that SrCOLOR e NP and CNFrSAT is NPecomplete hence exhibiting such a reduction would not demonstrate anything new 104 VERTEX COVER 145 Consider the three graphs shown in Figure 104 which are all 3colorable Copies of the gadget in the center or on the right can be used to convert an arbitrary graph into an equivalent planar graph that is a planar graph that is 3colorable if and only if the original graph is 3colorable We now provide a brief sketch of how this is accomplished The trick to the conversion is to notice that if the gadget in Figure 104 is 3 colored then vertices u and 1 must be assigned the same color and vertices p and 4 must be assigned the same color However the colors assigned to the two pairs are independent This gadget allows for one edge to cross through another while preserving 3colorability and remaining planar Thus the reduction from 3 COLOR to PLANAR S COLOR proceeds by replacing each crossing pair of edges with a copy of this gadget When no more crossing edges remain the resulting graph is planar and is 3colorable if and only if the original graph is 10 4 Vertex Cover The decision problem known as VERTEX COVER is as follows Given a graph G V E and k E N determine whether there exists a subset of vertices V C V such that lV l S k and each edge in E is incident upon some vertex in VA We think of the subset V as covering the edges of C It is well known that VERTEX COVER is NPcomplete in fact it is one of the most fundamental NPcomplete problems in that it is frequently used to show that other problems are NPcomplete The proof that VERTEX COVER is NPcomplete is a classic example of how such proofs are constructed Step 1 It is easy to see that VERTEX COVER is in NP The certi cate of membership is simply the set of vertices in the cover The size of this set is clearly no larger than the graph G and the fact that it is a cover of the required size can be easily checked in time we simply check each edge to ensure that one of its endpoints is in the cover Step 2 We shall show that SCNF SAT 5 VERTEX COVER Let f be a boolean formula in 3 CNF form and let X 11E1 12E2 szn be the set of all variables in 7 along with their negations and let C 511512013 ck1ck2ck3 denote the set of clauses where each CM 6 X We shall construct a graph G V E starting with some basic elements V XUcL1ci2ci3lil2k 106 E Ci1Ci2 512013 cl30 l i 12k U l i 12 n 107 where n is the number of distinct variables and k is the number of clauses in fig These vertices and edges de ne a line for each distinct variable and a triangle for each clause as shown in Figure 105 The minimal vertex cover for this basic graph consists of n 2k vertices one for each line and two for each triangle We next add one additional edge for each literal in each clause The edge will connect each vertex of the jth triangle to a different vertex representing a literal in the jth clause This is depicted in Figure 106 Claim The resulting graph has a vertex cover of size n 216 if and only if the boolean formula 7 is satis able To see this note that the two vertices in the cover that are in each triangle cover the 3 ere we are using the variable names mg as well as their negations and the symbols cg 39 which denote the literals of each clause merely as vertex labels in a graph In their role as vertex labels they lose their former meanings as variables and su 146 CHAPTER 10 CHALLENGING POLYNOMIAL TIME REDUCTIONS three edges of the triangle plus exactly two of the edges connecting the triangle to the corresponding literalsr The third edge connecting the triangle to a literal must be covered in another way the only other option is to cover it with the vertex that is covering the line it connects to If a cover of size n 2k exists then the vertices covering the literals must also succeed in covering at least one edge that leads to each of the clausesr If we identify the covered literals as representing T this means that each clause will have at least one T literal which means that the formula is satis abler On the other hand if the formula is satis able then it is possible to assign truth values to each of its variables in such a way that each clause will have at least one T literalr The existence of a satisfying truth assignment ensures that the graph G can be covered with exactly n2h vertices since the literals can be covered in such a way as to cover at least one edge leading to each triangles Step 3 The construction of the graph from the boolean formula can clearly be accomplished in Oh n time as each clause and each literal requires only a constant amount of works This is trivially polynomial in the size of the boolean formu as variable 1 variable 2 variable 3 variable n X1 X1 X2 X2 X3 X3 X o o o o O O 0 C11 C13 C21 C23 Cki Ck3 Figure 105 This gure shows part of the construction used to prove that VERTExecOVER is NPComplete by reduction from BCNFesAT The construction begins with 3k 2n vertices and 3k n edges organized as k triangles and 71 lines where k is the number of clauses and n is the number of distinct variables in the boolean formula This graph requires exactly 2k n vertices to cover all the edges One such selection of vertices is shown here the vertices in the cover are circled 105 Clique The decision problem known as CLIQUE is as follows Given a graph G and h E N determine whether G has a subgraph of size h or larger that is a clique irei completely connectedr We will show that CLIQUE is NPcomplete by reduction from SCNF SATr Step 1 CLIQUE is clearly in NP since it is a decision problem with an obvious certi cate of membership namely the list of vertices in the cliquer Given such a list it is trivial to check that they form a clique simply by checking that each is adjacent to all the others in the graph Gr 106 HAMILTONIAN CIRCUIT 147 variable1 variable Z variable 3 variable n X2 X2 Figure 106 This gure shows the complete construction that is used to transform an instance of BCNFisAT to an instance of VERTExicOVER The portion of the graph shown here corresponds to the 3iCNF boolean formula I1 V as V52 2 V 1 V in 51 V an V Is The dashed lines connect the triangles which represent the clauses to the corresponding literals found in that clause The complete graph consists of 271 3k vertices and 71 6k edges where k is the number of clauses and n is the number of distinct variables in the boolean formula The graph has a vertex cover consisting of n 2k vertices if and only if the boolean formula is s atis able Step 2 Given a boolean formula in 3CNF form With k clauses we construct a graph G V E consisting of 316 vertices as follows Each vertex Will correspond to one literal in the formula We add edges connecting each vertex to all other vertices that represent noncontradictory literals in other clauses For instance the vertex representing the literal 11 Will be connected to every literal in every other clause except for 51 See Figure 107 In other words each literal I Will be adjacent to every literal in every other clause that it is compatible With 7 ie to every other literal that could be made T simultaneously With I If there exists a clique of size k in this graph it means that there is at least one literal that can be set to T in each clause simultaneously since each of the literals is compatible With all the others Thus the formula is satis able Clearly the converse is also true if the formula is satis able the graph G Will have a clique of size k Step 3 The construction of the graph G can be done in 0062 time Which is polynomial in the size of the boolean formula 106 Hamiltonian Circuit The language HAMILTONIAN CIRCUIT consists of graphs that contain Hamiltonian circuits that is graphs that contain a circuit cycle that passes through each vertex exactly once HAMILTONIAN CIRCUIT is clearly in NP since the ordered list of vertices in the circuit suf ces for a certificate of membership 148 CHAPTER 10 CHALLENGING POLYNOMIAL TIME REDUCTIONS clause 2 clause 1 clause n X3 x X2 ll clause 3 Figure 107 This gure shows the construction that is used to transform an instance of BCNFisAT to an instance of CLIQUE The complete graph consists of 3k vertices and up to 9kk 7 1 edges where k is the number of clauses and rt is the number of distinct variables in the boolean formula An edge is placed between every pair of vertices that represent nonecontradictory variables in di erent clauses The edges adjacent to one vertex labeled x1 within one clause are shown here This vertex can be connected to every other vertex associated with every other clause except for T1 which it is incompatible with The graph has a clique of size k if and only if the boolean formula is satis able in HAMILTONIAN CIRCUIT such a certi cate can be checked in linear time to verify that it contains all the vertices of the graph and de nes a simple circuits We will show that HAMILTONIAN CIRCUIT is NPcomplete by reduction from VERTEX COVER That is7 given any graph G V7 E and an integer k we wil show how to construct another graph G V 7 E such that G has a vertex cover of size k if and only if G has a Hamiltonian circuits The reduction hinges on the use of the clever gadget shown in Figure lOiSal This 12vertex7 l4 edge7 graph will be replicated many times as a subgraph of the graph G that we will construct each copy will be connected to the larger graph only at its four corners7 as shown in the gures This gadget was devised to have a very special property If the graph to which it is a subgraph has a Hamiltonian circuit7 then the circuit must pass through774 the gadget in one of two ways 1 By entering at one corner7 following a sideways Q pattern7 then exiting the gadget on the same side7 as shown in gures lOiSb an 0i8cl 4Although we are considering only undirected graphs and undirected circuits it is useful to talk about a circuit as if it were directed eg by speaking of the circuit passing through verticesv This will aid in visualizing how the construction works 106 HAMILTONIAN CIRCUIT 149 2 By passing through the gadget twice in parallel paths as shown in Figure 108d This gadget will allow us to build a graph that mimics the essential properties of a vertex cover using a Hamiltonian circuitl Each gadget will represent an edge e in the original graph G the one that we are testing for a vertex cover and a circuit passing though it will correspond to a vertex covering er Since one or both of the endpoints of the edge 6 may be included in a vertex cover of G we must allow the circuit to pass through the gadget either once or twice but to pass though all vertices exactly once in either case This is precisely what the gadget allows us to do Here are the details of the construction For ease of notation welll denote some of the vertices of the graph by arrays with three subscripts zu v i where u and v are vertices in the original graph G and i is a positive integer First de ne the vertex sets L3 g dmumzmaieEJig6 00 V2 15 y17y2puyyx 109 and the edge sets E1 if za 121 zab2 zab2zab 3 H lab E E 1010 E2 if za Nia 6zaNl1a1 l 1 S i lt dega 1011 E3 g mN mJLWHaewigng min E4 if aNda6yj l a E V1 S j S Kd dega 1013 Here degv is the degree of vertex v and Niv denotes the ith neighbor of vertex 1 according to some xed but arbitrary ordering The sets V1 and E1 consist of many copies of the 12 vertices and the 14 edges respectively that are shown in Figure 1018a one copy for each edge in the original graph G1 Thus the subgraph G1 V1E1 consists of copies of the gadget The edges E2 create chains of gadgets that correspond to the edges adjacent to each vertex in G1 The edges E3 and E4 connect the start and end of each chain of gadgets to all of the vertices in V2 Finally we de ne G V E by W E mow awn E 12 EluEguEguEr 10115 An example of this construction is shown in Figure 1019 where the gray boxes are schematic rep resentations of the gadgets To keep the gure legible the edges in E3 and E4 are depicted in abbreviated form for all but three verticesi We claim that G has a Hamiltonian circuit if and only i G has a vertex cover of size 1 Observe that if G has a vertex cover of size K then we can nd K simple paths in G that begin and end in V2 and pass through each of the gadgets either once or twice according to whether one or both of the endpoints of a given edge are in the vertex coveri Thus we can construct a Hamiltonian circuit through G by joining these paths together forming one large circuitl Conversely if G has a Hamiltonian circuit then such a circuit must pass through the collection of gadgets exactly K times since it must pass through all the vertices of V2 he K vertices of G that correspond to these K loops through the gadgets of G will suf ce as a vertex cover of G since the circuit must pass through each gadget at least once and this implies that each edge of G is adjacent to at least one of these verticesi 150 CHAPTER 10 CHALLENGING POLYNOMIAL TIME REDUCTIONS I KIWI KIWI I Kiwi2 XlVJLZl V I XlHrVr3l XVL13 XlurVr4 XVL14 I XlHJ l xii415 x I XlHrVrGl XVL16 I III I a b C d Figure 108 a The gadget that is used to reduce VERTExicOVER to HAMILTONIANicIRCUITI Each instance of this gadget corresponds to an edge u v of the graph G and consists offourteen edges and twelve uertices which we denote by xuv 1 I I I xuv6 and xvu 1 I I I xvu6 as shown Each gadget is connected via its four corner uerticesI All twelve uertices can be included in a Hamiltonian circuit in one of exactly three ways as shown on the right 17 a path that passes through on the right c a path that passes through on the left or d two parallel pathsI 107 Partition Each member ofthe language PARTITION consists of a list multiset of natural numbers a1 a2 I I I an that can be split into two sublists with the same sumI We will show that PARTITION is NPcomplete by reduction from SCNF SATI Let f C1 I I I CK be a boolean formula in CNF form with the K clauses C1 I I I CKI Let n be the number of distinct variables 11 I I I In in f and let B E N be a constant such that B 2 7 we will use B as the base of a number system to construct an instance of PARTITIONI De ne the function 6 z N X N A 01 based on the clauses of f such that La 1 if z E Cj 5177 T 0 otherwise 1016 Let us also de ne 3ij analogously using the negated variables 7 Leg 1 if E e Cj 5177 T 0 otherwise 10 107 PARTITION 151 Figure 1019 The construction used for reducing VERTExicOVER to HAMILTONIANicIRCUIT The graph on the left leads to the ve gadgets on the right7 one for each edge Each path through the gadgets represents the edges adjacent to one vertex of the original graph The vertices y177yk on the far right allow any Hamiltonian path to make exactly k loops through the collection of gadgets We now de ne 2n natural nurnbers7 U171 7 Un and U171 7 U777 by U7 25 BKti l Z sh73314 1018 1315K U7 25 191Wquot1 Z 3i7jBj 1 1019 1315K for i 17 27111 7n1 Thus7 Ui encodes the Clauses that the literal 17 appears in and Vi encodes the Clauses that the literal 51 appears in Next we de ne the numbers V17 1 1 1 7 VK by V7 5 EH 1020 for j 17271117 K7 and the natural numbers W by W 25 Z 3141 1021 1515K 152 CHAPTER 10 CHALLENGING POLYNOMIAL TIME REDUCTIONS Finally we de ne the list multiset of 2n K 1 natural numbers S if UhmUnU1mUmVl iVKV1mVKWi 1022 We claim that S can be partitioned into two lists multisets with equal sums if and only if the original boolean formula is satis ablei Moreover the satisfying truth assignment can be easily read from the solution to the partition problem all literals in the set containing W are set to L and all literals in the set not containing W are set to T To see this imagine the collection of numbers 5 organized as shown in Figure 1010 The constant B was chosen so that the sum of any subset of these numbers cannot result in a carry from one eld to the next as no column sums to more than six The sum of the elds in the gray column is always exactly two This ensures that the numbers corresponding to a variable and its negation iiei Ui and Vi cannot both be on the same side of the equation In this context the equation is that in which the sum of a subset of the numbers is on one side and the sum of the rest is on the other The sum of the elds in a white column is always six three from group a that represent the variables in a clause two from group b since there are two copies of these numbers for eac clause and one from group c which contains a single number with a one in each white columni Consider the column corresponding to clause C Observe that not all of the numbers representing the literals in this clause can be on the same side of the equation as W since the elds in this column would then sum to at least four on one side which cannot be matched on the other side since the total for this eld is only six Consequently at least one of the literals in clause j must be on the side opposite Wi This is the only constraint however since the V numbers assure that all other combinations can result in an even partition that is if one two or three literals are on the side opposite W the numbers within eld j can be evenly partitioned by placing zero one or both of the V7s on the side of W respectively This is true within each white eld independentlyi Since the gray elds prevent both Ui and Vi from being on the same side of the equation for 1 S i S n the side that does not contain W de nes a valid truth assignment that places at least one true literal in each clause that is it is possible to simultaneously set all these literals to T and doing so satis es the original boolean formula This construction shows how to reduce SCNF SAT to PARTITION Each row represents a natural number that is partitioned into a number of smaller elds The elds are suf ciently wide so that adding these numbers will not result in in a carry from one eld to the next There is an number in block a for each variable as well as its negationi The gray elds prevent both a variable and its negation from being in the same partition ie on the same side of the equation There are two identical numbers in block b for each clause in the boolean formulai There is only one number in block c this number will indicate which half of the partition contains the truth assignment speci cally setting all the literals in the sublist that does not contain W to T will satisfy the original boolean formula 108 NonEquivalent StarFree Regular Expressions The language of nonequivalent starfree regular expressions or NESFRE is the language consisting of pairs of regular expressions e1e2 such that neither e1 nor e2 makes use of the Kleene star 108 N ON EQ UIVALEN T STAR FREE REG ULAR EXPRESSIONS 153 There are exactly six Ts in each There are exactly of these kcolumhs two Ts m each of these 71 columns CK 39 39 39 C3 C1 1 There 5 a pair of these numbers for each clause each containing a single T There 5 a T m each of these k elds Figure 1010 The construction used to reduce BCNFesAT to PARTITION A boolean formula f with 71 variables and k clauses is mapped to a set of 271 2k 1 natural numbers Each number is formed using elds wide enough to prevent a carry from one eld to the next when added There is one number for each variable and one for each negation of a variable In any valid partition the high order bits gray force the numbers representing negated and unrnegated variables to be in di erent subsets The loweorder bits encode the clauses that the literal appears in If a partition exists falsifying the literals in the subset containing W will satisfy f If no partition exists J cannot be satis ed operator and the languages generated by el and eg are different making them nonequivalents This language corresponds to the following decision problem Given two starfree regular expressions 154 CHAPTER 10 CHALLENGING POLYNOMIAL TIME REDUCTIONS el and eg are they nonequivalent77 We shall show that this problem is NPcomplete by reduction from CNF SATi Let F be a Boolean formula in CNF form and let C1 C2 i i i Ck denote the clauses of F and let 11 12 i i i 1 denote the Boolean variables appearing in F Thus F has k clauses and n distinct variables Let us encode truth assignments for F as a string of length n consisting of the symbols T and L the ith symbol in such a string simply indicates the value assigned to variable mix We shall create a regular expression R1 over the alphabet E T L that generates all falsifying truth assignments of F and another regular expression R2 over the same alpha et that generates all 2 possible truth assignments for Fl Observe that F is satis able if and only if it is not falsi ed by all truth assignmentsi Thus F is satis able if and only if R1 is not equivalent to Rgi This is equivalent to the statement that F is in CNF SAT if and only if R1R2 is in NESFREi We rst de ne a family of simple regular expressions one for each literal of each clausei L if z is a literal in clause Cj T if zi is a literal in clause Cj 1023 T l L otherwise Then Xij indicates the possible truth assignments for variable i that are compatible with clause Cj being falsi ed If we juxtapose all n of these for a given clause Cj Ej le X21 quotX7113 1024 then Ej is a regular expression that generates all possible truth assignments that falsify clause Cji To falsify the original formula we need only falsify a single clausei Taking the union of the truth assignments that falsify the individual clauses we arrive at the regular expression that produces all falsifying truth assignments of F R1 E1 l E2l l E19 1025 The regular expression that generates all possible truth assignments for the n variables is simply R2TliTlLTli7 1026 where the expression in parentheses is concatenated n times Then R1 R2 if and only if every truth assignment falsi es the Boolean formula F which is to say that F is unsatis ablei Equivalently R1 R2 if and only if F is satis ablei The language NESFRE is in NP since we need only nondeterministically guess a string that is generated by one expression and not the other then check that this is the case We next observe that CNF SAT 5 NESFRE via the construction above which clearly can be carried out in polynomial time Observe that the situation is entirely different if we were to be testing for the equivalence of starfree regular expressions rather than nonequivalence In this case the corresponding decision problem is not even in NP since elements of the language do not seem to admit short certi cates of membership that is there is no guess that we can make that can be easily checke i 109 INTEGER PROGRAMMING 155 109 Integer Programming Proof by reduction from 3CNF SATl That is we will show that SCNF SAT g5 INTEGER PROGRAMMING Let f be a boolean formula in SCNF Let v1 v2 l l 1 denote the variables appearing in f and let 5152 l 5 enote their negationsl We will encode a truth assignment for f as a vector x of Zn elements consisting of 07s and 17s The first n elements will encode the truth values of v1 v2 l l vn while the last n elements encode the truth values of 5152 l Enl Specifically a 1 will encode T and a 0 will encode Tl We wish to set up an integer program such that any valid solution will represent a valid truth assignment that satisfies 7 that is a truth assignment that will simultaneously satisfy at least one literal in each clause of fl We can accomplish this by imposing the following constraints on the elements of x H zi 1foril2ul2nl E0 zizinlt1foril2lunl 9 11 zj 1k 2 l where ij k are the indices of the literals appearing in each of the clauses 0102MCk off The first two sets of constraints ensure that any integer solution will correspond to a valid truth assignment moreover any valid truth assignment will automatically satisfy these constraints The third set of constraints ensures that any valid solution will assign at least one variable in each clause a positive value These constraints can be easily expressed as an integer program by defining the m X k integer matrix A where m 3n k and the vector b 6 NM as follows I 0 1 0 I 1 A I I b 1 1027 713 7E 71 where I is the n X n identity matrix and B and E are both k X n matrices defined as follows 7 1 if vj 6 Ci B 7 0 otherwise 1028 and i 7 1 if 5139 e C B 7 0 otherwise 1029 1010 Exercises H Describe how to preform the reduction CNF SAT 5 3 COLOR by generalizing the gadget used in the reduction of SCNF SAT to 3 COLORl E0 Describe how to preform the reduction SCNF SAT 5 HAMILTONIAN CIRCUIT by using the two types of gadgets shown belowl Chapter 2 Mathematical Preliminaries 21 Elements of Set Theory Set theory is one of the fundamental tools that we shall use in formalizing machines languages and computation The notion of a tuple relation of function shall appear in virtually every discussion The concept of cardinality is also central as we shall frequently wish to characterize the 77size77 of in nite setsl As we shall see not all in nite sets are equivalent which has some rather profound implications for computer science For example we can use this fact alone to show that there exist wellde ned mathematical functions that cannot be computed by any conceivable computer or programi Several sets are so fundamental that we adopt standard notation for theml In particular we de ne the natural numbers the integers and the rationals by N 012m Z 2771707172 Q kmlkEZAmENi0a respectively Similarly we denote the set of all real numbers by R The empty set is denoted by 0 211 Tuples and Relations An ordered pair consisting of 1 and y is denoted by 1 y where 1 is referred to as the rst coordinate and y is the second coordinate The ordered pair 1 y differs from the set 1 y in two crucial ways 1 order is signi cant so 1 y and y1 are distinct whenever 1 and y are and 2 the coordinates need not be distinct so 1 1 is a valid ordered pair whereas 11 has the same meaning as Two ordered pairs a b and 1 y are equal if and only if a 1 and b y In purely settheoretic terms one could de ne the ordered pair 1y to be the set 11y which has the required propertiesl That is it encodes ordering because 1 f y when 1 and y are distinct 17 18 CHAPTER 2 MATHEMATICAL PRELIMINARIES and it also handles the case where the elements are identical since 11 corresponds to the set 1 which is distinct from the singleton set We will not require this level of settheoretic formalism however and will treat ordered pairs as legitimate mathematical objects in themselves An ntuple denoted by rhzgp i In is the obvious generalization of an ordered pair here the coordinates 11 12 In may or may not be distinct The word tuple is sometimes used instead of n tuplei If A and B are sets the Cartesian product of A and B denoted by A X B is the set of all ordered pairs in which the rst coordinate is from A and the second coordinate is from AXB if zylz Ay Bi The Cartesian product generalizes to any number of sets Thus the n fold Cartesian product A1 X142 gtltquot39 gtlt An if alvwwan l Di 614139 is a set of n tuples where the sets A1A2i An may or may not be distinct Here the operators X X X are taken together to de ne a single n ary operator rather than each forming a set of ordered pairs In the special case where each Ai is the same set A we denote the n fold Cartesian product by Ant Since AXBgtltC 5 abclaeAbeBceC which consists of ordered pairs whose rst coordinate is another ordered pair this is clearly distinct from both A X B X C and A X B X C However we shall occasionally treat all three sets as consisting of threetuplesi That is we shall ignore the extra level of parentheses when it is convenient to do so which in effect de nes a natural isomorphism among the different sets that is an obvious onetoone correspondence between the elements of one and the elements of the other A binary relation R on sets A and B is simply a subset of the Cartesian product That is R Q AXBi An nary relation is a subset of the Cartesian product of it sets The arity of a relation is the number of sets in the Cartesian product or equivalently the number of coordinates in the resulting n tuplesi For example consider the following two relations which are subsets of N2 and N3 respectively L if zkyforsomekgt0 P if zyyyz l 1292 22 where z y z and k are all natural numbers Then L is the binary less than77 relation and P is the ternary Pythagorean relationi In the case of binary relations such as L it is common practice to use notation aLb to denote the fact that ab 6 Li Moreover we often adopt a special symbol for a relation such as lt77 to denote the less than relation so we write a lt 12 instead of a b 6 Li 212 Functions and Partial Functions Let X and Y be sets and let f be a binary relation on X and Y that is f E X X Y Then f is called a function if for every I E X there is exactly one ordered pair ab E f such that a z 21 ELEMENTS OF SET THEORY 19 When f has this property we often write f z X A Y and refer to X as the domain of f and Y as the co domain of We typically write fa 12 instead of ab E The notation fa is convenient for functions because each element of the domain is associated with one unique element of the codomaini By a partial function we mean a generalization of a function in which we allow zero or more elements of the domain to have no associated element in the codomain that is we allow fa to be unde ned for zero or more a 6 Al Note that every function therefore quali es as a partial function as well that is it is a partial function that happens to be de ned on all the elements of the domain Thus to make it clear when we are talking about functions in the traditional sense we will often refer to them as total functionsli It is frequently useful to consider the action of a function f z X A Y on subsets of the domain Xi For any subset Z Q X we de ne fZ if f2 l 2 6 Z which is known as the image of Z under A related concept is the setvalued inverse image with respect to the function f which is de ned by f 1y if 1 le1y Note that f 1 is a relation but in general not a function since it may be onetomanyi That is f 1y may consist of many elements or may even be the empty set Combining the above notations we de ne f 1Z if IEleI E Z for any subset Z E Y which is called the inverse image of Z under A function f z X A Y is said to be surjective or onto if Yr It is said to be injective or oneto one if each I E X is mapped to a unique y 6 Yr That is I f y implies that f or equivalently implies that z yi Finally f is said to be bijective if it is both injective and surjective oneto one and onto The inverse of f z X A Y is a function if and only if f is a bijection The sets X and Y are said to be in onetoone correspondence if and only if a bijection exists from one to the other Two functions are equal if and only if they produce the same values for each element of the domain Thus we say that two functions on the same domain are distinct ie not equal if and only if there is at least one element at which they differ That is if f z X A Y and g z X A Z then f f g if and only if gz for some I E Xi 213 Cardinality If a set S can be put into onetoone correspondence with the set l23i i i n then n is said to be the cardinal number of S and we write 5 n In other words the cardinality of a set S is its size This notion also applies to in nite sets but we need additional notation and terminology to talk about such setsi For example if the set A can be put into onetoone correspondence with lTechnically such a function would be a total partial function as it is a special case of a partial function However that absurdesounding terminology is usually abandoned in favor of the much more logicalesounding total function 20 CHAPTER 2 MATHEMATICAL PRELIMINARIES the natural numbers N 01 2 i i then we say that A is countably in nite This is expressed in symbols as lAl No where the symbol N aleph is from the Hebrew alphabet2l If two sets can be put into onetoone correspondence we say that they are are of the same cardinality or equinumerable and this is our criterion for declaring two sets to be of the same size whether nite or in nite A set that is equinumerable with a subset of N and possibly all of N is said to be countable or denumerable thus all nite and countably in nite sets are countable A surprising result of set theory discovered by the mathematician Georg Cantor in the 19th century is that there are uncountable or nondenumerable setsl For example Cantor succeeded in showing that the continuum of real numbers R is uncountable using a technique known as diagonalz39zatz39onl We state this as a theoreml Theorem 4 The set of real numbers R is uncountable That is R cannot be put into onetoone correspondence with the natural numbers N Proof We will show that no function f z N A R can be bijectivel We need only establish that every such function leaves out at least one element of R and thus fails to be onto For a given f we can construct an element of R that is not in the set f0 fl f2l i by diagonalz39zatz39onl Let 6kz denote the hth binary digit of I after the binary point Now let y E R be any number such that its binary digits after the binary point satisfy 1 if 60am 0 6k y 7 0 otherwise for k 123 i i M Then clearly y f for any 16 since the numbers differ in the hth digit after the binary pointl Consequently y g fN showing that f is not onto and therefore not a bijection D It is useful to introduce several conventions for comparing the cardinalities of sets that continue to be meaningful when the sets are in nite When the sets A and B are nite it is clear what lAl lBl and lAl lt lBl mean since we are simply comparing natural numbers In particular the former means that A and B have the same number of elements and the latter means that B has more elements While these exact statements do not translate to in nite sets the notation does if we are careful to de ne them in terms of functions By de nition then 1 lAl lBl means that A and B are equinumerablel That is there exists a bijection from A to B and therefore from B to A 2 lAl S lBl means that there exists an injection from A to B which may or may not be surjectivel 3i lAl lt lBl means that there exists an injection from A to B but no such mapping is also a surjectionl In other words is always a proper subset of B for every function f z A A B Note that these de nitions hold for all sets nite and in nite In the case of nite sets the meaning agrees exactly with the intuitive meaning which is based on comparing natural numbers i 2The symbol No is called aleph null 21 ELEMENTS OF SET THEORY 21 De nition 1 The power set of a set A denoted by either 73A or 2 is the set of all subsets of A that is 73A 25 3 S g A The notation 2 requires some explanation it actually denotes the set of all functions from the set A to the set 2 that is the set 01 which has two elementsgi Because each function f z A A 01 is naturally associated with a unique subset of A namely the set f 1l there is an obvious oneto one correspondence between the subsets of A and the functions f z A A 01 Consequently it is common to use the notation 2A to denote the power set of Al This idea also explains the notation R2 which is used to denote the set of ordered pairs of real numbers This set is actually the set of all functions f 01 A R ordered pairs result if we let 0 represent the rst coordinate and 1 represent the second coordinatei Theorem 5 Cantor s theorem The power set of any set has a cardinality strictly greater than the original set that is 73Al gt Al for any set A nite or in nite Proof Let f z A A 2 be any given function We shall use a form of diagonalization to show that some 5 6 2A is left out of fA so f cannot possibly be surjectivei In particular consider the set S aeAla fa By design the set S differs from the set fa in at least one element for each a 6 Al Consequently S g fA where is the collection of all sets fai Since 5 Q A and S g fA we conclude that 2Ai Thus there exists no mapping from A onto 2 and hence no bijectioni It follows that A cannot be put into oneto one correspondence with its own power set D Because the proof of theorem 5 makes no assumptions about the size of the original set A we now have a way to construct a countably in nite sequence of in nite sets each with a distinct cardinality that is by repeatedly taking the power set The above theorem revealed an anomaly in set theory known as Cantor s paradox which prompted mathematicians to rethink the foundations of mathematics and set theory in particular around the turn of the century Cantor noted that if the theorem is true for all sets then it must hold for the set of all sets77 That is the theorem implied that the power set of this massive set must be larger stilli But how could this be How could the power set contain anything that is not already in the set of all sets This paradox was nally resolved in several different ways by essentially eliminating the troublesome notion of the set of all sets77 which was ultimately seen to be an illde ned concepti 214 Explicit Bijections The most direct method for establishing that two sets are equinumerable is to construct an explicit bijective mapping from one to the other the direction being irrelevanti We now demonstrate this technique for several countably in nite sets 330 more formally the notation should be 01A 22 CHAPTER 2 MATHEMATICAL PRELIMINARIES Theorem 6 The set of all odd natural numbers has the same cardinality as N Proof De ne a function f z N A l35 l l by 2n 1 Then f is surjective because n 7 l2 is a natural number for all n E 135Hll Also f is injective because implies that 2i 1 2j l or i jl It follows that f is a bijection which implies that the sets are equinumerablel D Theorem 7 The set of all integers Z 7 2 7101 2 l l l is countable Proof De ne a function f z N A Z by n 1 142n1 Observe that for any k E N f2k 7k and f2k 1 k 1 Thus all even numbers are mapped to unique negative integers and all odd numbers are mapped to unique positive integers Furthermore since every integer is the image of some natural number under f it follows that f is a bijection so the sets are equinumerablel D It is interesting to note that 135Hl C N C Z where the set containment is proper yet all three sets are equinumerablel This counterintuitive behavior is in fact one of the distinguishing characteristics of in nite setsl We state this as a theorem Theorem 8 A set has an in nite number of elements if and only if it can be put into onetoone correspondence with a proper subset of itsel As a nal example we now show that even Cartesian products of sets do not yield bigger sets in the sense of cardinalityl This example also shows that it can be rather challenging to construct the desired bijectionl Theorem 9 The Cartesian product N X N X N is countable Proof We shall prove this by constructing an explicit bijection f that maps N X N X N onto Nl Note that for the purposes of this proof we could just as well construct the mapping in the other direction from N to N X N X N the choice is simply a matter of convenience Our construction will be broken into four steps Step 1 Partition the set N X N X N into nite subsets de ned by Pni17y72ENgtltNgtltN zyzn The sets P0 P1 P2 l l l then partition the lattice of 3D integer points N X N X N into a countable number of diagonal slices each containing only a nite number of points Moreover each point ij k is in exactly one of the slices namely Pn where n i j 21 ELEMENTS OF SET THEORY 23 Step 2 Assign the numbers 0 1 21 l Pnl 71 to the elements of Pn using some wellde ned ordering we shall use lexicographic ordering which is easily de ned on the integer triplesi That is we de ne 1 7 y yz lt 7971 to mean z ltz or 11 andy lty or z z y y and 2 ltzi Of course the last condition will never occur when comparing two points that belong to the same slice Pn because the constraint 1 y 2 n ensures that two such points that agree in both I and y are actually identicali Given a triple zyz E P what is its position in the ordered list To compute this number we count how many triples z y z come before zyz in the set P7 with respect to this orderingi First there are the cases in which 1 lt I In each of these cases there are n 1 7 1 possibilities for the remaining coordinates y and 2 given that z y 2 n and all coordinates must be natural numbers Summing this expression for all z E 0 121 1 7 1 we have 7 n1nn71n271WA In addition there are y possibilities for the case where z z and y lt y namely y 6 01 21 l i y 7 1 Therefore the mapping 12n7z3 ryyyz 7 y assigns a unique integer from the set 01 21 Pnl 7 1 to each triple in the set Pni Step 3 We now shift the counts within each of the sets Pn so that they are distinct from one another Since all the sets are nite we need only offset the elements of a given P7 by the number of entries in all the previous sets P0 P1 1 i i 13771 which is simply the number of triples z y 2 that satisfy zyz lt n We can compute this number directly by thinking of it as the number of distinct ways to place n 7 1 balls into four urns three of which represent 1 y and 2 Equivalently this is the number of distinct permutations of n 7 1 balls and three partitions where each contiguous sequence of balls represents the contents of one urni This number is given by the binomial coef cient n713 7 n2n1n 3 if Step 4 The bijection f z N X N X N 7gt N is then simply the sum of the above terms MW where z y and 2 are arbitrary natural numbers and n z y 2 D 24 CHAPTER 2 MATHEMATICAL PRELIMINARIES 215 The SchroderBernsteinTheorem Constructing an explicit bijection between two equinumerable sets can be very tedious as the pre vious example shows Fortunately the Schrb39derBernsteintheorem affords a much easier way to establish equinumerability requiring only the existence of injections not bijectionsi Before stat ing and proving this theorem we rst introduce some new terminology and prove several simpler theoremsi Theorem 10 Let A B and C be sets such that A 2 B 2 C If there exists a bijection f z A A C then there also exists a bijection g z A A Proof See appendix We now state and prove two different but equivalent versions of the SchroderBernsteintheorem since both forms are convenient The second form follows easily from the rst Theorem 11 SchroderBernstein7 I Let A and B be arbitrary sets If there exist injections f z A A B and g z B A A then there exists a bijection from A to B Proof Let A gB B fA and A gB as depicted in Figure All Then the function g o f is a bijection from A onto A Since A 2 A 2 A by theorem 10 we may assert the existence of a bijection h z A A AC Also since 9 z B A A is a bijection so is the inverse g l A A B It follows that 9 1 o h is a bijection from A to B which establishes the result D Theorem 12 SchroderBernstein7 II Let A andB be arbitrary sets If lAl g lBl and lBl g lAl then lAl Proof If lAl S lBl and lBl S lAl then by de nition there exist injections f z A A B and 39 B H Al The result now follows from theorem 11 D Using the SchroderBernsteintheorem we can now give a very simple proof of theorem 9 We need only demonstrate that there exist injections f z N X N X N A N and g z N A N X N X N The following functions suf ce MM 2315 2 92 2300 It is easy to see that both of these functions are injective so the result is established Note that any three relatively prime numbers suf ce for the construction of the function f above this follows from the fact that every integer has a unique prime factorization This is a common trick used to de ne injections from Nk to N Essentially the same strategy can be used to prove the countability of the rational numbers as we now show 22 ELEMENTS OF LOGIC 25 Theorem 13 The set of rational numbers Q is countable Proof For every 4 E Q there exist unique integers k and m such that k 2 0 k and m are relatively prime and q k ml We use this fact to assign a unique natural number to each rational number De nesz A be f i 21637 ifmgt0 q 7 2k5 m otherwise where q km k 2 0 and k andm are relatively prime ie the fraction is in lowest termsl Because k and m are unique f is an injection from Q to N Because N C Q the identity map is an injec tion in the other direction By theorem 11 these injections imply that the sets are equinumerablel D 22 Elements of Logic In this section we review the basic concepts of propositional or Boolean logic Propositional formulas also known as Boolean formulas play a very fundamental role in computer science s we shall see determining whether such a formula can in fact be satis ed is an intractable problem and lies at the foundation of the theory of NPCompletenessl We shall also nd the formalism of propositional logic to be useful in other contexts as well such as in formulating precise statements and proving theorems For more extensive discussions of propositional logic see Nerode and Shore and Davis et all A proposition is a statement that is either true or false such as the moon is made of green cheese l Propositional logic deals with symbolic A 39 of A A t and quot 39 among theml The propositions themselves are typically denoted by single letters such as I y 2 often with subscripts which are called boolean variables or propositional lettersl4 We shall denote the truth values true and false by the symbols T and l respectivelyl Propositional formulas are built up by combining boolean variables and constants using parentheses and logical connectives which are summarized belowl5 1 is negation 2 A is conjunction which means and 3 V is disjunction which means inclusive or 4 D is material implication 4The terminology propositional letters emphasizes the fact that boolean variables are atomic in that their com ponent symbo s carry no independent meaning Thus even though boolean variables are frequently comprised of multiple symbols such as subscripts they can nevertheless be thought of as single symbols or letters within a ni e alphabet 5The symbols that we use to denote the logical connectives is fairly common but unfortunately there is no universally accepted notation For example one sometimes sees conjunction denoted by or 85 and negation denoted by 7 or 7 It is also quite common to see either 4 or gt used instead of D for material implication and either t or ltgt used instead of E for material equivalence 26 CHAPTER 2 MATHEMATICAL PRELIMINARIES 5 E is material equivalence All of the connectives are binary relations iiei taking two arguments except for negation which is a unary relation The modi er material used for the implication and equivalence connectives above af rms that the connectives are concerned only with the truth values of the formulas they relate not with their forms or their meanings this is so with all of the connectives Material implication and equivalence are therefore weaker than the corresponding notions that one might employ in everyday speec For example the statement circles are round implies that six is even is true if implies is taken in the material sense since both the premise and the consequent are true However the evenness of six is in no way a consequence of the roundness of circles so we would not assert that one implies the other according to the common usage of the word Here are some examples of boolean formulas z A y 2 w v y 21gt z 2 y 3 w v y 22gt x v y 3 as A w v ex Ag 23gt 11 12 V zg n11 V 14 V zg 24 Each of the formulas above contains a number of subformulas lnformally a subformula is a wellformed formula wff appearing within a formula For instance formula 23 contains the subformulas I y I V y I y etc We can de ne precisely what a wellformed boolean formula is modulo some redundant parentheses as follows Let V be a set of boolean variables this may be an in nite set Then the set W of wellformed propositional formulas over V is de ned by the following rules 1 V C W 2 uEW gt nuEW 3 uv E W gt u o v E W where o is any of the binary logical connectives 4 No other strings of symbols are in W Note that we are using gt as a metasymbol that also denotes implication which in this context is an assertion that is a statement that is necessarily true6 Similarly the metasymbo ltgt is frequently used as an assertion that two boolean formulas are equivalent that is they produce the same values given the same truth assignments for their variables For example I V r ltgt T The metasymbols gt d ltgt are never part of a boolean formula rather they are used to make statements about boolean formulas hence the modi er meta i It is customary to omit many of the parenthesis that the above rules would include For example we normally do not include parentheses enclosing the entire formula so we write I y rather than IAy Also because of the 39 quot quot of both 39 39 and quot 39 quot see section 222 it is 6Conventions vary as to which symbols are the connectives and which are the metaesymbols See footnote 5 en examining unfamiliar literature be sure to rst understand all such conventions that are emp oye V 22 ELEMENTS OF LOGIC 27 customary to omit the parentheses in formulas such as IAy 2Aw and write szAzAw insteadi Similarly we write z rather than z and by assuming that n has higher precedence than the other connectives we may write r y rather than r Note that we have employed these conventions in formulas 21 through 24 The rules de ned in the previous section specify only the syntax or form of boolean formulas not their meanings To specify the meanings we rst need the meanings of the logical connectives themselves which can be completely de ned by a truth table The following truth table speci es the values resulting from each of the connectives given all possible truth values of the arguments which appear in the two leftmost columnsi Here we have also included de nitions for the symbols T and l which denote mmd a contraction for not and and nor a contraction for not or respectivelyi7 I C H C H C H C 919 T i T T T L T L L L AAPPH dhdk PPAA AFFPgt 444Plt Akaau aeeam The truth values of more complex formulas are found by repeated application of these de nitions beginning with the values of the variables themselves In fact truth tables can also be used to determine the value of a boolean formula as a function of its variables For example consider formula 21 We rst list each subformula across the top of the table organizing them in such a way that every subformula of an expression appears in a column to its left Then we can easily ll in the table working lefttoright and toptobottom by applying the de nitions of the individual logical connectivesi We obtain the following table z y sz r y zv y szE zV y L L L T T T L L T L T L T L T L L L T T L T T T L L L L In this particular instance we see that formula 21 which appears above the rightmost column of the truth table is unsatis able as all of the resulting values are false When one or more of the entries in a column is true the formula is called satis ablei For instance in the table above we see that each of the subformulas is satis ablei Using similar truth tables it is easy to verify that formulas 22 and 23 are valid which means that they always result in true regardless of the values assigned to their variables and that formula 24 is satis able but not valid Another more compact way to construct a truth table is to associate a column of truth values with each variable and connective in a single formula After assigning all possible truth values consistently to the variables we then ll in the columns associated with the connectivesi For example such a truth table for formula 22 would look like this 7Another symbol commonly used in the literature for nand is the Vertical bar as in z 28 CHAPTER 2 MATHEMATICAL PRELIMINARIES aeaalt AAPFH aeeam dhdk aaaau FFAAJ AAPFH 4k4ke This truth table demonstrates that formula 22 is valid since the pn39ncz39pal connective the one that is applied last 3 in this case always results in T See Carnap for further discussion of this type of truth table 221 Truth Assignments and Satis ability A truth assignment is a function V V A T L where V is a set of boolean variables That is V associates a truth value true or false with each variable in V We say that a truth assignment V is appropn39ate for a boolean formula 7 if every variable that appears in f is assigned a truth value by V The meaning of V can be extended to boolean formulas over V by means of the following de nitions 7 T if Vu T and Vv T 1 Vltu A v T L otherwise 7 T if Vu T or Vv T 2 Vltu V v T L otherwise 7 L if Vu T 3 VltTugt T T otherwise 7 L if Vu T and Vv L 4 Vltu D U T T otherwise if Vu Vv otherwise avwgm1 To handle extra parentheses we could of course introduce another explicit rule This provides a convenient formal de nition for the truth value of a boolean formula given the truth values of the underlying variablesi Think of these rules as providing an algorithmic alternative to a truth table indeed each of these rules corresponds very closely to a function that one would use say in a Lisp environment to recursively evaluate a boolean formulai With the notion of a truth assignment thus extended to arbitrary boolean formulas we identify a number of important special types of formulas each with its own terminology and notation These types are summarized below where 7 denotes an arbitrary boolean formula V denotes a truth assignment that is appropriate for f and l and W797 are new metasymbolsi In several cases the terminology column lists multiple phrases that are used synonymouslyi 22 ELEMENTS OF LOGIC 29 terminology notation meaning V veii es 7 V satis es 7 V l 7 V7 T V is a model for 7 V falsi es 7 V l7 7 V7 L V is satis able V7 T for some truth assignment V 7 is falsi able V7 L for some truth assignment V V17 T and V27 L for some i t39 t f ls um myen truth ass1gnments V1 and V2 7 is a tautology 7 is valid 7 is a contradiction 7 is unsatis able l7 f f Vf T for all truth assignments V V7 L for all truth assignments V Note that a contingent formula is one that is both satis able and falsi able or equivalently neither a tautology nor a contradiction Using the new notation we can now precisely state the relationship between the logical connectives D and E and their corresponding metasymbols gt an ltgt when the latter are applied to boolean formulas Speci cally if u and v are boolean formulas 1 We write u gt v if and only if l u 3 v 2 We write u ltgt v if and only if l u E 1 Thus the metasymbols implicitly refer to all possible truth assignments appropriate to the formulas involved For this reason metasymbo s are frequently used in the statement of theorems which typically assert the validity of some implication or equivalence For example the transitivity of material implication is asserted as I 3 y y D 2 gt I D 2 25 which is equivalent to asserting that l 3 y y D D I D 26 This latter fact can be easily demonstrated using a truth table 222 Elementary Theorems Listed below are a number of fundamental properties of the logical connectives These properties allow us to perform certain manipulations on boolean formulas to obtain equivalent often simpler formulas Each of these properties can be easily veri ed by replacing the metasymbol by the corresponding logical connective eg replace ltgt with E and then using a truth table to establish the validity of the resulting formula 30 CHAPTER 2 MATHEMATICAL PRELIMINARIES 1 z y ltgt y z commutativity of conjunction 2 I V y ltgt y V I commutativity of disjunction 9 1 ltgt z z idempotence of conjunction F I ltgt I V I idempotence of disjunction 5 z E y ltgt y E z commutativity of material equivalence 533 z y 2 ltgt z y 2 associativity of conjunction 7 I V y V 2 ltgt I V y V 2 associativity of disjunction 00 i z y V 2 ltgt z y V I 2 distributivity of conjunction over disjunction 50 I V y 2 ltgt I V y I V 2 distributivity of disjunction over conjunction H O i z y ltgt r V y De Morgan7s law H H i z V y ltgt r y De Morgan7s law H E0 z ltgt 1 law of double negation H 9 1 3 y ltgt r V y principle of material implication H F I E y ltgt z y V x y principle of material equivalence H 5 z 3 y y D 2 gt z D 2 transitivity of material implication H 533 z E y y E 2 gt z E 2 transitivity of material equivalence H 7 z 3 y y D I ltgt z E 2 double implication is equivalence H 9 I y D 2 ltgt z 3 y D 2 principle of exportation H to i z 3 y ltgt y 3 x principle of transposition for material implication N O z E y ltgt x E y principle of transposition for material equivalence Note that material implication and material equivalence can always be replaced by equivalent for mulas containing only the connectives A V and thus the material connectives are included only as a convenience not for their expressive power 223 Normal Forms A boolean formula is said to be in conjunctive normal form abbreviated CNF if it is expressed as a conjunction of zero or more disjunctions that is a conjunction of zero or more clauses Where each clause is itself a disjunction of zero or more literals A literal is a boolean variable the negation of a boolean variable or one of the constants T or L An example of a formula in CNF form is zV sz zV wAwA z 2 7


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.