CoNL in Complexity Theory and NL Theorem
"Explore the relationship between NL and coNL in Complexity Theory with insights on the NL=coNL Theorem, the proof process, and the use of the PATH problem. Discover the intriguing challenges and uncertainties in this complex domain."
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 281- Complexity Theory NL=coNL
NL=coNL Theorem: NL=coNL Before presenting the proof, a few comments Recall: we do not know the relationship between NP and coNP
NL=coNL Theorem: NL=coNL Before presenting the proof, a few comments Recall: we do not know the relationship between NP and coNP (and best guess is that NP coNP and P NP,P coNP)
NL=coNL Theorem: NL=coNL Before presenting the proof, a few comments Recall: we do not know the relationship between NP and coNP (and best guess is that NP coNP and P NP,P coNP) We do not know whether L NL
NL=coNL Theorem: NL=coNL Before presenting the proof, a few comments Recall: we do not know the relationship between NP and coNP (and best guess is that NP coNP and P NP,P coNP) We do not know whether L NL The proof is not long, but it is tricky
NL=coNL - the proof Theorem: NL=coNL Proof: We shall use the PATH problem, that reduces ndTm acceptance to PATH the directed graph with vertices corresponding to ndTM configurations, and edges corresponding to valid moves of the ndtM. The question is whether there is a path from distinguished vertex s to a distinguished vertex t. We want to prove PATH NL Let A= v V there is a directed path from s to v} PATH NL iff t A
NL=coNL - the proof Theorem: NL=coNL PATH NL iff t A (A= v V there is a directed path from s to v}) We shall prove Lemma: Assume we know a=|A|. Then there is an algorithm in NL that accepts PATH.
NL=coNL - the proof PATH NL iff t A (A= v V there is a directed path from s to v} Lemma: Assume we know a=|A|. Then there is an algorithm in NL that accepts PATH. Proof: (strategy) Find all vertices of A (nondeterministically) Verify that t is not one of the vertices of A.
NL=coNL - the proof PATH NL iff t A (A= v V there is a directed path from s to v} Lemma: Assume we know a=|A|. Then there is an algorithm in NL that accepts PATH. Proof: (strategy) Find all vertices of A (nondeterministically) Since we know |A|, we can make sure that we found all of A. So we can verify that t is not one of the vertices of A.
NL=coNL - the proof PATH NL iff t A (A= v V there is a directed path from s to v}) Lemma: Assume we know a=|A|. Then there is an algorithm in NL that accepts PATH. Proof: count=0 for all v V [enumerate in lexicographic order] guess whether v A. If so certify that there is a path from s to v count++; [this is in NL] if count = a accept
NL=coNL - the proof PATH NL iff t A (A= v V there is a directed path from s to v}) Lemma: Assume we know a=|A|. Then there is an algorithm in NL that accepts PATH. Proof: count=0 for all v V [enumerate in lexicographic order] guess whether v A. If so certify that there is a path from s to v count++; if (cannot find the path reject); [this is in NL] if count = a accept
NL=coNL - the proof PATH NL iff t A (A= v V there is a directed path from s to v}) Lemma: Assume we know a=|A|. Then there is an algorithm in NL that accepts PATH. Proof: count=0 for all v V [enumerate in lexicographic order] guess whether v A. If so certify that there is a path from s to v count++; if (cannot find the path reject); if (path found and v=t) reject [this is in NL] if count = a accept
NL=coNL - the proof PATH NL iff t A (A= v V there is a directed path from s to v}) Lemma: Assume we know a=|A|. Then there is an algorithm in NL that accepts PATH. Note note that A= Aiwhere Ai= v V there is a directed path of length at most i from s to v} We shall sketch the NL algorithm that can compute |Ai| given |Ai-1| This will prove the theorem because A|V|-1 = A, and the lemma guarantees that given |A| we can accept PATH.
NL=coNL Ai= v V there is a directed path of length at most i from s to v} A0= {s}, |A0|=1 We will compute Ai by generating all vertices reachable from Ai-1 through an edge. So, actually, we will generate all vertices of Aiin lexicographical order. As in the lemma we will also certify the membership vertex in Ai of each such vertex.
NL=coNL Ai= v V there is a directed path of length at most i from s to v} A0= {s}, |A0|=1 We will compute Ai by generating all vertices reachable from Ai-1 through an edge. So, actually, we will generate all vertices of Aiin lexicographical order. As in the lemma we will also certify the membership vertex in Ai of each such vertex. As before, the trick will be to generate vertices in lexicographical order
NL=coNL Ai= v V there is a directed path of length at most i from s to v} A0= {s}, |A0|=1 Inductive step: we can generate Ai-1in lexicographical order
NL=coNL Ai= v V there is a directed path of length at most i from s to v} A0= {s}, |A0|=1 Inductive step: we can generate Ai-1in lexicographical order Note: we take advantage of the fact that nondeterministic computation branches can fail.
NL=coNL Ai= v V there is a directed path of length at most i from s to v} A0= {s}, |A0|=1 Inductive step: we can generate Ai-1in lexicographical order Algorithm: for each v V [lexicographical order] for each u Ai-1. check if there is an edge (u,v) in G or v=s ; if so v Ai
NL=coNL Ai= v V there is a directed path of length at most i from s to v} A0= {s}, |A0|=1 Inductive step: we can generate Ai-1in lexicographical order Algorithm: for each v V [lexicographical order] for each u Ai-1. check if there is an edge (u,v) in G or v=s; if so v Ai Note that there are many, many ways to make incorrect choices, but we find out that they are incorrect, and reject . The important point is that we find the correct computation if there is one.
NL=coNL Ai= v V there is a directed path of length at most i from s to v} A0= {s}, |A0|=1 Inductive step: assume we can generate Ai-1in lexicographical order Algorithm: for each v V [lexicographical order] for each u Ai-1. check if there is an edge (u,v) in G or v=s; if so v Ai This enumerates Aiin lexicographical order
NL=coNL -- space analysis Inductive step: assume we can generate Ai-1in lexicographical order Algorithm: for each v V [lexicographical order] for each u Ai-1. check if there is an edge (u,v) in G or v=s; if so v Ai Note that for each inductive step i we only need to remember O(log n): i A constant number of vertex names from Ai-1 A constant number of vertex names from Ai
NL=coNL Study the complete proof in Sipser. Moral: it pays to consider recursive calls as black boxes. Do not look inside them!
