### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 174 Class Note for CSE 565 at PSU

### View Full Document

## 19

## 0

## Popular in Course

## Popular in Department

This 22 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 19 views.

## Similar to Course at Penn State

## Reviews for 174 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 31 P and NP Selfreducibility NPcompleteness Adam Smith S Raskhodnikova based on slides by K Wayne 1212008 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 Review Basic reducTion sTraTegies Simple equivalence INDEPENDENTSET a P VERTEXCOVER Special case To general case VERTEXCOVER s P SETCOVER Encoding wiTh gadgeTs 3SAT s P INDEPENDENTSET TransiTiviTy If X s P Y and Y s P Z Then X s P Z Pf idea Compose The Two algoriThms Ex 3SAT s P INDEPENDENTSET s P VERTEXCOVER s P SETCOVER Focus on decision yesno problems Simpler Theory Terminology problem or language X is a seT of binary sTrings eg binary rep39s of saTisfiable 3CNF formulas s E X means S is a YESinsTance of problem X For NPcompleTe problems decision a P search SelfReducibiliTy Decision problem Does There exisT a verTex cover of size s k Search problem Find verTex cover of minimum cardinaliTy SelfreducibiliTy Search problem s P decision version Applies To all NPcompleTe problems in This chapTer JusTifies our focus on decision problems Ex To find min cardinaliTy verTex cover On inpuT ltGVEgt Binary search for cardinaliTy k of min verTex cover Use log vl calls To The oracle for The decision version Find a verTex v such ThaT G v has a verTex cover of size s k 1 every verTex in a min verTex cover will have This properTy Include v in The verTex cover Ollvllcalls lhemcle Recursiver find a min verTex cover in G v deleTe v and all incidenT edges Polynomial Time Algori rhm A runs in polynomial Time if for every inpu r s rring s As Termina res in a r mos r plsl quots repsquot where p is some polynomial l lengTh of s PRIMES has a polynomial Time algoriThm Agr39awalKayalSaxena 2002 Ps ISIS DefiniTion of Class P P Decision problems for which There is a polyTime algoriThm MULTIPLE RELPRIME PRIMES EDIT DISTANCE LSOLVE Is x a mulTiple of y Are x and y relaTively prime Is x prime Is The ediT disTance beTween x and y less Than 5 Is There a vecTor 39x ThaT saTisfies Ax b Grade school division Euclid 300 BCE AKS 2002 Dynamic programming GaussEdmonds eliminaTion 51 34 53 17 39 niether neither 0 1 1 2 4 4 o 3 w lLEl 51 16 34 51 51 acgggt ttttta 10 0 1 11 11 0 11 1 DefiniTion of Class NP NP nondeTer39minisTic polynomialTime Cer39TificaTion algoriThm inTuiTion Cer39Tifier39 checks 0 proposed proof T ThaT s E X Need noT deTer39mine wheTher39 s E X on iTs own Def Algor39iThm Cs T is a cer39Tifier39 for problem X if for every sTr39ing s s E X iff Ther39e exisTs a sTr39ing T such ThaT Cs T yes quotcer TificaTequot or39 quotwiTnessquot NP Decision problems for which Ther39e exisTs a polyfTime cer39Tifier39 Cs T is a polyTime algor iThm and ITI s ps for39 some polynomial p CerTifiers and CerTificaTes ComposiTe COMPOSITES Given an inTeger s is s composiTe Cer TificaTe A nonTr39ivial facTor39 T of s NoTe Thcn such a cer TificaTe exisTs iff s is composiTe Moreover ITI s Isl CCPTTHCP boolean CompositesCertifiers t if t s 1 or t z 5 return false else if s is a multiple of t return true e 1 se return false InsTance s 437669 Cer TificaTe T 541 or39 809 lt 437669 541 x 809 Conclusion COMPOSITES is in NP Cer Tifier39s and CerTificaTes 3Sa risfiabili ry SAT Given a CNF formula I is There a saTisfying assignmenT Cer TificaTe An assignmenT of Tr39uTh values To The n boolean variables Cer39Tifier39 Check ThaT each clause in I has aT leasT one Tr39ue liTer39al EX xlvxzvx3Ax1vx2vx3 Ax1vx2Vx4A1vx3Vx4 insTance s x11 x21 x30 X41 cer TificaTe T Conclusion SAT is in NP Cer39Tifier39s and Cer39TificaTes HamilTonian Cycle HAMCYCLE Given an undirecTed graph G V E does Ther39e exisT a simple cycle C ThaT visiTs every node Cer39TificaTe A per39muTaTion of The n nodes Cer39Tifier39 Check ThaT The per39muTaTion conTains each node in V exacTIy once and ThaT There is an edge beTween each pair39 of adjacenT nodes in The per39muTaTion 39 r TificaTe T O O O O O V O P NP EXP P Decision problems for39 which There is a polyTime algor39iThm EXP Decision problems for which There is an exponenTialTime algor39iThm ie an algor39iThm ThaT runs in Time 02Ps for39 some polynomial p NP Decision problems for which There is a polyTime cer39Tifier39 Claim P Q NP Pf Consider any problem X in P By definiTion Ther39e exisTs a polyTime algor39iThm As ThaT solves X Cer39TificaTe T a cer39Tifier39 Cs T As Claim NP Q EXP Pf Consider39 any problem X in NP By definiTion Ther39e exisTs a polyTime cer39Tifier39 Cs T for X To solve inpuT 3 run Cs T on all sTr39ings T wiTh T s plsl ReTur39n yes if Cs T r39eTur39ns yes for any of These The Main Ques rion P Versus NP Does P NP Cook 1971 Edmonds Levin Yablonski Godel Is The decision problem as easy as The cerTificaTion problem Clay 1 million prize EXP If PNP If PNP would break RSA crypTography and poTenTially collapSe economy If yes EfficienT algoriThms for 3COLOR TSP FACTOR SAT If no No efficienT algoriThms possible for 3COLOR TSP SAT Consensus opinion on P NP Probably no NPCompleTe NPcompleTe A problem Y in NPcompleTe if V is in NP X s p Km Y for every problem X in NP Theorem Suppose Y is an NPcompleTe problem Then Y is solvable in polyTime iff P NP Pf lt If P NP Then Y can be solved in polyTime since Y is in NP Pf gt Suppose Y can be solved in polyTime LeT X be any problem in NP Since X s polyTime This implies NP Q P We already know P Q NP Thus P NP pl Karp Y we can solve X In FundamenTal quesTion Do There exisT quotnaTuralquot NPcompleTe problems Cir cuiT SaTisfiabiliTy CIRCUITSAT Given a combinaTional cir39cuiT buiIT ouT of AND OR and NOT gaTes is There a way To 361 The cir39cuiT inpuTs so Thcn The oquuT is 1 hardcoded inpuTs inpuTs The quotFirsTquot NPCompleTe Problem Theorem CIRCUITSAT is NPcompleTe Cook 1971 Levin 1973 Pf skeTch Any algoriThm ThaT Takes a fixed number of biTs n as inpuT and produces a yesno answer can be represenTed by such a circuiT Moreover if algoriThm Takes polyTime Then circuiT is of polysize skeTchy parT of proof fixing The number of biTs is imporTanT and reflecTs basic disTincTion beTween algoriThms and circuiTs Consider some problem X in NP IT has a polyTime cerTifier Cs T To deTermine wheTher s is in X need To know if There exisTs a cerTificaTe T of lengTh ps such ThaT Cs T yes View Cs T as an algoriThm on IsI ps biTs inpuT s cerTificaTe T and converT iT inTo a polysize circuiT K firsT IsI biTs are hardcoded wiTh s remaining ps biTs represenT biTs of T CircuiT K is saTisfiabIe iff Cs T yes Example Ex ConsTrucTion below creaTes a circuiT K whose inpuTs can be seT so ThaT K oquuTs True iff graph G has an independem seT of size 2 independem 36139 of size 2 independem 36139 a boTh endpoin rs of some edge have been chOSen 36139 of size 2 GVEn3 Q w w 1 o 1 hardcoded inpuTs graph de3cripfion n inpuTs nodes in independem 36139 EsTablishing NPCompleTeness Remark Once we esTablish firsT quotnaTur39alquot NPcompleTe problem oTher39s fall like dominoes Recipe To esTablish NPcompleTeness of problem Y STep 1 Show ThaT Y is in NP STep 2 Choose an NPcompleTe problem X STep 3 Pr39ove ThaT X s p Karp Y JusTificaTion If X is an NPcompleTe problem and Y is a problem in NP wiTh The pr39oper39Ty ThaT X 5 PI Karp Y Then Y is NPcompleTe Pf LeT W be any problem in NP Then W s P Karp X s P Karp Y By Tr39ansiTiviTy W s PI Karp V l by definiTion of by OSSUmpTion Hence Y Is NPcompleTe NPCompleTe 3SAT is NPCompleTe Theorem 3SAT is NPcompleTe Pf Suffices To show ThaT CIRCUITSAT s P 3SAT since 3SAT is in NP LeT K be any cir39cuiT Cr39eaTe a 3SAT variable xi for each cir39cuiT elemenT i Make cir39cuiT compuTe cor39r39ecT values aT each node x2 x3 gt add 2 clauses xzvxs zvx s x1 x4 v x5 gt add 3 clauses xlex1vgx1vx4v x5 x0 x1 A x2 gt add 3 clauses xo vxl xovxz xovxlvxz oquuT Xo Hardcoded inpuT values and oquuT value x5 0 gt add 1 clause X5 X1 X2 x0 1 gt add 1 clause x0 Final sTep Tur39n clauses of lengTh lt 3 info X5 X4 X3 0 9 9 clauses of lengTh exachy 3 by adding exTr39a var39iables x1 v x2 is saTisfiable iff xlvx2 v y A xlvx2 v y is saTisfiable NPComple reness ObservaTion All problems below are NPcompleTe and polynomial reduce wiTh Kar39p reducTions To one anoTher by defini rion of NPcomplefeness l 1122 LET SATquot llt l INDEPENDENT SET DIRHAM CYCLE GRAPH 3COLOR SUBSETSUM VERTEX COVER HAMCYCLE Pl ANAR 3COLOR SCHEDULING l l SET COVER TSP Some NPCompleTe Problems Six basic genres of NPcompleTe problems and paradigmaTic examples Packing problems SETPACKING INDEPENDENT SET Covering problems SETCOVER VERTEXCOVER ConsTrainT saTisfacTion problems SAT 3SAT Sequencing problems HAMILTONIANCYCLE Traveling Salesman ParTiTioning problems 3DMATCHING 3COLOR Numerical problems SUBSETSUM KNAPSACK PracTice MosT NP problems are eiTher known To be in P or NPcompleTe For mosT search problems if The corresponding decision problem is in P The search problem can be solved in polynomial Time NoTable excepTions Decision problem Graph isomorphism Polynomial idenTiTy TesTing Search problems FacToring Nash equilibrium ExTenT and ImpacT of NPCompleTeness ExTenT of NPcompleTeness PapadimiTriou 1995 Prime inTellecTual exporT of CS To oTher disciplines 6000 ciTaTions per year TiTle absTracT keywords more Than quotcompilerquot quotoperaTing sysTemquot quotdaTabasequot Broad applicabiliTy and classificaTion power quotCapTures vasT domains of compuTaTional scienTific maThemaTical endeavors and seems To roughly delimiT whaT maThemaTicians and scienTisTs had been aspiring To compuTe feasiblyquot NPcompleTeness can guide scienTific inquiry 1926 Ising inTroduces simple model for phase TransiTions 1944 Onsager solves 2D case in Tour de force 19xx Feynman and oTher Top minds seek 3D soluTion 2000 IsTrail proves 3D problem NPcompleTe More Hard CompuTaTional Problems Aerospace engineering opTimal mesh parTiTioning for finiTe elemenTs Biology proTein folding Chemical engineering heaT exchanger neTwork synThesis Civil engineering equilibrium of urban Traffic flow Economics compuTaTion of arbiTrage in financial markeTs wiTh fricTion ElecTrical engineering VLSI layouT EnvironmenTal engineering opTimal placemenT of conTaminanT Sensors Financial engineering find minimum risk porTfolio of given reTurn Game Theory find Nash equilibrium ThaT maximizes social welfare Genomics phylogeny reconsTrucTion Mechanical engineering sTrucTure of Turbulence in sheared flows Medicine reconsTrucTing 3D shape from biplane angiocardiogram OperaTions reSearch opTimal resource allocaTion Physics parTiTion funcTion of 3D Ising model in sTaTisTical mechanics PoliTics ShapleyShubik voTing power Pop culTure Minesweeper consisTency Sudoku STaTisTics opTimal experimenTal design max likelihood esTimaTion

### 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 signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I 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."

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