Complexity Theory and Logspace Computable Functions
Explore the world of Complexity Theory with a focus on Logspace computation functions, including definitions, interesting languages in L and NL, and the closure of L under composition. Learn about Turing machines, space complexity classes, and more in this informative overview.
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
L, NL Recall that we are using the model of Turing machine with a separate read-only input tape, and a work tape. The space used by such a Turing machine is the number of workspace squares used. SPACE(f(n)) is the class of languages decided by deterministic Turing machines that use O(f(n)) tape squares. NSPACE(f(n)) is the class of languages decided by nondeterministic Turing machines that use O(f(n)) tape squares.
L, NL Recall that we are using the model of Turing machine with a separate read-only input tape, and a work tape. The space used by such a Turing machine is the number of workspace squares used. Definition: L=SPACE(log n) NL=NSPACE(log n)
L, NL L=SPACE(log n) NL=NSPACE(log n) There are interesting languages in L, and in NL. The language {0n1n| n=0,1, } is in L The language {x#x | x is a string over {0,1} } is in L The language of properly nested parentheses (even with multiple parentheses symbols)
L, NL L=SPACE(log n) NL=NSPACE(log n) There are interesting languages in L, and in NL. The language {0n1n| n=0,1, } is in L The language {x#x | x is a string over {0,1} } is in L The language of properly nested parentheses (even with multiple parentheses symbols) PATH={<G,s,t> | directed graph G has a path from s to t} is in NL
L is closed under composition and g: be log space transducers. Theorem: Let f: Then h : transducer. defined by h(x)=f(g(x)) is computable by a log space The difficulty is that if |x|=n, the length of the intermediate result g(x) can be polynomial in n (n^k for some k depending on the transducer that computes g). A log space transducer does not have this much memory.
L is closed under composition and g: be log space transducers. Theorem: Let f: Then h : transducer. defined by h(x)=f(g(x)) is computable by a log space x N {0,1} be the function Solution: let gsbits: : gsbits(x,i) = i-th bit of g(x)
L is closed under composition and g: be log space transducers. Theorem: Let f: Then h : transducer. defined by h(x)=f(g(x)) is computable by a log space x N {0,1} be the function Solution: let gsbits: : gsbits(x,i) = i-th bit of g(x) gsbits is in L, The transducer computing f() always needs only one bit of g(x) to compute f(g(x)).
NL-complete languages B is NL-hard iff A NL A LB B is NL-complete (under logspace reductions) if B NL and B is NL-hard
NL-complete languages B is NL-hard iff A NL A LB B is NL-complete (under logspace reductions) if B NL and B is NL-hard Lemma: Lis transitive (A LB and B LC imply A LC )
NL-complete languages B is NL-hard iff A NL A LB B is NL-complete (under logspace reductions) if B NL and B is NL-hard Lemma: Lis transitive (A LB and B LC imply A LC ) Corollary: If B is NL-hard, and B L,then L = NL
GAP is NL-complete Proof: i. GAP is in NL. Given G,s,t a nondeterministic machine guesses the path. More precisely: current s while current t choose a vertex v such that (current,v) is an edge; current v
GAP is NL-complete Proof: i. GAP is in NL. Given G,s,t a nondeterministic machine guesses the path. More precisely: even more precisely current s; while number of steps is less than poly while current t choose a vertex v such that (current,v) is an edge; current v accept (and halt) reject
GAP is NL-complete Proof: i. GAP is in NL. Given G,s,t a nondeterministic machine guesses the path. ii. Every language in NL can be reduced to GAP
GAP is NL-complete Proof: i. GAP is in NL. Given G,s,t a nondeterministic machine guesses the path. ii. Every language in NL can be reduced to GAP We already know this (technique from previous proof: consider the graph of configurations of the NL acceptor)
