Introduction to Complexity Theory and NP Problems
Explore Complexity Theory topics such as the complexity of the clique problem, NP complexity class, and examples like FACTOR in NP. Understand the concept of NP as a tool for computational reasoning and the verification of certificates in a nondeterministic context.
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 2025 Instructor: William Hoza 1
CLIQUE = { ?,? ? has a ?-clique} EXP-hard EXP-complete CLIQUE seems to be here EXP P 2
Complexity of the clique problem Evidently, to understand the complexity of CLIQUE, we need new conceptual tools 3
Guessing and checking Key insight: There exists a polynomial-time randomized Turing machine ? with the following properties. If ?,? CLIQUE, then Pr ? accepts ?,? = 0. Nondeterministic TM If ?,? CLIQUE, then Pr ? accepts ?,? 0. Proof:?picks a random subset of the vertices, accepts if it is a ?-clique, and rejects otherwise. 4
The complexity class NP Let ? 0,1 Definition:? NP if there exists a randomized polynomial-time Turing machine ? such that for every ? 0,1 : If ? ?, then Pr ? accepts ? 0 If ? ?, then Pr ? accepts ? = 0 Nondeterministic Polynomial-time 5
Another example of a language in NP FACTOR = ?,? ? has a prime factor ? ? Claim:FACTOR NP Proof: 1. Pick ? 2,3,4, ,? uniformly at random 2. Check whether ?/? is an integer (long division) 3. If it is, accept; if it isn t, reject 6
How to interpret NP NP is not intended to model the concept of tractability A nondeterministic polynomial-time algorithm is not a practical way to solve a problem Instead, NP is a conceptual tool for reasoning about computation 7
Verification of certificates perspective Let ? 0,1 Verifier Claim:? NPiff there exists ? and a deterministic poly-time TM ? such Certificate / Witness that: For every ? ?, there exists ? such that ? ?? and ? accepts ?,? For every ? ?, for every ?, the machine ? rejects ?,? Proof: ( ) Given ?,? , ? simulates ? with ? on tape 1 and ? on tape 2 ( ) Pick ? at random and simulate ? on ?,? 8
NP The P vs. NP problem P P NP (why?) Open question: Does P = NP? Let ? NP What can we do if we want to decide ? deterministically? 9
Solving problems in NP by brute force Claim:NP PSPACE Proof: Let ? be a time-?? nondeterministic TM. Given ? 0,1?: 1. For every ? 0,1??, simulate ?, initialized with ? on tape 1 and ? on tape 2 2. If we find some ? such that ? accepts, accept. Otherwise, reject NP can be informally defined as the set of problems that can be solved by brute-force search 10
EXP PSPACE NP P 11
P vs. NP vs. PSPACE vs. EXP P NP PSPACE EXP What we expect: All of these containments are strict What we can prove: At least one of these containments is strict. (Why?) 12
NP The P vs. NP problem P P = NP would mean: Brute-force search algorithms can always be converted into poly-time algorithms Verifying someone else s solution is never significantly easier than solving a problem from scratch This would be counterintuitive! Conjecture:P NP 13
Comparing NP and BPP Conjecture:P NP It s hard to find a needle in a haystack Conjecture:P = BPP It s easy to find hay in a haystack! 14
The P vs. NP problem P vs. NP is one of the most important open questions in theoretical computer science and mathematics The Clay Mathematics Institute will give you $1 million if you prove P NP (or if you prove P = NP) 15
Complexity of CLIQUE Recall: CLIQUE = { ?,? ? has a ?-clique} Previously discussed: CLIQUE NP Consequence: If P = NP, then CLIQUE P Plan: We will prove that if P NP, then CLIQUE P This will provide evidence that CLIQUE P To prove it, we will use concepts of NP-hardness and NP-completeness 16
NP-hardness Let ? 0,1 Definition: We say that ? is NP-hard if, for every ? NP, we have ? P? Interpretation: ? is at least as hard as any language in NP Every problem in NP is basically a special case of ? 17
NP-completeness Let ? 0,1 Definition: We say that ? is NP-complete if ? is NP-hard and ? NP The NP-complete languages are the hardest languages in NP If ? is NP-complete, then the language ?can be said to capture / express the entire complexity class NP Example: We will eventually prove that CLIQUE is NP-complete 18
NP-complete languages are probably not in P Let ? be an NP-complete language Claim:? P if and only if P = NP Proof: This holds because ? NP This holds because ? is NP-hard 19
NP-completeness NP-hard NP-complete NP P 20
Proving NP-completeness How can we prove that a language like CLIQUE is NP-complete? How can we use graph theory to simulate Turing machines? Plan: Turing Machines Logic Gates Graph Theory 21
Logic gates AND: ? ? OR: ? ? NOT: ? 22
Boolean formulas Compare to arithmetic formulas Definition: An ?-variate Boolean formula is a rooted tree Each internal node is labeled or (two children) or (one child) Each leaf is labeled with 0, 1, or a variable among ?1, ,?? It computes ?: 0,1? 0,1 E.g., ? ?1,?2,?3 = ?1 ?2 ?1 ?3 ?1 ?2 ?1 Notation: ?? is another way of writing ?? ?3 23
Boolean circuits 1 1 0 A Boolean circuit is like a Boolean 1 0 0 1 0 1 formula, except that we permit vertices 0 0 1 0 to have multiple outgoing wires 0 0 1 1 1 0 0 1 1 1 1 0 ?4 ?2 ?3 ?1 1 1 0 1 24
Boolean circuits: Rigorous definition Definition: An ?-input ?-output circuit is a directed acyclic graph We refer to the edges as wires Each node is labeled with one of the following: or (two incoming wires) gates (one incoming wire) 0, 1, or a variable among ?1, ,?? (zero incoming wires) ?of the nodes are additionally labeled as output 1 , output 2 , , output ? 25
Boolean circuits: Rigorous definition Each node ? computes a function ?:{0,1}? {0,1} defined inductively: If ? is labeled ??, then ? ? = the ?-th bit of ? If ? is labeled and its incoming wire comes from ?, then ? ? = ? ? If ? is labeled and its incoming wires come from ? and , then ? ? = ? ? ? If ? is labeled and its incoming wires come from ? and , then ? ? = ? ? ? 26
Boolean circuits Let the output nodes be ?1, ,?? As a whole, the circuit computes ?: 0,1? 0,1? defined by ? ? = ?1? , ,??? 27
Circuit complexity ?1 ?2 The size of the circuit is the total number of AND/OR/NOT gates How much work does the circuit do? Let ?:{0,1}? {0,1}? The circuit complexity of ? is the size of the smallest circuit that computes ? How much work is required to compute ?? 28
Circuit complexity example 1 Let ? ? = ?1 ?2 ?? ?1 ?2 ?3 ?5 ?8 ?7 ?4 ?6 Circuit complexity: ? 29
Circuit complexity example 2 Let ? ? = ?1 ?2 ?? What is the circuit complexity of ?? A: ?2 B:? 1 D: 2? C: ? Respond at PollEv.com/whoza or text whoza to 22333 30
