×

### Let's log you in.

or

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

×

or

39

0

17

# 664 Class Note for CSE 565 at PSU

Marketplace > Pennsylvania State University > 664 Class Note for CSE 565 at PSU

No professor available

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

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

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

×
Unlock Preview

COURSE
PROF.
No professor available
TYPE
Class Notes
PAGES
17
WORDS
KARMA
25 ?

## Popular in Department

This 17 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.

×

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

×

×

### What is Karma?

#### 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 30 Computational Intractability Polynomial Time Reductions Adam Smith A Smith based on slides by S Raskhodnikova and K Wayne 11212008 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 Reduc rion By Simple Equivalence Basic r educ rion sTraTegies I ReducTion by simple equivalence I Reduc rion from special case To general case I Reduc rion by encoding wiTh gadgeTs IndependenT SeT INDEPENDENT SET Given a graph G V E and an inTeger39 k is There a subseT of ver39Tices S E V such Thcn ISI 2 k and for each edge cn mosT one of iTs endpoints is in 5 Ex Is There an independenT seT of size 2 6 Yes Ex Is There an independenT seT of size 2 7 No O independenf 36139 Ver39Tex Cover39 VERTEX COVER Given a graph G V E and an inTeger39 k is There a subseT of ver39Tices S E V such Thcn ISI 5 k and for each edge cn leasT one of iTs endpoints is in 5 Ex Is There a ver39Tex cover39 of size s 4 Yes Ex Is There a ver39Tex cover39 of size s 3 No ver39Tex cover39 Ver Tex Cover39 and IndependenT SeT Claim VERTEXCOVER EP INDEPENDENTSET Pf We show 5 is an independem seT iff V S is a ver39Tex cover O independem 36139 ver39Tex cover39 Ver Tex Cover and IndependenT SeT Claim VERTEXCOVER EP INDEPENDENTSET Pf We show 5 is an independenT seT iff V S is a ver39Tex cover39 LeT S be any independenT seT Consider an ar39biTr39ar39y edge u v SindependenTuSorvS gt uEVSor39vEVS Thus V 5 covers u v LeT V S be any ver39Tex cover39 Consider39 Two nodes u E S and v E S Obser39ve Thcn u v i E since V S is a ver39Tex cover39 Thus no Two nodes in S are Joined by an edge gt 5 independenT seT Reduc rion from Special Case To General Case Basic r educ rion sTraTegies I Reduc rion by simple equivalence I Reduc rion from special case To general case I Reduc rion by encoding wiTh gadgeTs SeT Cover39 SET COVER Given a seT U of n elemenTs a collecTion 1 2 Sm of subseTs of U and an inTeger39 k does Ther39e exisT a collecTion of s k of These seTs whose union is equal To U Sample applicaTion m available pieces of sofTwar39e SeT U of n capabiliTies ThaT we would like our39 sysTem To have The iTh piece of sofTwar39e provides The seT S Q U of capabiliTies Goal achieve all n capabiliTies using fewesT pieces of sofTwar39e Ex U1234567 k2 5137 5424 52345 S55 531 56 1 267 Ver39Tex Cover39 Reduces To SeT Cover39 Claim VERTEXCOVER s P SETCOVER Pf Given a VERTEXCOVER insTcmce G V E k we consTr39ucT a seT cover39 insTcmce whose size equals The size of The ver39Tex cover39 insTcmce ReducTion On inpuT lt 6 V E kgt OquuT SETCOVER insTcmce kk UE SveEEeincidenTTov Cor39r39ecTness claim SeTcover39 of size s k iff ver39Tex cover39 of size s k VERTEX COVER e 7 62 63 e4 SET COVER U1234567 k 2 5a37 5b24 5c 3 4 5 6 sd 5 se1 sf1267 Reduc rions by Encoding wi rh Godge rs Basic r39educTion sTr39oTegies ReducTion by simple equivalence ReducTion from special case To general case ReducTion by encoding wiTh godgeTs Satisfiability Literal A Boolean variable or its negation xi 0r xi Clause A disjunction OR of literals C x1 V g V 3 3 Conjunctive normal form A propositional q C1 A02 A 03A C4 formula lt1 that is the conjunction AND of clauses SAT Given CNF formula I does it have a satisfying truth assignment 3SAT SAT where each clause contains exactly 3 literals each corresponds to a different variable Ex x1vx2vx3x1vgvx3x2vx3Evgvg Yes x1 true x2 true X3 fOISe 3 SaTisfiabiliTy Reduces To IndependenT SeT Claim 3SAT s P INDEPENDENTSET Pf Given an insTance lt1 of 3SAT we consTr39ucT an instance 6 k of INDEPENDENTSET ThaT has an independenT seT of size k iff I is saTisfiable ReducTion On inpuT lt I gt LeT G conTain 3 ver39Tices for each clause one for each IiTer39al ConnecT 3 IiTer39als in a clause in a Triangle ConnecT IiTer39aI To each of iTs negaTions k Ilt1gtI k of clauses in I OquuT lt6 kgt 3 SaTisfiabiliTy Reduces To IndependenT SeT Claim 6 conTains independenT seT of size k lt1gt iff I is saTisfiable Pf gt LeT S be independenT seT of size k S musT conTain exachy one verTex in each Triangle 561 These ferd3 10 True 4 and any o rher variables in a consis ren r way TruTh assignmenT is consisTenT and all clauses are saTisfied Pf lt Given saTisfying assignmenT selecT one True liTeral from each Triangle This is an independent seT of size k Review Basic r39educTion sTr39aTegies Simple equivalence INDEPENDENTSET a P VERTEXCOVER Special case To general case VERTEXCOVER s P SETCOVER Encoding wiTh gadgets 3SAT s P INDEPENDENTSET Tr39ansiTiviTy If X s P Y and Y s P Z Then X s P Z Pf idea Compose The Two algor39iThms Ex 3SAT s P INDEPENDENTSET s P VERTEXCOVER s P SETCOVER

×

×

### BOOM! Enjoy Your Free Notes!

×

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

Amaris Trozzo George Washington University

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

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

Parker Thompson 500 Startups

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

Become an Elite Notetaker and start selling your notes online!
×

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