# CSE 6311 Spring 2009 ADVANCED COMPUTATIONAL MODELS AND

CSE 6311 Spring 2009 ADVANCED COMPUTATIONAL MODELS AND ALGORITHMS Lecture Notes Feb. 3, 2009 Instructor: Dr. Gautam Das notes by Walter Wilson Some NP-Complete problems: SAT, 3SAT, CLIQUE, VERTEX COVER, MAX INDEP SET SAT - Satisfiability:

Inputs: a) n Boolean variables: v1,..,vn b) Boolean formula variables & operators (and &, or |, not ~) Example: (v1 | ~v2) & (~v1 | v2 | v3) Output: Is there a satisfying assignment to the variables? For our example yes: v1=1, v2=0, v3=1 Cook's Theorem (or Cook-Levin Thm) "The complexity of theorem proving

procedures" (1971) SAT is NP-complete: var asmt can be verified in polynomial time Boolean expr satisfied iff nondeterministic Turing machine accepts NP problem Karp - reduction "Reducibility Among Combinatorial Problems" (1972) Proved 21 NP-complete problems 3SAT Inputs:

a) n Boolean variables: v1,..,vn b) 3-CNF (Conjunctive Normal Form) Boolean formula: Conjunction of clauses, each clause a disjunction of 3 literals, each literal a variable or its negation (if clause length = 2, problem is P) (3 is smallest length that is NP) CLIQUE largest complete subgraph Decision problem: Given graph G (n vertices, m edges) and k>0, is there a clique of size >=k? Naive algorithm look at all 2^n vertex subsets

Problem in NP verification of clique is in P Reduce NP-complete problem 3SAT to CLIQUE: Create vertex for each literal of each clause Make edges between vertices of different clauses except for opposite literals Clique of size C exists iff 3SAT formula is satisfiable where C is number of clauses Thus CLIQUE is NP-complete VERTEX COVER Smallest vertex subset that touches all edges

Decision problem: Given graph G (n vertices, m edges) and k>0, is there a cover of size <=k? Reduce CLIQUE to VERTEX COVER: Given Clique inputs G,k compute VC inputs: G' = complement of G (edge (vi,vj) in G' iff not in G) k' = n - k Clique of size k in G iff VC of size k' in G' Example graph: a

c b d g e f Vertex Cover: {a, g, e} MAX INDEP SET Independent Set: vertex subset with no edges within the set

Decision problem: Given graph G and k, is there an independent set of size >=k? Is in NP: easy to verify subset as independent Reduce VERTEX COVER to MAX INDEP SET Given VC inputs G,k compute Max Indep. Set inputs: G' = G k' = n - k VC of size k iff Independent Set of size k' Max Indep Set = {b, c, d, f} for example graph

## Recently Viewed Presentations

• The Nicene Creed. The Nicene Creed was developed at the Councils of Nicaea (325 AD) and the Council of Constantinople (381 AD) It is a personal profession of the core beliefs held by Catholics. Reminds believers of the mysteries of...
• The Linear Biped Model and Application to Humanoid Estimation and Control Benjamin Stephens Carnegie Mellon University Monday June 29, 2009 * * * My previous work has been on static balance strategies, including IBC which used a hip strategy, and...
• Knowing your key influencers, objectives and establishing a budget and schedule that is clear but flexible are the components of A GOOD PLAN. Identifying your external and internal team members and establishing clear ground rules regarding involvement and communications are...
• Lupine-Induced Crooked Calf Disease Situation Analysis Baby born in NW CA with severe bone deformities. Partial absence of forearm bones Absent thumbs Possibilities Herbicide spraying in area linked to birth defects.
• Critical Success Factor: Speed to Market - Ability to execute on deliverables at a rapid pace. Partnering To Advance Early Success . The Case for Value. The Execution Playbook. ... PowerPoint Presentation Last modified by: Foster, Linda A ...
• Early South Asia & Early China Chapter 3 Notes Early South Asia 3rd civilization on the rise = Indus River Valley in South Asia Arose on the subcontinent of Asia = landmass that is part of a continent but is...
• 4. Direct access to the CSO/CCO. Trusted advisor willing to spend time with clients to talk through: Gap Analysis. Auditor questions. Facility tours. Compliance control mapping . Security best practices. 3/13/19. www.lightedge.com 1.877.771.3343
• (a) Morgan. [AP/Wide World Photos.] 4.11b Thomas Hunt Morgan's work with Drosophila helped unravel many basic principles of genetics, including X-linked inheritance. (b) The Fly Room, where Morgan and his students conducted genetic research. [American Philosophical Society.] 4.12 Morganﾕs X-linked...