EXP-Completeness in Complexity Theory
Explore the concepts of EXP-hardness and EXP-completeness in complexity theory, where languages are classified based on their difficulty levels. Dive into the proofs and implications of EXP-complete languages being outside of P, showcasing the valuable technique for identifying complex languages. Discover examples like BOUNDED-HALT to grasp these fundamental principles.
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
EXP-hardness Definition: Let ? be a language. Suppose that for every ? EXP, there is a poly-time mapping reduction from ? to ?. In this case, we say that ? is EXP-hard ? is EXP-hard means ? is at least as hard as any language in EXP 2
EXP-completeness Definition: Let ? be a language. We say that ? is EXP-complete if ? is EXP-hard and ? EXP The EXP-complete languages are the hardest languages in EXP If ? is EXP-complete, then the language ? can be said to capture / express the entire complexity class EXP 3
EXP-completeness EXP-hard EXP-complete EXP P 4
EXP-complete languages are not in P Claim: If ? is EXP-complete, then ? P Proof: Since P EXP, there exists ?HARD EXP P Since ? is EXP-hard, there is a poly-time mapping reduction from ?HARD to ? Since ?HARD P, this implies ? P 5
BOUNDED-HALT is EXP-complete Let BOUNDED-HALT = ?,?,? ? halts on ? within ? steps Claim:BOUNDED-HALT is EXP-complete Proof:First, let s show that BOUNDED-HALT EXP Algorithm: Given ?,?,? , we simulate ? on ? for ? steps Exercise: This algorithm has time complexity ?2= ? ? 2? 2= 2? ? ? ? 6
BOUNDED-HALT is EXP-complete Next, we need to show that BOUNDED-HALT is EXP-hard Fix any ? EXP. Let ?? be a TM that decides ? in time ? 2?? ,?,? 2??, where ?? Reduction from ? to BOUNDED-HALT: ? ? = ?? is a modified version of ?? in which ?reject has been replaced with looping Poly-time computable YES maps to YES NO maps to NO 7
EXP-completeness EXP-hard BOUNDED-HALT EXP-complete EXP P 8
EXP-completeness EXP-completeness is a valuable technique for identifying languages outside P If ? is EXP-complete, then ? P There are many interesting EXP-complete languages 9
An EXP-complete problem that isnt about TMs Let GENERALIZED-CHESS = { ? ? is an arrangement of chess pieces on an ? ? board from which "white" can force a win} (Exercise: Precisely define GENERALIZED-CHESS) Theorem:GENERALIZED-CHESS is EXP-complete. Consequently, GENERALIZED-CHESS P. (Proof omitted. This theorem will not be on psets/exams) 10
EXP-completeness EXP-completeness is a valuable tool for identifying intractability Is EXP-completeness the only tool we need for identifying intractability? 11
The clique problem A ?-clique in a graph ? = ?,? is a set ? ? such that ? = ? and every two vertices in ? are connected by an edge Example: This graph has a 4-clique Which of the following statements is false? A: Every vertex in a ?-clique has degree at least ? 1 B: A single graph might have many ?-cliques C: If ? has fewer than ? then ? does not have a ?-clique D: If every vertex has degree at least ? 1, then ? has a ?-clique 2 edges, Respond at PollEv.com/whoza or text whoza to 22333 12
The clique problem Let CLIQUE = { ?,? ? has a ?-clique} Example: Let ? be the graph with the following adjacency matrix Does ? have a 4-clique? a b c d e f g a 0 1 1 0 0 1 0 b 1 0 0 1 1 0 1 c 1 0 0 0 1 0 1 d 0 1 0 0 1 0 1 e 0 1 1 1 0 1 1 f 1 0 0 0 1 0 1 g 0 1 1 1 1 1 0 13
The clique problem Let CLIQUE = { ?,? ? has a ?-clique} Example: Let ? be the graph with the following adjacency matrix Does ? have a 4-clique? a b c d e f g a 0 1 1 0 0 1 0 Yes! ? = {b,d,e,g} b 1 0 0 1 1 0 1 c 1 0 0 0 1 0 1 d 0 1 0 0 1 0 1 e 0 1 1 1 0 1 1 f 1 0 0 0 1 0 1 g 0 1 1 1 1 1 0 14
Complexity of the clique problem Let CLIQUE = { ?,? ? has a ?-clique} CLIQUE EXP. (Why?) If you spend a while trying to design a good algorithm, eventually you might start to suspect that CLIQUE P However, if you spend a while trying to design a good reduction, eventually you might start to suspect that CLIQUE is not EXP-complete either! 15
EXP-hard EXP-complete CLIQUE seems to be here EXP P 16
Complexity of the clique problem Evidently, to understand the complexity of CLIQUE, we need new conceptual tools 17
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. 18
The complexity class NP Let ? be a language Definition:? NP if there exists a randomized polynomial-time Turing machine ? such that for every ? : If ? ?, then Pr ? accepts ? 0 If ? ?, then Pr ? accepts ? = 0 Nondeterministic Polynomial-time 19
Another example of a language in NP Let FACTOR = ?,? ? has a prime factor ? ? Claim:FACTOR NP Proof: 1. Pick ? 2,3,4, ,? uniformly at random 2. Check whether ? is a multiple of ? by long division 3. If it is, accept; if it isn t, reject 20
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 21
Terminology: Verification of certificates perspective A poly-time TM that decides ? is called a verifier for ? If ?,? ?, then ? is called a certificate/witness for ? Let ? be a language Claim:? NPif and only if there exists ? and ? P such that For every ? ?, there exists ? such that ? ?? and ?,? ? For every ? ?, for every ?, we have ?,? ? Proof: ( ) Let ? = ?,? ? accepts ? when ? is on tape 2 ( ) Pick ? at random. Accept if ?,? ? and reject otherwise 22
NP The P vs. NP problem P P NP (why?) Does P = NP? P = NP would mean that finding a solution is never significantly harder than verifying someone else s solution This would be counterintuitive! Conjecture:P NP 23
The P vs. NP problem Nobody knows how to prove that P NP The question of whether P = 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) 24
Solving problems in NP by brute force Claim:NP PSPACE Proof: Let ? be a nondeterministic TM that runs in time ??. Given ? ?: 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 25
EXP PSPACE NP P 26
