### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 688 Class Note for CSE 565 at PSU

### View Full Document

## 39

## 0

## Popular in Course

## Popular in Department

This 11 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 39 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 688 Class Note for CSE 565 at PSU

### 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: 02/06/15

Algorithm Design and Analysis LECTURE 35 Computational Intractability Polynomial Time Reductions Adam Smith A Smith based on slides by S Raskhodnikova K Wayne 11192008 This chapTer compuTaTional in rr ac rabili ry and NP Goal under39s rand wha r canno r be compu red can you name some hard problems Compu rabili ry canno r even in principlequot Complexi ry cannoT given reasonable r39esour39cesquot we focus on complexiTy here why Cen rr39al ideas polyTime as feasible mos r na rur39al problems are ei rher39 easy or39 have no known polyTime algor39i rhms nunreasomble H NP and NPcomple reness Effec figeness P pr39oblems ThaT are easy To answer39 mathgma rics eg minimum cu r i SC encequot NP 2 problems whose answers are easy To verify given hin r eg gr39aph 3color39ing NP comple reness many na rur39al problems are easy if and only if PNP So far39 under39sTand alg design Examples Greedy On log n inTer39val scheduling Divideandconquer39 On log n FFT Dynamic programming 0n2 ediT disTance DualiTy eg MaxFlowNlinCuT On3 bipar39TiTe maTching ReducTions Local search Randomm on New goal under39sTand whaT is hard To compuTe NPcompleTeness Onkalgor39iThm unlikely PSPACEcompleTeness Onk cer TificaTion algor39iThm unlikely UndecidabiliTy No algor39iThm possible amnes quot 5quot Example hard problems A y Problems in P Problems in NPcomplete PSPACE Undecidable NP not known complete to be in P or NPcomplete max ow factoring longest path TQBF totally halting problem t39f d knapsack W1th graph traveling 83211162 fractional isomorphism salesman formula elements in h 1 knapsack grap CO O ng Given a game 35m with polysize board independent set con gurations knapsack W decide if White fract weights has Wmmng strategy 11 19 2008 A Smith based on slides by S Raskhodnikova K Wayne UndersTanding quothardnessquot CompuTabiliTy UndersTand whaT cancannoT be compuTed even in principle HalTing problem given program code will This program geT sTuck in an infiniTe loop Theorem Turing halTing problem is uncompuTable so mosT Things we wanT compilers To do are undecidable Corollary Some numbers are Too big To compuTe busy beaver problem BBnmax of sTeps ThaT an ncharacTer C program ThaT sTops evenTually can Take before iT sTops If you could compuTe an upper bound on BBn you could solve The halTing problem CompeTiTion Think of The biggesT number you can ComplexiTy UndersTand whaT problems cannoT be solved in a reasonable amounT of Time Far less is known Famous problem P vs NP unreasonable effectiveness of maThemaTics in sciencequot Cen rral ideas we39ll cover PolyTime as feasible mos r na rural problems ei rher are easy say n3 or have no known polyTime algori rhms Reduc rions X is no harder Than Y P 2 problems Tha r are easy To answer eg minimum cu r NP 2 problems whose answers are easy To verify given him eg graph 3coloring NPcompleTeness many naTural problems are easy if and only if PNP Classify Problems DesideraTa Classify problems as Those ThaT can be solved in polynomialTime and Those ThaT cannoT Roughly C program on machine wiTh Provably require exponenTial 39me 39 fm39Te memory Given a Turing machine does iT halT in aT mosT k sTeps Given a board posiTion in an nbyn generalizaTion of chess can black guaranTee a win FrusTraTing news Huge number of fundamenTal problems have defied classificaTion for decades This chapTer Show ThaT These fundamenTal problems are quotcompuTaTionally equivalenTquot and appear To be differenT manifesTaTions of one really hard problem Tool PolynomialTime Reduc rion DesideraTa39 Suppose we could solve X in polynomialTime WhaT else could we solve in o nomia Time p y don T confUSe wiTh reduces from ReducTion Problem X polynomial reduces To problem Y if arbiTrary insTances of problem X can be solved using Polynomial number of sTandard compuTaTional sTeps plus Polynomial number of calls To oracle ThaT solves problem Y compuTaTional model SupplemenTed by special piece of hardware ThaiL solves insTances of Y in a single sTep NoTaTion X s PICook Y or X s P Y LaTer in The ecTure X s P Karp Y Remarks We pay for Time To wriTe down insTances senT To black box gt insTances of Y musT be of polynomial size PolynomialTime ReducTion Purpose Classify problems according To r39elaTive difficulTy Design algor39iThms If X s P Y and Y can be solved in polynomialTime Then X can also be solved in polynomial Time EsTablish inTr39acTabiliTy If X s P Y and X cannoT be solved in polynomialTime Then Y cannoT be solved in polynomial Time EsTablish equivalence If X s P Y and Y s P X we use noTaTion X a PY up To cosT of r39educTion Simpliinng Assumption Decision Problems Search problem Find some structure Example Find a minimum cut Decision problem X is a set of strings Instance string 3 If xe X x is a YES instance if xi X is a NO instance Algorithm A solves problem X As yes iff s E X Example Does there exist a cut of size s k Selfreducibility Search problem s PICook decision version Applies to all NPcomplete problems in this chapter Justifies our focus on decision problems Polynomial TransformaTion Def Problem X polynomial reduces Cook To problem Y if arbiTrary insTances of problem X can be solved using Polynomial number of sTandard compuTaTional sTeps plus Polynomial number of calls To oracle ThaT solves problem Y Def Problem X polynomial Transforms Karp To problem Y if given any inpuT x To X we can consTrucT an inpuT y such ThaT x is a yes insTance of X iff y is a yes insTance of V l we require IyI To be of size polynomial in IXI NoTe Polynomial TransformaTion is polynomial reducTion wiTh jusT one call To oracle for Y exachy aT The end of The algoriThm for X Open quesTion Are These Two concest The same CauTion KT abuSes noTaTion sp and blurs disTincTion

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

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