NL equals coNLSlide 2The statement of the theorem and the main lemma (*)Solving PATH’ when c is knownComputing the number cL, NL and coNL versus P and PSPACENL equals coNLNL equals coNLSection 8.6 Giorgi Japaridze Theory of ComputabilityGiorgi Japaridze Theory of ComputabilityNL equals coNLNL equals coNLSection 8.6The statement of the theorem and the main lemma (*) 8.6.aGiorgi Japaridze Theory of ComputabilityTheorem 8.27 NL = coNL. Proof Idea. It is sufficient to prove the following: PATHcoNL, i.e. PATH’NL (*)coNL is defined as {A | the complement A’ of A is in NL}. Indeed, assuming that (*) holds, consider any language A in NL. Since PATH is NL-complete, there is a log space reduction f of A to PATH. The same f, of course, is also a log space reduction of A’ to PATH’. By (*), however, PATH’NL. Hence A’NL and thus AcoNL. For the opposite direction, consider any language A in coNL, so that A’NL. Then there is a log space reduction f of A’ to PATH. Hence f is also a reduction of A to PATH’. By (*), however, PATH’NL. So,ANL. To summarize, as long as (*) is true, we have ANL iff AcoNL for all A, meaning that NL=coNL. It remains to understand why (*) holds. This will be done through constructing an NL algorithm M for PATH’.Solving PATH’ when c is known 8.6.bGiorgi Japaridze Theory of ComputabilityLet c be the number of nodes in graph G that are reachable from the start node s, and assume c is already known. Let m be the number of all nodes.One by one, M goes through all nodes of G and nondeterministically guesses whether each node is reachable from s. Whenever a node u is guessed to be reachable, M verifies this guess by additionally guessing a path (of length m) from s to u, and rejects if the guessed path does not hit u. In addition, if the target node t is ever guessed to be reachable, M rejects. M counts the number of nodes (successfully) guessed to be reachable and, once this number hits c, M accepts. That is because M knows that the remaining nodes, including t, are not reachable, so there is no path from s to t.It now remains to see how M can compute c in logarithmic space.Computing the number c 8.6.cGiorgi Japaridze Theory of ComputabilityFor each i=0,1,...,m, let Ai be the set of nodes at a distance i from s, and ci be the number of such nodes. Thus, c0=1 and cm=c. M calculates ci+1 from ci by going through all the nodes of G, determining whether each is a member of Ai+1, and counting the members.To determine whether a node v is in Ai+1, M uses an inner loop to go through all the nodes of G and guesses whether each node is in Ai. Eachpositive guess is verified by a path of length i from s. For each node u verified to be in Ai, M tests whether (u,v) is an edge of G. If it is an edge,v is in Ai+1. Additionally, the number of nodes verified to be in Ai is counted. At the completion of the inner loop, if the total number of nodes verified to be in Ai is not ci, not all members of Ai have been found, so this computation branch rejects. If the count equals ci and v has not yetbeen shown to be in Ai+1, M concludes that it isn’t in Ai+1. Then M goes on to the next v in the outer loop.L, NL and coNL versus P and PSPACE 8.6.dGiorgi Japaridze Theory of ComputabilityThis is what we know:1. L  NL = coNL  P  PSPACE2. L, NL, coNL  PSPACEOpen problems:1. L = NL, coNL?2. NL, coNL = P?3. P = PSPACE?At least one of these two equalities does not hold;but which one we do not know (probably