Documentation

Complexitylib.Metacomplexity.MINCKT.Gap.Difference.SoI.Unconditional

Building the conditional difference estimator from one ordinary estimator #

One unconditional Fact 3.4 estimator is queried on a paired string and on its condition. Under the explicit clock/loss compatibility contract, those two queries instantiate every surrounding input of the SoI accounting theorem. Consequently their adjusted difference satisfies the conditional estimator sandwich and solves GapMINCKT.

The remaining construction obligations are concentrated in Compatible: a concrete upper-chain evaluator, the paper's iterated clock identities and dominations, and the finite logarithmic budget calculations.

@[simp]

The paired ordinary query contains the canonical pair.

@[simp]

The paired ordinary query uses the planned source clock.

@[simp]

The condition query contains exactly the condition string.

@[simp]

The condition query uses the planned source clock.

Every paired query belongs to the plan's exact estimator-query domain.

Every condition-only query belongs to the plan's exact estimator-query domain.

@[simp]
theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Plan.components_minuend (plan : Plan) (ordinaryEstimate : GapMINKT.Logarithmic.Estimator) (inst : MINCKT.Instance) :
(plan.components ordinaryEstimate).minuend inst = ordinaryEstimate (plan.pairInput inst)

The induced minuend is one application of the ordinary estimator to the paired query.

@[simp]
theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Plan.components_subtrahend (plan : Plan) (ordinaryEstimate : GapMINKT.Logarithmic.Estimator) (inst : MINCKT.Instance) :
(plan.components ordinaryEstimate).subtrahend inst = ordinaryEstimate (plan.conditionInput inst)

The induced subtrahend is one application of the same estimator to the condition query.

@[simp]

The induced difference retains the plan's explicit correction.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.SupportsPairUpper.pair_upper {ordinaryTapes conditionalTapes : } {plan : Plan} {composition : PairCompositionPlan} {ordinaryMachine : TM ordinaryTapes} {conditionalMachine : OracleTM conditionalTapes} (hsupports : SupportsPairUpper plan composition ordinaryMachine conditionalMachine) (inst : MINCKT.Instance) :
ordinaryMachine.timeBoundedKolmogorovComplexity (pair inst.output inst.condition) (plan.pairInputTime inst) inst.complexity conditionalMachine + ordinaryMachine.timeBoundedKolmogorovComplexity inst.condition inst.time + (plan.pairUpperLoss inst)

An operational condition-first compiler with attained minima proves the paired upper-chain field required by Compatible.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Compatible.satisfiesSoIInputs {ordinaryTapes conditionalTapes : } {plan : Plan} {ordinaryMachine : TM ordinaryTapes} {conditionalMachine : OracleTM conditionalTapes} {ordinaryParameters : GapMINKT.Logarithmic.Parameters} {conditionalParameters : Parameters} {soiClock soiLoss : } (hcompatible : Compatible plan ordinaryMachine conditionalMachine ordinaryParameters conditionalParameters soiClock soiLoss) {ordinaryEstimate : GapMINKT.Logarithmic.Estimator} (hestimate : ordinaryEstimate.SatisfiesBounds ordinaryMachine ordinaryParameters) :
(plan.components ordinaryEstimate).SatisfiesSoIInputs (plan.accountingSchedule ordinaryParameters) ordinaryMachine conditionalMachine conditionalParameters soiClock soiLoss

A valid unconditional estimator plus clock/loss compatibility instantiates all inputs surrounding the single SoI invocation.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Compatible.satisfiesSoIInputsOnQueries {ordinaryTapes conditionalTapes : } {plan : Plan} {ordinaryMachine : TM ordinaryTapes} {conditionalMachine : OracleTM conditionalTapes} {ordinaryParameters : GapMINKT.Logarithmic.Parameters} {conditionalParameters : Parameters} {soiClock soiLoss : } (hcompatible : Compatible plan ordinaryMachine conditionalMachine ordinaryParameters conditionalParameters soiClock soiLoss) {ordinaryEstimate : GapMINKT.Logarithmic.Estimator} (hestimate : ordinaryEstimate.SatisfiesBoundsOn ordinaryMachine ordinaryParameters plan.IsEstimatorQuery) :
(plan.components ordinaryEstimate).SatisfiesSoIInputs (plan.accountingSchedule ordinaryParameters) ordinaryMachine conditionalMachine conditionalParameters soiClock soiLoss

Estimator correctness is needed only on the two ordinary queries issued by the plan, not on every possible MINKT instance.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Compatible.satisfiesBounds {ordinaryTapes conditionalTapes : } {plan : Plan} {ordinaryMachine : TM ordinaryTapes} {conditionalMachine : OracleTM conditionalTapes} {ordinaryParameters : GapMINKT.Logarithmic.Parameters} {conditionalParameters : Parameters} {soiClock soiLoss : } (hcompatible : Compatible plan ordinaryMachine conditionalMachine ordinaryParameters conditionalParameters soiClock soiLoss) {ordinaryEstimate : GapMINKT.Logarithmic.Estimator} (hestimate : ordinaryEstimate.SatisfiesBounds ordinaryMachine ordinaryParameters) (hsoi : TimeBoundedSymmetryOfInformation ordinaryMachine conditionalMachine soiClock soiLoss) (hwidening : conditionalParameters.IsWidening) :
(plan.components ordinaryEstimate).estimate.SatisfiesBounds ordinaryMachine conditionalMachine conditionalParameters

Fully composed ordinary-estimator-plus-SoI construction of the conditional estimator sandwich.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Compatible.satisfiesBoundsOnQueries {ordinaryTapes conditionalTapes : } {plan : Plan} {ordinaryMachine : TM ordinaryTapes} {conditionalMachine : OracleTM conditionalTapes} {ordinaryParameters : GapMINKT.Logarithmic.Parameters} {conditionalParameters : Parameters} {soiClock soiLoss : } (hcompatible : Compatible plan ordinaryMachine conditionalMachine ordinaryParameters conditionalParameters soiClock soiLoss) {ordinaryEstimate : GapMINKT.Logarithmic.Estimator} (hestimate : ordinaryEstimate.SatisfiesBoundsOn ordinaryMachine ordinaryParameters plan.IsEstimatorQuery) (hsoi : TimeBoundedSymmetryOfInformation ordinaryMachine conditionalMachine soiClock soiLoss) (hwidening : conditionalParameters.IsWidening) :
(plan.components ordinaryEstimate).estimate.SatisfiesBounds ordinaryMachine conditionalMachine conditionalParameters

Query-local ordinary estimator correctness suffices for the fully composed conditional estimator sandwich.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Compatible.solvedBy {ordinaryTapes conditionalTapes : } {plan : Plan} {ordinaryMachine : TM ordinaryTapes} {conditionalMachine : OracleTM conditionalTapes} {ordinaryParameters : GapMINKT.Logarithmic.Parameters} {conditionalParameters : Parameters} {soiClock soiLoss : } (hcompatible : Compatible plan ordinaryMachine conditionalMachine ordinaryParameters conditionalParameters soiClock soiLoss) {ordinaryEstimate : GapMINKT.Logarithmic.Estimator} (hestimate : ordinaryEstimate.SatisfiesBounds ordinaryMachine ordinaryParameters) (hsoi : TimeBoundedSymmetryOfInformation ordinaryMachine conditionalMachine soiClock soiLoss) (hwidening : conditionalParameters.IsWidening) :
(GapMINCKT ordinaryMachine conditionalMachine conditionalParameters hwidening).SolvedBy (decisionOfEstimator (plan.components ordinaryEstimate).estimate)

Thresholding the adjusted difference of two ordinary estimator queries solves the exact conditional gap promise.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Compatible.mem_PromiseP {ordinaryTapes conditionalTapes : } {plan : Plan} {ordinaryMachine : TM ordinaryTapes} {conditionalMachine : OracleTM conditionalTapes} {ordinaryParameters : GapMINKT.Logarithmic.Parameters} {conditionalParameters : Parameters} {soiClock soiLoss : } (hcompatible : Compatible plan ordinaryMachine conditionalMachine ordinaryParameters conditionalParameters soiClock soiLoss) {ordinaryEstimate : GapMINKT.Logarithmic.Estimator} (hestimate : ordinaryEstimate.SatisfiesBounds ordinaryMachine ordinaryParameters) (hsoi : TimeBoundedSymmetryOfInformation ordinaryMachine conditionalMachine soiClock soiLoss) (hwidening : conditionalParameters.IsWidening) (hpolynomial : estimatorLanguage (plan.components ordinaryEstimate).estimate P) :
GapMINCKT ordinaryMachine conditionalMachine conditionalParameters hwidening PromiseP

If the induced threshold language is in P, the ordinary-estimator-plus- SoI construction places the exact conditional gap promise in PromiseP.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Compatible.mem_PromisePOnQueries {ordinaryTapes conditionalTapes : } {plan : Plan} {ordinaryMachine : TM ordinaryTapes} {conditionalMachine : OracleTM conditionalTapes} {ordinaryParameters : GapMINKT.Logarithmic.Parameters} {conditionalParameters : Parameters} {soiClock soiLoss : } (hcompatible : Compatible plan ordinaryMachine conditionalMachine ordinaryParameters conditionalParameters soiClock soiLoss) {ordinaryEstimate : GapMINKT.Logarithmic.Estimator} (hestimate : ordinaryEstimate.SatisfiesBoundsOn ordinaryMachine ordinaryParameters plan.IsEstimatorQuery) (hsoi : TimeBoundedSymmetryOfInformation ordinaryMachine conditionalMachine soiClock soiLoss) (hwidening : conditionalParameters.IsWidening) (hpolynomial : estimatorLanguage (plan.components ordinaryEstimate).estimate P) :
GapMINCKT ordinaryMachine conditionalMachine conditionalParameters hwidening PromiseP

Query-local ordinary estimator bounds and a polynomial-time induced completion place the exact conditional gap promise in PromiseP.