Documentation

Complexitylib.Metacomplexity.MCSP.Magnification.AntiChecker.Generator.Size.Defs

Anti-checker generator size bounds -- definitions #

The full selector repeats an exhaustive minimum circuit and then pads its output. These definitions give a coarse finite bound for that construction and an explicit overhead transformation suitable for the published 2^n * 2^(k * beta * n) generator interface.

source
def Complexity.GapMCSP.Magnification.AntiCheckerLemma.generatorOverheadSlack :
ℕ

Additive exponent slack used to absorb the sample-count factors and fixed polynomial overhead of the exhaustive selector.

Equations
Instances For
    source
    def Complexity.GapMCSP.Magnification.AntiCheckerLemma.generatorOverheadFromCounter (counterOverhead : ℕ) :
    ℕ

    Generator overhead obtained from the per-counter overhead.

    Equations
    Instances For
      source
      def Complexity.GapMCSP.Magnification.AntiCheckerLemma.selectionSizeFactor (counterOverhead : ℕ) (beta : PositiveRationalScale) (arity : ℕ) :
      ℕ

      Coarse factor accounting for every selection round and its counter.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        source
        def Complexity.GapMCSP.Magnification.AntiCheckerLemma.paddedSelectionSizeBound (counterOverhead : ℕ) (beta : PositiveRationalScale) (arity : ℕ) :
        ℕ

        Finite upper bound used for the complete padded selection circuit.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For