L/poly: Difference between revisions
Content deleted Content added
improve sourcing and expand |
m Open access bot: doi added to citation with #oabot. |
||
| (10 intermediate revisions by 6 users not shown) | |||
| Line 1: | Line 1: | ||
In [[computational complexity theory]], '''L/poly''' is the [[complexity class]] of [[logarithmic space]] machines with a polynomial amount of [[advice (complexity)|advice]]. L/poly is a [[Circuit complexity|non-uniform]] logarithmic space class, analogous to the non-uniform polynomial time class [[P/poly]].<ref>{{ComplexityZoo|L/poly|L#l.2Fpoly}}.</ref> |
In [[computational complexity theory]], '''L/poly''' is the [[complexity class]] of [[logarithmic space]] machines with a polynomial amount of [[advice (complexity)|advice]]. L/poly is a [[Circuit complexity|non-uniform]] logarithmic space class, analogous to the non-uniform polynomial time class [[P/poly]].<ref>{{ComplexityZoo|L/poly|L#l.2Fpoly}}.</ref> |
||
Formally, for a [[formal language]] {{mvar|L}} to belong to L/poly, there must exist |
Formally, for a [[formal language]] {{mvar|L}} to belong to L/poly, there must exist an advice function {{mvar|f}} that maps an integer {{mvar|n}} to a string of length polynomial in {{mvar|n}}, and a [[Turing machine]] M with two read-only input tapes and one read-write tape of size logarithmic in the input size, such that an input {{mvar|x}} of length {{mvar|n}} belongs to {{mvar|L}} if and only if machine M accepts the input {{math|''x'', ''f''(''n'')}}.<ref name="t">{{citation|title=The Computational Complexity of Equivalence and Isomorphism Problems|volume=1852|series=Lecture Notes in Computer Science|first=Thomas|last=Thierauf|publisher=Springer-Verlag|year=2000|isbn=978-3-540-41032-4|page=66|url=https://books.google.com/books?id=e3xOiREJF4EC&pg=PA66}}.</ref> Alternatively and more simply, {{mvar|L}} is in L/poly if and only if it can be recognized by [[branching program]]s of polynomial size.<ref>{{citation |
||
| last = Cobham | first = Alan | authorlink = Alan Cobham |
| last = Cobham | first = Alan | authorlink = Alan Cobham |
||
| contribution = The recognition problem for the set of perfect squares |
| contribution = The recognition problem for the set of perfect squares |
||
| Line 8: | Line 8: | ||
| title = [[Symposium on Foundations of Computer Science|Proceedings of the 7th Annual IEEE Symposium on Switching and Automata Theory (SWAT 1966)]] |
| title = [[Symposium on Foundations of Computer Science|Proceedings of the 7th Annual IEEE Symposium on Switching and Automata Theory (SWAT 1966)]] |
||
| year = 1966}}.</ref> One direction of the proof that these two models of computation are equivalent in power is the observation that, if a branching program of polynomial size exists, it can be specified by the advice function and simulated by the Turing machine. In the other direction, a Turing machine with logarithmic writable space and a polynomial advice tape may be simulated by a branching program the states of which represent the combination of the configuration of the writable tape and the position of the Turing machine heads on the other two tapes. |
| year = 1966}}.</ref> One direction of the proof that these two models of computation are equivalent in power is the observation that, if a branching program of polynomial size exists, it can be specified by the advice function and simulated by the Turing machine. In the other direction, a Turing machine with logarithmic writable space and a polynomial advice tape may be simulated by a branching program the states of which represent the combination of the configuration of the writable tape and the position of the Turing machine heads on the other two tapes. |
||
In 1979, Aleliunas et al. showed that [[SL (complexity)|symmetric logspace]] is contained in L/poly.<ref>{{citation |
|||
| last1 = Aleliunas | first1 = Romas |
|||
| last2 = Karp | first2 = Richard M. | author2-link = Richard M. Karp |
|||
| last3 = Lipton | first3 = Richard J. | author3-link = Richard J. Lipton |
|||
| last4 = Lovász | first4 = László | author4-link = László Lovász |
|||
| last5 = Rackoff | first5 = Charles | author5-link = Charles Rackoff |
|||
| contribution = Random walks, universal traversal sequences, and the complexity of maze problems |
|||
| doi = 10.1109/SFCS.1979.34 |
|||
| location = New York |
|||
| mr = 598110 |
|||
| pages = 218–223 |
|||
| publisher = IEEE |
|||
| title = [[Symposium on Foundations of Computer Science|Proceedings of 20th Annual Symposium on Foundations of Computer Science]] |
|||
| year = 1979}}.</ref> However, this result was superseded by [[Omer Reingold]]'s result that SL collapses to uniform logspace.<ref>{{citation |
|||
| last = Reingold | first = Omer | author-link = Omer Reingold |
|||
| doi = 10.1145/1391289.1391291 |
|||
| issue = 4 |
|||
| journal = [[Journal of the ACM]] |
|||
| mr = 2445014 |
|||
| pages = 1–24 |
|||
| title = Undirected connectivity in log-space |
|||
| volume = 55 |
|||
| year = 2008}}.</ref> |
|||
[[BPL (complexity)|BPL]] is contained in L/poly, which is a variant of [[P/poly#Adleman's theorem|Adleman's theorem]].<ref>{{citation |
|||
| last = Nisan | first = Noam | authorlink = Noam Nisan |
|||
| doi = 10.1016/0304-3975(93)90258-U |
|||
| issue = 1 |
|||
| journal = Theoretical Computer Science |
|||
| mr = 1201169 |
|||
| pages = 135–144 |
|||
| title = On read-once vs. multiple access to randomness in logspace |
|||
| volume = 107 |
|||
| year = 1993| doi-access = free |
|||
}}.</ref> |
|||
==References== |
==References== |
||
{{reflist}} |
{{reflist}} |
||
{{DEFAULTSORT:L |
{{DEFAULTSORT:L Poly}} |
||
[[Category:Complexity classes]] |
[[Category:Complexity classes]] |
||
Latest revision as of 21:18, 5 July 2021
In computational complexity theory, L/poly is the complexity class of logarithmic space machines with a polynomial amount of advice. L/poly is a non-uniform logarithmic space class, analogous to the non-uniform polynomial time class P/poly.[1]
Formally, for a formal language L to belong to L/poly, there must exist an advice function f that maps an integer n to a string of length polynomial in n, and a Turing machine M with two read-only input tapes and one read-write tape of size logarithmic in the input size, such that an input x of length n belongs to L if and only if machine M accepts the input x, f(n).[2] Alternatively and more simply, L is in L/poly if and only if it can be recognized by branching programs of polynomial size.[3] One direction of the proof that these two models of computation are equivalent in power is the observation that, if a branching program of polynomial size exists, it can be specified by the advice function and simulated by the Turing machine. In the other direction, a Turing machine with logarithmic writable space and a polynomial advice tape may be simulated by a branching program the states of which represent the combination of the configuration of the writable tape and the position of the Turing machine heads on the other two tapes.
In 1979, Aleliunas et al. showed that symmetric logspace is contained in L/poly.[4] However, this result was superseded by Omer Reingold's result that SL collapses to uniform logspace.[5]
BPL is contained in L/poly, which is a variant of Adleman's theorem.[6]
References
[edit]- ^ Complexity Zoo: L/poly.
- ^ Thierauf, Thomas (2000), The Computational Complexity of Equivalence and Isomorphism Problems, Lecture Notes in Computer Science, vol. 1852, Springer-Verlag, p. 66, ISBN 978-3-540-41032-4.
- ^ Cobham, Alan (1966), "The recognition problem for the set of perfect squares", Proceedings of the 7th Annual IEEE Symposium on Switching and Automata Theory (SWAT 1966), pp. 78–87, doi:10.1109/SWAT.1966.30.
- ^ Aleliunas, Romas; Karp, Richard M.; Lipton, Richard J.; Lovász, László; Rackoff, Charles (1979), "Random walks, universal traversal sequences, and the complexity of maze problems", Proceedings of 20th Annual Symposium on Foundations of Computer Science, New York: IEEE, pp. 218–223, doi:10.1109/SFCS.1979.34, MR 0598110.
- ^ Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): 1–24, doi:10.1145/1391289.1391291, MR 2445014.
- ^ Nisan, Noam (1993), "On read-once vs. multiple access to randomness in logspace", Theoretical Computer Science, 107 (1): 135–144, doi:10.1016/0304-3975(93)90258-U, MR 1201169.