Importance of Environmental Cleaning in Hospitals
Environmental cleaning plays a crucial role in controlling infections in hospitals. General principles, frequency guidelines for cleaning common situations, disinfection of operation theatre surfaces, and fogging for aerial disinfection are discussed in detail.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2024 Instructor: William Hoza 1
?-CNF formulas A ?-CNF formula is an AND of ORs of literals in which every clause has at most ? literals Example of a 3-CNF formula with two clauses: ? = ?1 ?2 ?6 ?5 ?1 ?2 2
The Cook-Levin Theorem Define ?-SAT = { ? ? is a satisfiable ?-CNF formula} The Cook-Levin Theorem: 3-SAT is NP-complete Proof:3-SAT NP (guess a satisfying assignment) To show that 3-SAT is NP-hard, we will reduce from CIRCUIT-SAT 3
Gate gadgets Define the following Boolean functions: CHECK-NOT ?,? = 1 if ? = ? 0 otherwise CHECK-AND ?,?,? = 1 if ? = ? ? 0 otherwise CHECK-OR ?,?,? = 1 if ? = ? ? 0 otherwise Each can be represented by a 3-CNF formula. (Every function has a CNF representation!) 4
Reduction from CIRCUIT-SAT to 3-SAT Reduction: ? ? = ? , where ? is a 3-CNF defined as follows Circuit ? has variables ?1,?2, ,?? and AND/OR/NOT gates ?1, ,?? Assume without loss of generality that ?? is the output gate Formula ? has ? + ? variables, which we denote ?1, ,??,?1, ,?? Note: In ?, ?? is the name of a gate. In ?, ?? is the name of a variable 5
Reduction from CIRCUIT-SAT to 3-SAT For each AND/OR/NOT gate ?? in the circuit ?, define a 3-CNF ??: ?? ?? ?? ? ? ? ? ? ??= CHECK-OR ??,?,? ??= CHECK-NOT ??,? ??= CHECK-AND ??,?,? Reduction produces ?:= ?1 ?2 ?? ?? 6
Reduction example ?5 ?1= CHECK-NOT ?1,?1 = ?1 ?1 ( ?1 ?1) ?4 ?3 ?2= CHECK-NOT ?2,?2 = ?2 ?2 ?2 ?2 ?3= CHECK-AND ?3,?1,?2 = ?1 ?2 ?3 ?1 ?3 ?2 ?3 ?1 ?2 ?4= CHECK-AND ?4,?1,?2 = ?4 ?1 ?4 ?2 ?4 ?1 ?2 ?2 ?1 ?5= CHECK-OR ?5,?3,?4 = ?5 ?3 ?5 ?4 ?5 ?3 ?4 ? = ?1 ?1 ?3 ?1 ?2 ?5 ?4 ?1 ?1 ?2 ?2 ?4 ?1 ?5 ?3 ?4 ?5 ?2 ?2 ?4 ?2 ?4 ?1 ?2 ?5 ?3 ?3 ?1 ?3 ?2 7
YES maps to YES Claim: If the circuit ? is satisfiable, then the 3-CNF formula ? is also satisfiable Proof: We are assuming there is some ? {0,1}? such that ? ? = 1 For each ?, assign to ?? (the variable) the value that ?? (the gate) outputs when we evaluate ? on ? We claim that ? ?1, ,??,?1, ,?? = 1. Indeed, each ?? is satisfied because of the circuit structure, and ??= 1 because ? ? = 1 8
NO maps to NO Claim: If ? is not satisfiable, then ? is not satisfiable Proof sketch: We will prove the contrapositive: if ? is satisfiable, then ? is satisfiable If ? ?1, ,??,?1, ,?? = 1, then we claim ? ?1, ,?? = 1 Indeed, by induction on the circuit structure, ?? (the variable) must be equal to the value that ?? (the gate) outputs when we evaluate ? on ?. Furthermore, ??= 1 9
Reduction efficiency Reduction is computable in polynomial time For each gate in the circuit, we write down ? 1 clauses, and it is straightforward to compute what they are Let ? = ? ? . Which of the following is false? A:? is satisfiable if and only if ? is satisfiable ? poly ? B: C: The number of clauses in ? is size of ? D:? and ? compute the same Boolean function Respond at PollEv.com/whoza or text whoza to 22333 10
NP-hard CIRCUIT-SAT 3-SAT NP-complete NP P 11
Chaining reductions together 3-SAT is the starting point for many NP-hardness proofs We are finally ready to use the hardness of 3-SAT to prove that CLIQUE is NP-complete 12
CLIQUE is NP-complete Recall CLIQUE = ?,? ? contains a ?-clique Theorem: CLIQUE is NP-complete Proof: We showed CLIQUE NP in a previous class To prove that CLIQUE is NP-hard, we will do a reduction from 3-SAT 13
Reduction from 3-SAT to CLIQUE Let ? be a 3-CNF formula (an instance of 3-SAT) Reduction: ? ? = ?,? ? is the number of clauses in ? ? is a graph on 3? vertices defined as follows 14
Reduction from 3-SAT to CLIQUE E.g., ? = ?1 ?2 ?5 ?1 ?4 ?6 For each clause 1 2 3, create a ?2 ?4 ?3 ?3 ?6 ?1 group of three vertices labeled 1, 2, 3 ?1 ?2 ?5 (If the clause only has one or two literals, ?1 ?2 then only use one or two vertices) ?4 Put an edge {?,?} if ? and ? are in ?4 ?6 different groups and ? and ? do not ?3 have contradictory labels (?? and ??) ?3 ?6 ?1 15
YES maps to YES Suppose ? is satisfiable, i.e., there exists a satisfying assignment ? In each clause, at least one literal is satisfied by ? Therefore, in each group, at least one vertex is satisfied by ?, i.e., it is labeled by a literal that is satisfied by ? Let ? be a set consisting of one satisfied vertex from each group Then ? is a ?-clique (vertices in ? cannot have contradictory labels) 16
NO maps to NO Suppose ? has a ?-clique ? Let ? be an assignment that satisfies each vertex in ? (this exists because no two vertices in ? have contradictory labels) ? cannot contain two vertices from a single group, and ? = ?, so ? must contain one vertex from each group Therefore, ? satisfies at least one literal in each clause, i.e., ? satisfies ? 17
Poly-time computable Hopefully it is clear that the reduction ? ? = ?,? can be computed in polynomial time 18
NP-hard CIRCUIT-SAT CLIQUE NP-complete 3-SAT NP P 19
NP-completeness is everywhere There are thousands of known NP-complete problems! These problems come from many different areas of study Logic, graph theory, number theory, scheduling, optimization, economics, physics, chemistry, biology, 20
Proving that ? is NP-complete (cheat sheet) 1. Prove that ? NP What is the certificate? How can you verify a purported certificate in polynomial time? 2. Prove that ? is NP-hard Which NP-complete language ?HARD are you reducing from? What is the reduction? Is it polynomial-time computable? YES maps to YES: Assume there is a certificate ? showing ? ?HARD. In terms of ?, construct a certificate ? showing that ? ? ?. NO maps to NO: (Contrapositive) Assume there is a certificate ? showing ? ? ?. In terms of ?, construct a certificate ? showing that ? ?HARD. 21
NP-complete languages stand or fall together If you design a poly-time algorithm for one NP-complete language, then P = NP, so all NP-complete languages can be decided in poly time! If you prove that one NP-complete language cannot be decided in poly time, then P NP, so no NP-complete language can be decided in poly time! 22
Final exam cutoff point Final exam will be Wednesday, May 22 from 10am to noon in this room (STU 105) The exam is cumulative To prepare for the final exam, you only need to study the material up to this point (including problem set 7) 23
