High Quality Content by WIKIPEDIA articles! In computational complexity theory, the Sipser–Lautemann theorem or Sipser–Gacs–Lautemann theorem states that BPP (Bounded-error Probabilistic Polynomial) time, is contained in the polynomial time hierarchy, and more specifically ?2 ? ?2. In 1983, Michael Sipser showed that BPP is contained in the polynomial time hierarchy. Peter Gacs showed that BPP is actually contained in ?2 ? ?2. Clemens Lautemann contributed by giving a simple proof of BPP's membership in ?2 ? ?2 , also in 1983. Michael Sipser's version of the proof works as follows. Without loss of generality, a machine M ? BPP with error ? 2-|x| can be chosen. (All BPP problems can be amplified to reduce the error probability exponentially.) The basic idea of the proof is to define a ?2 ? ?2 sentence that is equivalent to stating that x is in the language, L, defined by M by using a set of transforms of the random variable inputs.

Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.