### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Foundations of Computer Science CS 301

CSU

GPA 3.51

### View Full Document

## 5

## 0

## Popular in Course

## Popular in ComputerScienence

This 15 page Class Notes was uploaded by Betty Kertzmann on Tuesday September 22, 2015. The Class Notes belongs to CS 301 at Colorado State University taught by Staff in Fall. Since its upload, it has received 5 views. For similar materials see /class/210194/cs-301-colorado-state-university in ComputerScienence at Colorado State University.

## Popular in ComputerScienence

## Reviews for Foundations of Computer Science

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

Undecidability Recall that 2 represents a countable number of strings over a nite alphabet All possible languages would be every poi lible arrangement of string which is the power set of 2 and is uncountany in nite What does this mean While there are a countable number of regular context free context sensitive and Turing acceptable languages there are languages outside this domain There are problems for which no solution exists Slide Lecture 15 7445 The Halting Problem Does some TM program contain an in nite loop This is a problem for which no solution exis s Proof We attempt to construct a Universal Testing Program which takes an arbitrary program P of some language and answers this question Does there exists an input W such that P loops inde niter on W Slide Lecture 15 7446 Assume we have a TM D which decides the halting problem It takes as input the description of the Turing machine Delta T and the input to the Turing machine DeltaT Halls and answers quotyesquot if T halts on input X Halls and answers quotnoquot if T loops on input X Slide Lecture 15 7447 We are interested in a special case where the input is also the program description Delta 1 DeltaT DeltaT Slide Lecture 15 7448 WC can construct a TM E which is composcd of D plus statcs to copy Dclta T E TAKES AND GENERATES AND TURNS CONTROL OVER TO quotDquot Slide Lecture 15 7449 Fi Hal ly st atcs Halls and answers quotyesquot if T halts on DeltaT Halls and answers quotno on DeltaT if T loops wc modier E slightly to obtain E3 WC add two now If T loops on Delta T cntcr statc 1 and halt If T halts on Delta T cutor statc 1 and loop Now lct T E run E on itsclf Slide Lecture 15 7450 Equot Halts if Equot Loops A CONTRADICTION Equot loops if Equot halts Slide Lecture 15 7451 WC could also do this in PascalCLisp cth Lot P ho our tost program PP If P halts P loops If P loops WP halts PP If P halts WP loops If P loops WP halts Slide Lecture 15 7452 179174 91 61111061 spas 1111 31191111111101013110N 1a 110 01111213100c1 011111 11a1111011 10d 0111111N div 1111 011g11111111010q 1a 110 01111213100c1 011111 11a1111011 10d 01111111 d pmH dN p112 3131dmoO dN dN P Ia d 9174 91 WEST aPEIS quot011111313111 011219 01111131 12 1111111 01111111100 111120 0m 113111111 0112 010111 0011100 10 1113 39111211 S011111012111 011210 0111111 1112 91001 f 011011101 0m 11 112111 m011gt1 0m 001110 0011111012111 011210 0111111 10 11101110111 12 111101 S1111 11101110111 01111151111 0111311 2011111012W 31111111 112111 1012 0111 110 131101I01 100111 S1111 0011100 10 Martin The class P is the set of all languages L that can be accepted in polynomial time There exists a TM T and a natural number k so that the time complex of T on an input of length n is Outquot The class NP is the set of all languages L that can be accepted in nondeterministic polynomial time by a Nondeterministic Turin 6 machine r Slide Lecture 15 7455 All languages accepted in P time are decided in P time All languages accepted in NP time are decided in NP time Let Fn represent the maximum polynomial time required to accept any string of length 11 Run the TM for time 2Fn If the string is not accepted it is reje tedl Slide Lecture 15 7456 All NP time computations carried out by a Nondeterministic Turing Machine can be expressed by a Boolean Expression with a polynomial number of variables Slide Lecture 15 7457 Let H be true if the tape head is at cell l at time t Let QM be true if the TM is in state 13 at time t Let SM be true if the TM reads symbol 7k at time t Since time is polynomial and the number of states and input symbols is constant the space of H X QX S is polynomial Transitions can be written QM Htt3tk 2 Quay Ht1t39 ASHJJV Slide Lecture 15 7458 There are other constraints EC The machine must be in 1 of 939 states at each time step ow AQTJAQTMQJ QM Amme l V mAQimAQmem i V mAmAmuomn But these constaints are all polynomial See Martin pages 436 to 442 for the DETAILS Slide Lecture 15 7459 Given a speci c input string there is a way to assign values 0 1 to the resulting Boolean Expression so that it evaluates to true IFF the Turing Machine accepts the input string Thus every problem in APP can be empress as a Boolean Sotis obilrty problem In other words Cook s Theorem Boolean Sotis obilrty problem SAT is NP Complete Slide Lecture 15 7460 ZQ 91 WEST aPEIS uxoldumo 011111 121111011X10d 1111111 31111111111103 011111312 311111111 12 S1 0110111 quot3391 39011111 121111011X101I 111 1301111111103 oq 11123 011011111 7 3 r 11 7 3 r 112111 1pm 3 e 3 1101131111 12101 a 11 010111 11 67 01 olqponpm mugImmouhilod oq 01 p192 1 7 K101111301Ig01 3 pm 3 111 Soi mi ml oq 67 p111 7 p111 gloqnqdln 011111 oq Z3 p111 lg 101 Kunmmg 0mm 917 91 31n13339l SPEIS uhqy zggng unopog 01 999717291 d M 111 111011101111 X10111 112111 Km mm 01111111 111 111011101111 X1111qngg1mg 111201003 12 gm poggmdxo oq 11123 d M 111 11101110111 mom 031113 L llgl 112011 II HIGIqOId S ll 9011109 911111 11 393111121111211 momma 11312 110 01111211 130111103 0111 913111 K111231312111 W1 311g1111111111p110 0111 39011111312W 311111111 311g1111111111p110 1a q 01111113 111 130111011 0gp g1 qunysung umloog We use the notation L lt30 L2 to indicate L is polynomial time reducible to L24 Slide Lecture 15 7463 A language L 6 2 is NP hard if for every language L 6 MP L lt L If language L is NP hard and L 6 IVP L is NP Complete Slide Lecture 15 7464 99 91 31n13339l SPEIS 0101111110063 g 1V3 911111 131112 dJV 3 1V S l 01111111111010p110g a q SOIq QH KZA 0 ILXFHHII 11 011111 113011 II 13011211112110 011 11120 1101011011ng 111201003 10110 001113 39P Iml g 1V8 1110Iq0Jd 1amp111111121311111123 111201003 12 S12 1301100111240 011 11120 011111012W 311111111 011g1111111101013110 1 110110 001113 99 91 31111331 aF EIS men1N Other NP Complete problems SAT 3CNFSAT CLIQUE HAMCYCLE VERTEX COVER TSP Slide Lecture 15 7467 CLIQUE 2 Complete Subgraph Problem Often expressed as Maximum subgraph problem HAM CYCLE The Hamiltonian Circuit Problem TSP The Traveling Salesman Problem Slide Lecture 15 7468 NXJr Y amp NZ Y Slide Lecture 15 7469 v1 IFF v2 amp v3 v2 IFF quotx Y v3 IFF quotz Y Which can be l39C CXII CSSCd in Conjunctivc Normal Form Slide Lecture 15 7470 C1X1 NXZ NX3 C2NX1X2X3 C3X1X2X3 Slide Lecture 15 7471 Since every SAT problem can be expressed as a 3 CNF SAT problem and every 3 CNF SAT can be expressed as a Clique complete subgraph problem SAT lt30 3 CNF lt30 CLIQUE So CLIQUE is NP Hard CLIQUE is also in NP since we can nd the CLIQU E in linear time given a Norrdetermirristie TM Thus CLIQU E is NP Complete Slide Lecture 15 7472 THE OPEN QUESTION P 2 MP It is believed that P y NP There are more than 1000 NP Complete problems None are known to have a P time solution Slide Lecture 15 7473

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

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

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

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

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