### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Computational Complexity COT 6410

University of Central Florida

GPA 3.74

### View Full Document

## 27

## 0

## Popular in Course

## Popular in Engineering and Tech

This 50 page Class Notes was uploaded by Lamont Block on Thursday October 22, 2015. The Class Notes belongs to COT 6410 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 27 views. For similar materials see /class/227694/cot-6410-university-of-central-florida in Engineering and Tech at University of Central Florida.

## Similar to COT 6410 at University of Central Florida

## Reviews for Computational Complexity

### 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: 10/22/15

Problem Subset Sum Given A set S S1 s2 sn for n 2 1 ofpositive integers and an integer B Question Does there exist a subset of S whose items sum to B Denote an instance ofthis problem by a Boolean variable SSs1 s2 s B which is true if and only if there exists a subset of the values s1 sz sn that sum to the value B Notice when n 1 we de ne SSs1 sz S B to be true exactly when B sn Theorem For n 2 2 SSs1 sz S B is true ifand only if SSs1 sz sn1 B or SSs1 sz sn1 Bis is true Proof First suppose for some arbitrary instance that SSs1 s2 s B is true By the de nition there is a set A g S S1 sz sn so that the sum ofthe items in A is B Either A contains s or it does not If sn 6 A then the sum of the items in A7sn must be Bis Therefore since A7sn g S1 sz sn1 SSs1 sz sn1 Bis is true On the other hand ifsn e A then A g S1 sz sn1 Therefore SSs1 sz sn1 B is true That is at least one of SSs1 sz sn1 B or SSs1 sz sn1 Bis is true Now assume the right hand side of the statement is true That is at least one of SSs1 sz sn1 B or SSs1 sz sn1 Bis is true If SSs1 sz sn1 B is true then from the de nition there is a subset A ofsl sz sn1 whose elements sum to B Since s1 s2 sn1 is a subset of s1 s2 s by transitivity of set inclusion A is a subset of s1 sz sn Therefore SSs1 sz S B is true Now suppose SSs1 sz sn1 B7 s is true Then by de nition there is a subset A of s1 sz sn1 that sums to Bis Since A does not include S the elements in A U sn sum to Bisn l Sn B Since A U sn is a subset ofsl sz s SSs1 sz s B is true and completes the proofof the theorem v L1 L2 L3 X Y I Z D E C I R Sorry this is intended to be the same picture as in the document I sent last evening I have given labels to every vertex The top and bottom verteX are actually the same verteX The L vertices are U and quotU barquot vertices as described in the document This is just thequotgadgetquot for one clause For each clause there is a similar gadget and all have vertices R and C in common They also share Li vertices when the clauses have a common variable In any proper coloring of this gadget 3 colors or not we may assume R has a color and specify it to be 3 We know C will receive a color it can not be 3 but it can be any other color we want So we will arbitrarily choose it to be 1 We also know each Li will have a color and it will also not be 3 but we can not say what or how many at this point Lemma 1 Ifa gadget is 3colorable then at least one of L1 L2 or L3 must have the same color as C that is colored 1 Proof Suppose not Then we may assume the color of L1 L2 and L3 are all 2 Then X and Y must be colored 1 and 3 it doesn39t matter which is which and hence Z must be colored 2 Now Z and L3 are both colored 2 By the same argument D and E must be colored 1 and 3 Again it doesn39t matter which is which Finally C must be colored 2 contradicting the color of C being 1 Theorem 2 If G the graph constructed from the given instance of 3SAT is 3 Colorable then the 3SAT instance is satisfiable Proof When G is 3colorable then each gadget is 3 colorable By Lemma 1 each set ofL1 L2 and L3 have at least one variable colored the same as vertex C Since C and R are common to all gadgets in G We simply say the color ofC is 1 TRUE Then every gadget has a TRUE label color on at least one of its three Li vertices Thus in the instance of 3SAT from which G was constructed every clause has a TRUE variable hence a satisfying assignment Theorem 3 Ifa 3SAT instance is satisfiable then the graph G constructed as above is 3colorable Proof Suppose the instance of3SAT has a satisfying assignment Then every clause has a true variable Color the corresponding Ui and quotUi barquot vertices in G with TRUE or FALSE as determined by the satisfying assignments Then in each gadget at least one ofits Li vertices is are colored TRUE We may arbitrarily color verteX C with TRUE and verteX R with color 3 Now we must show it is possible to properly color the remaining vertices of G with at most 3 colors TRUE FALSE and 3 Since R C and the U and quotU barquot vertices are already given an assignment we need only show the coloring for X Y Z D and E in the clauses Further by considering an arbitrary assignment with at least one TRUE for the Li vertices it is sufficient to show a 3 coloring for one clause since their colorings are independent of each other First suppose either or both ofL1 and L2 is are TRUE Then it is possible to color X and Y FALSE and 3 and it doesn39t matter which since either forces us to color Z TRUE Now Z andor L3 is TRUE As before it is possible to color D and E with FALSE and 3 which is consistent with C being colored TRUE Thus the gadget is 3colored Hence all gadgets can be 3colored and G is 3colored 3 Together Theorems 2 and 3 give Theorem 4 G as constructed is 3Colorable if and only if the 3SAT instance is satisfiable Corollary 5 Graph 3Colorability is NPComplete Corollary 6 Graph kColorability is NPComplete Note It is possible to make Lemma 1 quotifand only ifquot That would simpli l the proofof Theorem 3 a little I had already proven Theorem 3 before I noticed that 3 DM Instance A positive integer q a set of 3q distinct objects partitioned into three sets of q objects W X and Y And a set ofs quottriplesquot ofthe form a b c where a e W b e X and c e Y Question Does there eXist a subset of exactly q triples containing all of the 3q objects 3 SAT 3 DM 37DM is clearly in NP Consider an arbitrary instance of37SAT U u1 uz um and a set ofm clauses C1 C2 Cm Each C contains exactly 3 variables of the form u or u Construct W to be uiLi u iLi l for l S i S n and l Sj Sm Note u1l u12 u1n all correspond to Boolean variable ui While u 1l u 12 u 1n all correspond to the complement of u Later triples corresponding to Boolean variables in say clause j will force us to quotselectquot a triple containing uiLi If u also appears in clause k we must also select the triple containing u k etc Then of course none ofthese triples can ever force us to select u Li But since u j and u k etc is a member of W it must be selected in some triple We rst need a set of triples that select either all or none ofu1l u12 u1n and none or all ofu 1l u 12 u 1n These are the T triples uim ajl bLi and u Li aj bLi for 1 Si in and l Sj Sm Note Whenj m above jl cycles to be l as and b will not appear elsewhere Observations 1 If any uiLi is selected then u k for l S k S m must be selected and no u k can be selected 2 If any uiLi is NOT selected then u k for l S k S m CAN NOT be selected and EVERY u k must be selected Satisfaction We need a set of triples Whose selection corresponds to a clause and assigning one of it s Boolean variables to true Suppose clausej is um u 7 u zs Create the following three triples and new objects sl s and sz s which do not appear elsewhere u10U7SIU7SZU VDl SID SzUl uizslll SID SzUl Thus we must select exactly one of these three Create the corresponding triples for each clause of 3SAT We now have W uiLi u iLi l 1 Si S nand l Sj Em and lWl 2mn XajllSiSnandlSjSm s1UllSjSmanlelmnm YbiLillSiSnandlSjSm szmllijim andlYlmnm Let q equal 2mn Theorem An instance of 37SAT is satis able if and only if there are le triples that can be selected so that every object in X and Y are selected exactly once each and no object in W is selected twice But this is not quite 37DM Exactly mnm triples have been selected the number of objects in each ofX and Y So there are mnim objects inW that have not been selected We need to add mnim objects to each of X and Y and suf cient triples to make sure the mnim unselected objects in W can be selected by exactly mnim triples We can do this by adding g1k to X and g2k to Y for l S k S mnim Now add triples for l S k S mnin uiUg1k7g2kf0r1 SiSn and 1 Sj Sm and u iL g1k g2k for 1 Si in and l Sj Sm We can select exactly mnim of these to cover any set of mnim unselected W objects LOWER BOUND THEORY Searching ordered lists with Comparison Based Algorithms ComparisonBased Algorithms Information can be gained only by comparing keyitoi element or elementitoielement in some problems Given An integer n a key and an ordered list of n values Question Is the key in the list and if so at what index We have an algorithm We don t know what it is or how it works It accepts n a key and a list on n values That s it It MUST though work pretty much as follows 1 It must calculate an index for the rst compare based solely upon n since it has not yet compared the key against anything ie it has not yet obtained any additional information Notice this means for a xed value of n the position of the rst compare is xed for all data sets of size n 2 The following is repeated until the key is found or until it is determined that no location contains the key The key is compared against the item at the speci ed index a If they are equal the algorithm halts b If the key is less then it incorporates this information and computes a new index c If the key is greater then it incorporates this information and computes a new index There are no rules about how this must be done In fact we want to leave it wide open so that we are not eliminating any possible algorithm After the rst compare there are two possible second compare locations indexes Neither depends upon the key or any item in the list Just upon the result of the rst compare Every second compare on every set of n items will be one of these two locations Every third compare will be one of four locations Every fourth compare will be one of eight locations And so on In fact we may look at an algorithm for a given n as being described by or possibly describing a binary tree in which the root corresponds to the rst comparison it s children to the possible second comparisons their four children represent the possible third comparison etc This binary tree called in this context a quotdecision treequot then depicts for this algorithm every possible path of comparisons that could be forced by any particular key and set of n values Observation 0 Every comparisonibased search algorithm has it s own set of decision tree s one for each value of n 7 even if we don t know what or how it does its task we know it has one for each n and are pretty much like the one described above Observation 1 For any decision tree and any rootileaf path there is a set of date which will force the algorithm to take that path The number of compares with a given data set key and n values is the number of nodes in the quotforcedquot rootileaf path Observation 2 The longest rootileaf path is the quotworst casequot running time of the algorithm Observation 3 For any position i of 1 2 n some data set contains the key in that position So every algorithm must have a compare for every index that is the decision tree must have at least one node for each position Therefore all decision treesifor the search problemimust have at least n nodes in them All binary trees with n nodes have a rootileaf path with at least l logznl nodes you can verify this by induction Thus all decision trees de ned by search algorithms on n items have a path requiring l logznl compares Therefore the best any comparison based search algorithm can hope to do is logzn m l logznl l This is the comparisonibased lower bound for tlre problem of searching an ordered list of n items for a given key Comparison Based Sorting Here there is no quotkeyquot Typically in comparisonibased sorting we will compare values in two locations and depending upon which is greater we might I do nothing 2 exchange the two values 3 move one of the values to a third position 4 leave a reference pointer at one of the positions 5 etc As with searching above each sorting algorithm has its own decision tree Some differences occur Leaf nodes are the locations which indicate quotthe list is now sortedquot Internal nodes simply represent comparisons on the path to a leaf node As with searching we will determine the minimum number of nodes any sorting algorithm comparisonibased must have Then from that the minimum height of all decision trees for sorting can be determined providing the proof that all comparisoni based sorting algorithms must use at least this many comparisons Actually it is quite simple now Every decision tree starts with an unordered list and ends up at a leaf node with a sorted list Suppose you have two lists one is a rearrangement of the other Then in sorting them something must be done differently to one of the lists done at a different time Otherwise if the same actions are performed to both lists in exactly the same sequence then one of them can not end up sorted Therefore they must go through different paths from the root of the decision tree By the same reasoning all n different permutations of the integers l 2 n these are valid things to sort too you know must go through distinct paths Notice that distinct paths end in distinct leaf nodes Thus there must be n leaf nodes in every decision tree for sorting That is their height is at least logzn By a common result one of Sterlings formula s logzn m nlogzn Therefore all comparison based sorting algorithms require n10 gzn time Theorem 1 3 Colorability is NP Complete Proof Given a YES instance of 3 Colorability and a 3coloring of the vertices is easy in polynomial time to verify the instance is YES Thus 3Coloribility is in the set NP In order to transform 3SAT to 3colorability we have to construct a graph of nodes and edges which is 3colorable if and only if the given instance of 3SAT can be satisfied This means we need a graph that can be 3colored only when a corresponding expression evaluates to true For this example the three colors are TRUE FALSE and OTHER To construct the graph start with a node named root that is colored OTHER Also for every variable x in the expression create a pair of nodes x and x This pair is connected to each other and to the root to create a triangle for each variable root OTHER 0 l l 7 7 l l 7 l l 7 l l OO OO OO X X y y Z Z If this graph is to be 3colorable each of the variable nodes must be colored TRUE or FALSE With this graph in place add gadgets for every clause containing the literals 1 1 and 1 where a gadget is 1 o l l 1 o o l l 1 o o o C root TR UE OTHER 2 Note that 1 node c is a single vertex and is common to all gadgets and is either colored TRUE or FALSE and 2 all the literals on the left are also connected to the root node as shown in the first picture Lemma G is 3colorable if and only if the color of node c agrees with the color assigned to at least one of the three literal nodes in every gadget This gadget is a three input OR gate If it is 3colorable it demands that one of the inputs on the left is colored TRUE For example if the expression consisted of the clause x y z the graph would look like this l root o pl 7 l l 7 l l p l l o o o o o o l X X y y Z Z l l l l l l l l O O l l l l l l l l o l o o c O This is the finished graph for x l y l Z If we can find a way to 3color this graph we have also found a way to satisfy the Boolean expression The process of 3coloring this graph is just as complex as 3 SAT ie 3 Colorability is NPcomplete Theorem 2 kColorability is NPComplete lt man References taming 1lbymyemu quot m Maui fmm km Dh md m D Arun Kulshreshth c T 6410 Complexity Theory Department of Computer science 8 UCF April 9 2009 I t f Gutiifnii Q Introduction 0 Grain and Orientations 0 Methods to Reconstruct Grain Maps Background 0 3DXRD 0 Projection Geometry 0 Representation of Grains and Orientations Reconstruction Problem 0 Single Grain reconstruction 9 NP Completeness 0 0 1 Integer Programming 0 Proof of NP Completeness 9 Summary I Introduction r I d Fleccnsln ticn P NPrComplet ms 5man Referenie i th ng Q Introduction Reconstruction NPrkomple n 0 Many materials natural or artificial are found in crystalline forms eg metals ceramics minerals ice bones and drugs 0 As such crystalline structures are of basic interest to various branches of science including materials science physics geophysics chemistry biology pharmacy and forensic science o It is the crystal structure what governs many of the physical chemical and mechanical properties of a crystalline material Introduction ound Reconva i Surging Dimi j39n 0 Most crystalline materials are polycrystals ie they are composed of an assemblage of crystals called grains or crystalites 0 Each grain can be associated with one orientation which describes how that grain is oriented in 3D space relative to a fixed coordinate system 0 Undeformed specimen the lattice within each grain is typically near perfect ie each element has nearly same orientation 0 Moderately Deformed specimen orientations within a grain will vary within a certain orientation range around the so called basic orientation I Introduction Reconstruction F blem NPCompleten umm References is Gran e r ll A labeling coloring of a polycrystalline specimen where each grain is represented by a color according to its basic orientation I Arun Kulshreshth 31mm Rmmme l im lt2 Introduction 5 roun 39 ti mv Meme 7 Mg r i Construct Grain Maps 0 Surface probes such as optical and electron microscopy EM 9 Drawback o destructive in nature a rule out any study of the dynamics of the individual grains during typical processes such as annealing or deformation 1L mantax mm Mass 7 Mg i s39truct Grain Maps 0 Surface probes such as optical and electron microscopy EM 9 Drawback o destructive in nature a rule out any study of the dynamics of the individual grains during typical processes such as annealing or deformation 0 Three dimensional X ray diffraction 3DXRD microscopy 0 Developed at European Synchrotron Radiation Facility ESRF 0 Non destructive in nature 0 Uses high energy monochromatic X rays and the physical phenomenon known as diffraction I H e m immatva gamma 0 One of the three argest and most powerfu synchrotrth In the wor I Introduction vol d F ccnsln ticn Problem NP on as Eummam are 3 Ref a x wildm as39 mmz em wad i th ng Background 3931313 7 3pm Nondestructive imaging technique makes dynamic studies feasible 0 0 Uses high energy monochromatic X rays and the physical phenomenon known as diffraction O Exceptional penetration depth several mm s for steel and some cm s for aluminum 3D reconstructions can be performed by imaging multiple cross sections O o It produces an image of a 2D layer of the sample in the form of diffraction patterns called projections o Projections are recorded by a detector plate while the sample is rotated about an axis perpendicular to the X ray beam I F39tgure Sketch of the BDXRD exper39tmenta setup The Bragg ang e 29 the rotation ahghe w and the azimutha ahghe n are indicated for a part of the gra39m that g39hes rise to d39ttfract39torv The aboratory coord39mate system is g39nen as XYZ I o For every image pixel X7y its coordinates in laboratory coordinates are x7 y 2 o For a given point thhzl of the grain we can compute the associated diffraction point on the detector Lidanger as X xcosw 7 ysinw y xsinw i ycosw l ydet L XI tan20 SW77 VI zdet L 7 X tan20 cosn i z 356mm icymama 0 Let the total number of locations in the 20 area of interest sample layer be I 0 We assign to each location i1 i g I both a grain label i and an orientation oi 0 Grains are labeled by l E 1237 n where n the total number of grains is assumed to be known a priori o Orientations can be represented in various ways most common are representations in Euler angles Rodrigues vectors and unit quaternions These representations describe rotations in 3D space o Quaternion representation was used I Unit quaternions is a 4 tuple of the form q a7 b7 c7 c1 cos W2 7 W3 where the 3D unit vector n and the real scalar 4p are the axis and angle of rotation respectively Introduction ound Reconstruc39 n Problem NPrCompl ms w m xzm5gmlu i th mzo Q Reconstruction Problem 4L Reconstruction N Prkomp Stairs com commandos Single 0 O O 0 O 0 Lets consider the subproblem of reconstructing a single grain with known orientation 0 and grain label I and no deformation If we consider the whole image then at every pixel x7 y it either belongs to grain l or not Let p0 I7 0 be the assignment corresponding to the grain Let ox7 y be the density of the intersection between the grain and the illuminated layer For all pixels except those at the boundary we expect either pupo orpo0 The pixelated values are listed in the one dimensional array X For each reflected ray r the normalized intensities are saved in array b I Introduction 5 roun Reconstruction Pro em N Pr Co W 613 tmmmmm There is a linear relationship between density and intensity and it can be derived from equation For each reflection r we may write A X b 2 where A comprises the information on geometry equation 1 Next we pile the A values for all the reflection into a block matrix A and define the compound array b as follows 3 Raning m e m tmiaimif i Hence we have the following equation for the reconstruction of single grain AX b 4 where A is a matrix of integers of size I x I b is a matrix of integers since intensities on detector are integer values of size I x 1 X is a vector of unknowns of size I x 1 NOTE Here I is the number of pixels in the 2D area of interest in sample and it is a variable chosen based upon the application Introduction E nd u Reconsan 39 1 Problem NPrCompletenss summaw Referen i th ng Q N P Com pleteness Introduction ound erconsln m A 1 P NPrCompletenss 5 We have the following o A is a matrix of integers of size I x I o b is a matrix of integers of size I x l o X is a vector of size I x 1 0 Each element of X is either 0 or p0 where p0 is a constant 0 X ix where X is a 0 1 vector We can ignore p0 for the purpose of solving the equations 0 Now problem reduces to AX b where A and b are as defined above and x is a 0 1 vector 0 This is an integer programming problem I INSTANCE Integer matrix A and integer vector b QUESTION Does 3 a 0 1 vector X such that AX b 0 Classical problem in combinatorial optimization 0 NP complete in general 0 3 SAT 0 1 Integer Programming Introduction ound Reconsan 1 m Pro NPrCompletenss Ref 7 Proof of P emplgeteness o It is easy to see that given the value of X it is easy to varify its correctness in deterministic polynomial time Hence this problem is in the set NP 0 Instance of 3 SAT 0 Variables U u1 u2 u3 u o Clauses C 5152 53 cm such that lcl for 1 g i g m 0 We have to construct an instance of 0 1 Integer programming a Boolean to arithmatic means true and means false 0 Let 0 denote false and 1 denote true 0 Place OR s between the variables 0 X1 l X2 7 X3 now means that X1 is true or X2 is true or X3 is false I Fleccnslmcticn Lm NPrCompletenss F Immam 2 7 mm F39NP Fleccnslruction lul NPrCompletenss F Immam 2 i ream ofNP 0 Points to remember for each expression row 0 Each has exactly one column of minimum value a This column corresponds to a nonsatisfying truth assignment 0 Every other column satisfies the expression a All other columnms have higher values 0 Construction of matrix A awan o n columns corresponding to variables in U o m rows corresponding to clauses in C 1 if uj e c 0 am 71 ifFJe c 0 otherwise I Introduction ound Fleccnslru 39I P m NPrCompletenss 5mm mi iii ax magi 1m 7 teams am The vector b bngtlt1 is merely made up of the appropriate minimum values plus one from the chart where the elements are defined as follows b l 7 the number of complemented variables in C f Proo fof P e pleteness a Assume that 3 SAT is satisfiable and let 1 U a T7 F be the satisfying truth assignment for C where T means true and F means false We can construct matrix A and vector b as described in the above construction Let us construct a vector X Xngtlt1 such that 1 Mm T 0 iftuF Xi Now if we multiply A and X then we will get a vector of size n where element i corresponding to clause c is of the form lX 1 i X2 i X3 which is always less than b because of the choice of b as described above Hence X is a solution to the 0 1 Integer Programming problem I Introduction oun 7 Proof at we a Assume that there does exists a 0 1 valued vector X such that AX b Now construct the truth assignment 1 of 3 SAT as follows t T ifX1 u F ifx0 The construction of A and b will force that each clause is satisfied If not then one of the values of the vector AX will be greater that the corresponding value in vector b which will contradict the assumption that AX b Hence 1 is the satisfying assignment for 3 SAT Hence 3 SAT and 0 1 Integer Programming are equivalent problems Since 3 SAT is known to be NP Complete 0 1 Integer programming must be NP Complete I Introduction 1 r ample nms Summam Refersquot i th m 9 Summary Referenze i o Crystalline substances are made up of grains governs many of the physical chemical and mechanical properties 0 3DXRD is a technique which uses high energy monochrmatic X rays and phenomena known as diffraction to determine the grain map of a polycrystal o Subproblem of reconstructing a single grain with known orientation leads to 0 1 Integer Programming problem 0 0 1 Integer programming is a NP complete problem 0 Reconstruction of grain maps is NP Complete I Vum man References HF Poulsen and Xiaowei Fu Generation of grain maps by an algebraic reconstruction technique J Appl Cryst 36 2003 1062 1068 R Karp Reducibility among combinatorial problems in Proceedings of a Symposium on the Complexity of Computer Computations Plenum Press New York 1972 85 103 AK Kulshreshth A Alpers G T Herman E Knudsen L Rodek and H F Poulsen A Greedy method for reconstructing polycrystals from three dimensional X ray diffraction data J Inverse Problems and Imaging Volume 3 No 1 2009 69 85 I Vum m in References L Rodek E KnudsenH F Poulsenand G T Herman Discrete Tomographic Reconstruction of 2D Polycrystal Orientation Maps From X ray Diffraction Projections Using Gibbs Priors Electronic Notes in Discrete Mathematics 20 2005 439 453 A Alpers H F Poulsen E Knudsen and G T Herman A discrete tomography algorithm for improving the quality of three dimensional X ray diffraction grain maps J Appl Cryst 39 2006 582 588 H F Poulsen Three Dimensional X ray Diffraction Microscopy Springer Verlag Berlin 2004 I int Juc39 n E ro Fleccnslru N P7 Compl n mam References R J Gardner P Gritzmann and D Prangenberg On the computational complexity of reconstructing lattice sets from their X rays Discrete Math 202 1999 45 71 B E Warren X Ray Diffraction Dover Publications New York 1990 HALTING PROBLEM 7 given a syntactically correct program P and an input string of characters X X may or may not be a valid input for P 7 it doesn39t matter 0 Question 7 does P halt when given X o P may loop forever or halt 0 So is there an algorithm for the Halting Problem 0 By way of contradiction we assume that there exists an algorithm here called Q which examines P X to report if P halts or does not halt on input X m input string X and program P Note P is just another strin I of 39 to Q Q P doesn t halt when P halts when given X given X Now build another program Q39 by changing 2 statements of Q I IfP halts on a IfP doesn t X then while halt on X 9 lt 10 do then no End loops 0P Lemma 1 If Q exists then Q exists P halts on X if and only if Q prints quotP halts on Xquot P halts on X if and only if Q39 loops forever P does not halt on X if and only if Q39 halts on P X 0 Build one more program S S reads a program P and duplicates P Then S calls Q39 with P P as input P cannot accept itself as input if and only if S halts That is P accepts itself as input if and only if S loops forever OOOO Q391 L IfP halts on ifP doesn t halt on P P then while 9 lt10 do then no 0p End loops Lemma 2 If Q39 exists then S exists Theorem 3 If Q exists then S halts on input P 0 iff Q39 halts on PP 0 iff Q39 writes out quotP does not halt on Pquot 0 iff P does not halt on P 39 II 0 Since S is a correct program we can replace P with S in Theorem 3 0 Theorem 3 If Q exists then S halts on input S 0 iff Q39 halts on S S 0 iff Q39 writes out quotS does not halt on Squot 0 iff S does not halt on S A contradiction Thus Q can not exist Cook39s Theorem De niton ofNP A decision problem H is in the set NP if and only if there exists a Non Deterministic Turing Machine NDTM M that when given an arbitrary instance X of H on the input tape of M will 1 Non deterministically place a string w e 2 on M s tape just to the left of instance X IfX e YH w will be the quotanswerquot to instance X ithat is sufficient information along with X to verify in step 2 below that X e YH Otherwise X e NH and the string w will be a random set of characters or empty we need not verify instances in NH If we can 7 fine but it is not necessary and 2 If X e YH deterministically and in polynomial time with respect to n le verify that X e YH and finally halt in state qy If X e YH i e X e NH the machine M may halt in state qN or it may compute forever 7 we are only guaranteed that M will not halt in state qy Notes We may interpret this as two Turing Machines acting sequentially The first is non deterministic and simply writes characters on the tape The second is totally deterministic and can but need not utilize the result of the first For certain problems in NP TM s eXist which ignore the quotanswerquot given by the non deterministic phase For eXample if H e P there is no need to eXamine the answer because a DTM eXists which can compute the answer within the required time In these case quotnoquot instances also can be correctly identified in deterministic polynomial time Further we can not simply terminate eXecution manually or automatically after some number of state transitions of an apparently quotloopingquot computation We usually don t know the eXact polynomial pn and therefore can never know when pn transitions have been eXceeded Completeness We first describe Completeness in terms of languages since that is the setting in which the terminology originated For any set of languages say X a particular language L e X may quotembodyquot the properties of all languages in X in the sense that for every language L e X all strings X e 2 can be transformed into strings fX so that X e L39 if and only if fX e L We call L the quotcompletion ofthe set Xquot that L is quotcomplete in Xquot or that L is or is in quotXiCompletequot For a language L to be XComplete l L must be in the set X and 2 all languages in X must be be transformable into L by a polynomial time per instance deterministic algorithm Notice that not all sets of languages must contain a complete language Some sets of languages can contain incomparable languages Analogously we say a decision problem B is NP omplete or in the set NP Complete if B 6 NP and all instances of every problem H 6 NF can be polynomially transformed into instances of problem B so that X e YH if and only if fX e YB Cook39s Theorem SAT is NP Complete For the following discussion H is an arbitrary decision problem in NP X is an arbitrary instance of H we assume valid instances of H are polynomially recognizable by a DTM and we assume the existence of a deterministic veri er M as described in step 2 above Then we will construct an instance of SAT that is true if and only if M when given input X results in M halting in state qy that is if and only if X e YH The details of the transformation will be described later these details also appear in Garey and Johnson pgs 3844 The instance of SAT fX will be constructed prior to any computation by M Therefore every instance X maps to an instance of SAT Actually both X and M are involved in the transformation but M is the same for every instance X so we can think of the transformation as being just a function of X All instances of X e YH cause M to halt in state qy Such instances will be mapped into satisfiable instances of SAT All other instances will be mapped to SAT instances which can not be satisfied That is all instances X e H which either cause M to halt in state qN or to loop forever Now we can claim 1 X e YH if and only if M halts on X in state qY if and only if fX e YSAT and 2 X e NH if and only if M halts in state qN or simply does not halt if and only if fX e NSAT Note we e ectivelyignore the complication that some instances in NIY might cause M to compute fbre ver Since they can not cause M to ternnna te in qy we siinplyinap them to instances in NSAT Therefore if the construction of SAT described neXt is correct SAT will be NPi Complete SAT Construction To construct instances of SAT we must define a set of Boolean variables and set of clauses that are consistent with our understanding of a given problem H an instance X and a deterministic verifier M The only properties we may assume are that H is a decision problem in NP and hence has a polynomial time deterministic verifier M and that X is a valid instance of H Therefore with n N there is a polynomial pn which bounds the computing time of M It also places bounds on other aspects of M and the transformation First notice that the alphabet and M are f1Xed for problem H Therefore their respective sizes are independent of the size of the instance X and hence are constants Alphabet Z s0 s1 sv where so is a special quotblankquot character which does not appear in the language of H It is used only as a marker by M Note Garey and Johnson use F rather than 2 States of M The states in M must include a start state qo and halt states q1 and q for halt quotyesquot and halt quotnoquot Thus we assume for some constant r 2 3 the states ofM are Q q0 q1 qr Tape cell contents and readwrite head position Initially at time zero the tape contains the given instance X X1XzXn Xi e Zis0 in quotcellsquot 1 2 n with the readwrite head initially positioned on cell 1 Within pn time transitions the head can never move more than pn positions to the right so we must have quotblank squot in cells n1 n2 pnl Cells to the left ofposition l i e cell 0 fl 72 7pn are lled by the nondeterministic quotanswerquot but will not exceed that needed by pn possible moves to the left So we need only keep track of tape cell contents and the position of the readwrite head for cells 7pn 7pnl pnl Notice this also implies the non deterministic answer for a yes instance can not be exponentially large Now we introduce a set of Boolean variables whose assignments corresponds to whether or not M when given string X is at time i in state j the tape head positioned at tape cell k and tape cell k contains character c for all times i states j tape cell positions k and characters c Variables At time i for 0 S i S pn Qi k 0 S k S r M is in state qk Hi j 7pn Sj S pnl The rw head is on cellj Sij k 7pn Sj S pnl39 0 S k S v The contents of cellj is sk This gives an order of 4p2n variables ie a polynomial number of variables with respect to n X Intuitively we will now construct clauses in such a way that allows forces these variables to have a satis able assignment consistent with M reading X and nally terminating in state q1 if and only if X e YH For eXample if X e YH M must be in the start state at time 0 and in state q1 at time pn So we could have clauses QO 0 and Qpn 1 In fact we will We could also have a collection of clauses Q0k for 0 lt k S pn since M cannot be in any ofthe other states at time 0 In fact we will not because there will be another set of clauses that will subsume this set But this is the general idea clauses will enforce a correspondence that can be satis ed if and only if they re ect the quotphysicalquot properties of a quotproperly runningquot Deterministic Turing Machine Other clauses will be produced which can be satis ed if and only if there is a sequence of state transitions head movements and tape contents that lead M to state q1 a property of M when given X e YH These clauses can not be satis ed for any instance in NH since M cannot then enter state q1 Clauses See Garey and Johnson pgs 4243 Conclusions Since SAT is NP omplete 37Sat is NPiComplete This in turn implies VerteX Cover is NPiComplete Hence Independent Set and Clique are both NP omplete We also can conclude that 1 if any problem H in NPiComplete can be solved in polynomial time be a DTM then all problems in NP can be solved in deterministic polynomial time ie P NP and 2 if any problem H in NPiComplete requires an exponential time DTM then all problems in NPiComplete require an exponential time DTM ie P i NP

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

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

#### "I made $350 in just two days after posting my first study guide."

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

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.