Complexity Theory: Hamiltonian Paths and NP-Completeness
Explore the concepts of Hamiltonian paths in directed and undirected graphs, NP-completeness, and reductions between different complexity classes. Learn about the challenges and intricacies of proving problems to be NP-hard and NP-complete in the realm of complexity theory.
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
Hamiltonian paths Let ? be a directed graph Definition: A Hamiltonian path is a directed path that visits every vertex exactly once 2
DIRECTED-HAM-PATH is NP-complete ? ?1 Let DIRECTED-HAM-PATH = { ?,?,? ?1 ?2 ? is a digraph, ? and ? are vertices, and ?2 ?3 there exists a Hamiltonian path ? from ? to ?} ?? ? Theorem: DIRECTED-HAM-PATH is NP-complete 3
NP-hard CIRCUIT-SAT DIRECTED-HAM-PATH CLIQUE NP-complete 3-SAT SUBSET-SUM NP P 4
Undirected Hamiltonian path Let ? be an undirected graph A Hamiltonian path in ? is a path that visits every vertex exactly once Let UNDIRECTED-HAM-PATH = { ?,?,? ? is an undirected graph, ? and ? are vertices, and there exists a Hamiltonian path from ? to ?} Theorem: UNDIRECTED-HAM-PATH is NP-complete 5
UNDIRECTED-HAM-PATH is NP-complete First, note that UNDIRECTED-HAM-PATH NP (why?) To prove that UNDIRECTED-HAM-PATH is NP-hard, we will do a reduction from DIRECTED-HAM-PATH Attempted reduction: Replace each directed edge ?,? with an undirected edge {?,?}. Does this work? B:It doesn t work, because it doesn t run in polynomial time A: Yes C:It doesn t work, because it doesn t always map YES to YES D:It doesn t work, because it doesn t always map NO to NO Respond at PollEv.com/whoza or text whoza to 22333 6
From directed to undirected Reduction: Given ?,?,? , produce ? ,?in,?out, constructed as follows: 1. Delete all edges going into ? or coming out of ? ? ?out ?out ?in ? 2. ? ? ?out ? ?in ?in ?mid ?out ? YES maps to YES: Suppose ? ?1 ?2 ?? ? is a Hamiltonian path New Hamiltonian path in ? : ?in ?mid ?out ?1 in ?1 mid ?1 out ?2 in ?? out ?in ?mid ?out 7
? ?out ?out ?in ? ? ? ?out ? ?in ?in ?mid ?out ? NO maps to NO: Suppose ? has a Hamiltonian path from ?in to ?out We deleted edges going into ?, so the path begins ?in ?mid ?out For every ?, path must eventually use edges ?in ?mid ?out Therefore, the path has the form ?in ?mid ?out ?1 in ?1 mid ?1 out ?2 in ?? out ?in ?mid ?out Hamiltonian path in ?: ? ?1 ?2 ?? ? 8
NP-hard CIRCUIT-SAT DIRECTED-HAM-PATH UNDIRECTED-HAM-PATH CLIQUE NP-complete 3-SAT SUBSET-SUM NP P 9
Hamiltonian cycles Let ? be an undirected graph A Hamiltonian cycle is a cycle that visits every vertex exactly once Let UNDIRECTED-HAM-CYCLE = { ? ? is an undirected graph with at least one Hamiltonian cycle} Theorem: UNDIRECTED-HAM-CYCLE is NP-complete 10
UNDIRECTED-HAM-CYCLE is NP-complete Proof: First note that UNDIRECTED-HAM-CYCLE NP(why?) To prove NP-hardness, we do a reduction from UNDIRECTED-HAM-PATH 11
? ? From paths to cycles ? ? Reduction: Given ?,?,? , add one new vertex ? and two new edges {?,? } and {?,? } Poly-time computable ? YES maps to YES ? ? ? NO maps to NO ? 12
NP-hard DIRECTED-HAM-PATH CIRCUIT-SAT CLIQUE UNDIRECTED-HAM-PATH NP-complete UNDIRECTED-HAM-CYCLE 3-SAT SUBSET-SUM NP P 13
Comparison: Eulerian cycles Let ? be an undirected graph An Eulerian cycle is a cycle that traverses every edge exactly once (possibly visiting some vertices multiple times) 14
Eulerian cycles vs. Hamiltonian cycles Which graphs have Eulerian cycles? Let ?be a simple, undirected, connected graph Euler s Theorem: ? has an Eulerian cycle if and only if every vertex has even degree (Proof omitted) Which graphs have Hamiltonian cycles? There is probably no good answer to this question! 15
NP-hard DIRECTED-HAM-PATH CIRCUIT-SAT CLIQUE UNDIRECTED-HAM-PATH NP-complete UNDIRECTED-HAM-CYCLE 3-SAT SUBSET-SUM NP P 16
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, 17
Proving that ?NEW is NP-complete (cheat sheet) 1. Prove that ?NEW NP What is the certificate? How can you verify a purported certificate in polynomial time? 2. Prove that ?NEW is NP-hard Which NP-complete language ?OLD are you reducing from? What is the reduction? Given ?, construct ? . How is ? defined? Polynomial time? YES maps to YES: Assume there is a certificate ? showing ? ?OLD. In terms of ?, describe a certificate ? showing that ? ?NEW. NO maps to NO: (Contrapositive) Assume there is a certificate ? showing ? ?NEW. In terms of ?, describe a certificate ? showing that ? ?OLD. 18
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! 19
Complexity of factoring integers Recall FACTOR = ?,? ? has a prime factor ? ? In most cases, if a language ? is in NP, then we can either prove ? P or we can prove that ? is NP-complete FACTOR is one of the rare exceptions to this rule Conjecture:FACTOR is neither in P nor NP-complete! 20
FACTOR = ?,? ? has a prime factor ? ? PRIMES = ? ? is prime NP-hard 3-SAT NP-complete FACTOR is probably here. NP-intermediate NP PRIMES P 21
Complexity of factoring integers Why do experts expect that FACTOR is not NP-complete? Key: The complexity class coNP Informal definition: coNP is like NP, except that we swap the roles of yes and no 22
The complexity class coNP Let ? 0,1 Definition:? coNP if there exists a randomized polynomial-time Turing machine ? such that for every ? 0,1 : If ? ?, then Pr ? accepts ? = 1 If ? ?, then Pr ? accepts ? 1 23
The complexity class coNP Let ? 0,1 and let ? = 0,1 ? Fact: ? NP if and only if ? coNP coNP is the set of complements of languages in NP What is coP? A: The set of languages that are not in P B:coP = P D:The notion of coP doesn t make any sense C: The set of algorithms that do not run in polynomial time Respond at PollEv.com/whoza or text whoza to 22333 24
The complexity class coNP Example: We say that a Boolean formula is unsatisfiable if it is not satisfiable Let 3-UNSAT = { ? ? is an unsatisfiable 3-CNF formula} Then 3-UNSAT coNP, because a satisfying assignment is a certificate showing that ? 3-UNSAT 25
FACTOR coNP FACTOR = { ?,? ? has a prime factor ? such that ? ?} Claim:FACTOR coNP Proof: Given ?,? : Nondeterministically guess numbers ? log? and ?1,?2, ,?? ? If ?1, ,?? are prime, ?1 ?2 ?3 ??= ?, and min ?1, ,?? > ?, reject Otherwise, accept PRIMES P 26
