L/poly
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 a polynomially bounded advice function f 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 belongs to L if and only if machine M accepts the input x,f(.[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.
References
- ^ 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 9783540410324.
- ^ 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.