Sipser–Lautemann theorem
id:
sipser-lautemann-theorem-312-16847891
title:
Sipser–Lautemann theorem
text:
In computational complexity theory, the Sipser–Lautemann theorem or Sipser–Gács–Lautemann theorem states that bounded-error probabilistic polynomial (BPP) 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. Péter Gács 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. It is conject
brand slug:
wiki
category slug:
encyclopedia
description:
Bounded-error probabilistic polynomial time is contained in the polynomial time hierarchy
original url:
https://en.wikipedia.org/wiki/Sipser%E2%80%93Lautemann_theorem
date created:
date modified:
2023-11-17T20:19:46Z
main entity:
{"identifier":"Q7525845","url":"https://www.wikidata.org/entity/Q7525845"}
image:
fields total:
13
integrity:
14