The complexity class PP

Lax666725.UnboundedError · concepts/Lax666725/UnboundedError.lean · lax-666725

definition

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Definition

    A binary language belongs to PP\mathrm{PP} if a polynomial-time probabilistic machine answers correctly with probability strictly greater than 1/21/2 on every input. No constant or inverse-polynomial lower bound on the advantage over 1/21/2 is imposed. We use the strict-correctness convention on both members and nonmembers; ties do not count as success.

    Concept map
    3 concepts; 1 descendant hidden
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A

    Lean source view on GitHub

    1import Lax666725.ProbabilisticMachines
    2
    3/-!
    4---
    5title: The complexity class PP
    6type: definition
    7---
    8A binary language belongs to PP\mathrm{PP} if a polynomial-time
    9probabilistic machine answers correctly with probability strictly greater
    10than 1/21/2 on every input. No constant or inverse-polynomial lower bound
    11on the advantage over 1/21/2 is imposed. We use the strict-correctness
    12convention on both members and nonmembers; ties do not count as success.
    13-/
    14
    15namespace Lax666725.UnboundedError
    16
    17open Lax434930.PolynomialTime ProbabilisticMachines
    18
    19def PP : Set Language :=
    20 {L | ∃ A : Procedure Bool, ∀ x, (1 / 2 : ℚ) < A.probability x (Correct L x)}
    21
    22end Lax666725.UnboundedError
    23
    Builds on
    Used by
    From Mathlib

    none

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…