Documentation

Complexitylib.Circuits.DepthThree.LowerBound.Internal.TapeCancelStep

Unrestricted depth-three lower bound: tape cancel step #

Adapted from OpenAI's formalization at revision adc7f1241b42e322a6451854ab7e4b4c146bf78a. Source: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/lean/OAI/Computability/DepthThree/TapeCancelStep.lean

Imports, namespaces, module visibility, documentation, and formatting are adapted for complexitylib. The source theorem statements and mathematical proofs are retained.

source
@[reducible, inline]
abbrev Complexity.DepthThreeLowerBound.TapeCancelStep.ReadState :
Type

Control states for the read stage of the cancel step routine.

Equations
Instances For
    source
    @[reducible, inline]
    abbrev Complexity.DepthThreeLowerBound.TapeCancelStep.FirstState :
    Type

    Control states for the first stage of the cancel step routine.

    Equations
    Instances For
      source
      @[reducible, inline]
      abbrev Complexity.DepthThreeLowerBound.TapeCancelStep.State :
      Type

      Control states of the cancel step routine.

      Equations
      Instances For
        source
        def Complexity.DepthThreeLowerBound.TapeCancelStep.readProgram (v : Bool) :
        TapeMultiProgram ReadState

        Transition function for the read stage of the cancel step routine.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          source
          def Complexity.DepthThreeLowerBound.TapeCancelStep.firstProgram (v : Bool) :
          TapeMultiProgram FirstState

          Transition function for the first stage of the cancel step routine.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            source
            def Complexity.DepthThreeLowerBound.TapeCancelStep.program (v : Bool) :
            TapeMultiProgram State

            Transition function of the cancel step routine.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              source
              def Complexity.DepthThreeLowerBound.TapeCancelStep.start :
              State

              Initial control state of the cancel step routine.

              Equations
              Instances For
                source
                def Complexity.DepthThreeLowerBound.TapeCancelStep.done :
                State

                Terminal control state of the cancel step routine.

                Equations
                Instances For
                  source
                  def Complexity.DepthThreeLowerBound.TapeCancelStep.resultStore (σ : TapeStore) (j k : ℕ) (out : List Bool) :
                  TapeStore

                  Tape-store contents at the result stage of the cancel step routine.

                  Equations
                  • One or more equations did not get rendered due to their size.
                  Instances For
                    source
                    theorem Complexity.DepthThreeLowerBound.TapeCancelStep.runs_step (v : Bool) (σ : TapeStore) (j k : ℕ) (hA : σ TapeRegister.indexA = List.replicate j true) (hC : σ TapeRegister.indexC = List.replicate k true) (hj : j < (σ TapeRegister.polyBits).length) (hk : k < (σ TapeRegister.productBits).length) :
                    RunsIn (program v).step (TapeMultiProgram.cfg start (storeTapes σ)) (TapeMultiProgram.cfg done (storeTapes (resultStore σ j k (xorListAt (σ TapeRegister.productBits) k (v && (σ TapeRegister.polyBits).getD j false))))) (2 * j + 2 * k + 15)
                    source
                    @[simp]
                    theorem Complexity.DepthThreeLowerBound.TapeCancelStep.program_done (v : Bool) (h : TapeHeads) :
                    program v done h = none