The Classes L and NLSublinear complexityL and NL defined{0k1k | k0}  LPATH  NLThe Classes L and NL The Classes L and NL Section 8.4 Giorgi Japaridze Theory of ComputabilitySublinear complexity 8.4.aGiorgi Japaridze Theory of ComputabilitySublinear (less than linear) time complexity does not make sense (why?).But it does make sense as space complexity. We need to slightly modifyour TM model of computation though. The modification consists in separating the input tape from the worktape. The work tape remains read/write, but the input tape is read-only. When counting space complexity, we only look at how many cells of the work tape are utilized. This separation is not artificial. In real life, it is often the case that read-only input is bigger than the computer’s memory (“work tape”).CD-ROM is an example. Or, if we want to focus on fast computations, computer’s memory becomes even more limited --- registers only. Logarithmic space computability can be seen as computability with registers only. Or, more generally, computability with memory that is “much smaller than” input.L and NL defined 8.4.bGiorgi Japaridze Theory of ComputabilityDefinition 8.17 1. L is the class of languages that are decidable in logarithmic space on a deterministic Turing machine. In other words, L = SPACE(log n) 2. NL is the class of languages that are decidable in logarithmic spaceon a nondeterministic Turing machine. In other words, NL = NSPACE(log n){0k1k | k0}  L 8.4.cGiorgi Japaridze Theory of ComputabilityExample 8.18 Remember the machine for {0k1k | k0} from Section7.1, which works by zigzagging back and forth. What is its space complexity?To improve space (but not time!) complexity, we can set up a differentmachine. Instead of zigzagging, such a machine just makes one passthrough the input, and records on its work tape --- in the binary notation --- the number m of 0s and the number n of 1s. Holding m and n requires only logarithmic space. Then the machine compares these two numbers by zigzagging. This does not take any additional space.PATH  NL 8.4.dGiorgi Japaridze Theory of ComputabilityExample 8.19 Remember our polynomial-time algorithm for PATH from Section 7.2, which works by marking nodes. What is its space complexity?We can set up a nondeterministic logarithmic space machine for PATH. Starting from s as the “current node”, every time it guesses a next node--- among the nodes pointed to by the current node --- and jumps to it, until it hits t or has already visited more nodes than the number of nodes in the graph without hitting t. In the former case it accepts, and in the latter case rejects. At any time, the machine thus only needs to remember “the currentnode”, as well as the node count. How much space do these two pieces of information take? So, the whole algorithm runs in logarithmic