Misplaced Pages

#567432

22-413: ZPL may refer to: ZPL (complexity) , a complexity class ZPL (programming language) , for scientific applications Zebra Programming Language , for label printers Zope Public License Lachixío Zapotec language (ISO 639-3 language code) Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with

44-403: A Turing machine accepts any word in the language for an appropriate choice of certificate in its additional input tape, and rejects any word not in the language regardless of the certificate. Cem Say and Abuzer Yakaryılmaz have proven that the deterministic logarithmic-space Turing machine in the statement above can be replaced by a bounded-error probabilistic constant-space Turing machine that

66-438: A deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that: This was the strongest deterministic-space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have PSPACE = NPSPACE . Suppose C

88-604: A random computation path of length n , and execute this 2 times. Because no computation path exceeds length n , and because there are 2 computation paths in all, we have a good chance of hitting the accepting one (bounded below by a constant). The only problem is that we don't have room in log space for a binary counter that goes up to 2 . To get around this we replace it with a randomized counter, which simply flips n coins and stops and rejects if they all land on heads. Since this event has probability 2 , we expect to take 2 steps on average before stopping. It only needs to keep

110-521: A running total of the number of heads in a row it sees, which it can count in log space. Because of the Immerman–Szelepcsényi theorem , according to which NL is closed under complements, the one-sided error in these probabilistic computations can be replaced by zero-sided error. That is, these problems can be solved by probabilistic Turing machines that use logarithmic space and never make errors. The corresponding complexity class that also requires

132-420: Is a composite number (a number which is not prime). Here the domain of the complement is the set of all integers exceeding one. There is a Turing reduction from every problem to its complement problem. The complement operation is an involution , meaning it "undoes itself", or the complement of the complement is the original problem. One can generalize this to the complement of a complexity class , called

154-524: Is a generalization of L , the class for logspace problems on a deterministic Turing machine . Since any deterministic Turing machine is also a nondeterministic Turing machine , we have that L is contained in NL . NL can be formally defined in terms of the computational resource nondeterministic space (or NSPACE) as NL = NSPACE (log n ). Important results in complexity theory allow us to relate this complexity class with other classes, telling us about

176-419: Is a superset of that class which is closed under complement. The closure under complement is the smallest such class. If a class is intersected with its complement, we obtain a (possibly empty) subset which is closed under complement. Every deterministic complexity class ( DSPACE (f(n)), DTIME (f(n)) for all f(n)) is closed under complement, because one can simply add a last step to the algorithm which reverses

198-436: Is allowed to use only a constant number of random bits. There is a simple logical characterization of NL : it contains precisely those languages expressible in first-order logic with an added transitive closure operator. The class NL is closed under the operations complementation, union, and therefore intersection, concatenation , and Kleene star . Complement (complexity) In computational complexity theory ,

220-466: Is known that NL is equal to ZPL , the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error. It is not, however, known or believed to be equal to RLP or ZPLP , the polynomial-time restrictions of RL and ZPL , which some authors refer to as RL and ZPL . We can relate NL to deterministic space using Savitch's theorem , which tells us that any nondeterministic algorithm can be simulated by

242-419: Is more frequently used to refer to randomized logarithmic space , which is not known to equal NL . Several problems are known to be NL-complete under log-space reductions , including ST-connectivity and 2-satisfiability . ST-connectivity asks, for nodes S and T in a directed graph , whether T is reachable from S . 2-satisfiability asks, given a propositional formula of which each clause

SECTION 10

#1732797919568

264-462: Is not limited to polynomial time, because although it has a polynomial number of configurations it can use randomness to escape an infinite loop. If we do limit it to polynomial time, we get the class RL , which is contained in but not known or believed to equal NL . There is a simple algorithm that establishes that C = NL . Clearly C is contained in NL , since: To show that NL is contained in C , we simply take an NL algorithm and choose

286-491: Is still in the class. Because there are Turing reductions from every problem to its complement, any class which is closed under Turing reductions is closed under complement. Any class which is closed under complement is equal to its complement class. However, under many-one reductions , many important classes, especially NP , are believed to be distinct from their complement classes (although this has not been proven). The closure of any complexity class under Turing reductions

308-416: Is the complexity class of decision problems solvable in logarithmithic space with probabilistic Turing machines that never accept incorrectly but are allowed to reject incorrectly less than 1/3 of the time; this is called one-sided error . The constant 1/3 is arbitrary; any x with 0 ≤ x < 1/2 would suffice. It turns out that C = NL . Notice that C , unlike its deterministic counterpart L ,

330-430: Is the disjunction of two literals, if there is a variable assignment that makes the formula true. An example instance, where ¬ {\displaystyle \neg } indicates not , might be: It is known that NL is contained in P , since there is a polynomial-time algorithm for 2-satisfiability , but it is not known whether NL = P or whether L = NL . It is known that NL = co-NL , where co-NL

352-509: Is the class of languages whose complements are in NL . This result (the Immerman–Szelepcsényi theorem ) was independently discovered by Neil Immerman and Róbert Szelepcsényi in 1987; they received the 1995 Gödel Prize for this work. In circuit complexity , NL can be placed within the NC hierarchy. In Papadimitriou 1994, Theorem 16.1, we have: More precisely, NL is contained in AC . It

374-401: The complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement problem. For example, one important problem is whether a number is a prime number . Its complement is to determine whether a number

396-401: The complement class , which is the set of complements of every problem in the class. If a class is called C , its complement is conventionally labelled co-C . Notice that this is not the complement of the complexity class itself as a set of problems, which would contain a great deal more problems. A class is said to be closed under complement if the complement of any problem in the class

418-660: The answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases. Similarly, probabilistic classes such as BPP , ZPP , BQP or PP which are defined symmetrically with regards to their yes and no instances are closed under complement. In contrast, classes such as RP and co-RP define their probabilities with one-sided error, and so are not (currently known to be) closed under complement. Some of

440-422: The machine to use only polynomial time is called ZPLP . Thus, when we only look at space, it seems that randomization and nondeterminism are equally powerful. NL can equivalently be characterised by certificates , analogous to classes such as NP . Consider a deterministic logarithmic-space bounded Turing machine that has an additional read-only read-once input tape. A language is in NL if and only if such

462-400: The relative power of the resources involved. Results in the field of algorithms , on the other hand, tell us which problems can be solved with this resource. Like much of complexity theory, many important questions about NL are still open (see Unsolved problems in computer science ). Occasionally NL is referred to as RL due to its probabilistic definition below; however, this name

SECTION 20

#1732797919568

484-445: The title ZPL . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=ZPL&oldid=1036473463 " Category : Disambiguation pages Hidden categories: Short description is different from Wikidata All article disambiguation pages All disambiguation pages ZPL (complexity) NL

#567432