Documentation

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

Explicit slack amplification for the conditional MinKT reduction #

The final clock is enlarged constructively so that its base-two logarithm pays the paired-estimator loss, the condition-estimator loss, the SoI loss, and the fixed pair compiler overhead. This removes the two abstract LossBudget inequalities from the exact two-query reduction.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Iterated.Slack.finalClock_source_le (clock : ) (additive compilerLoss outputLength conditionLength time : ) :
time finalClock clock additive compilerLoss outputLength conditionLength time

The slack-amplified clock dominates the source time.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Iterated.Slack.finalClock_iterateFour_le (clock : ) (additive compilerLoss outputLength conditionLength time : ) :
clockIterate clock 4 (totalTime outputLength conditionLength time) finalClock clock additive compilerLoss outputLength conditionLength time

The slack-amplified clock dominates the fourfold query clock.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Iterated.Slack.slackExponent_le_log_finalClock (clock : ) (additive compilerLoss outputLength conditionLength time : ) :
slackExponent clock additive compilerLoss outputLength conditionLength time Nat.log 2 (finalClock clock additive compilerLoss outputLength conditionLength time)

The final logarithmic slack contains its complete explicit loss exponent.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Iterated.Slack.lowerLoss_budget {clock : } (hclock : Monotone clock) (additive compilerLoss : ) (inst : MINCKT.Instance) :
(ordinaryParameters clock).logarithmicSlack ((plan clock compilerLoss).pairInput inst) + logarithmicSoILoss clock additive ((plan clock compilerLoss).soiTime inst) + (plan clock compilerLoss).correction inst (parameters clock additive compilerLoss).logarithmicSlack inst

Monotonicity moves all three query losses from t' to the total source parameter, after which the amplified final slack pays them.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Iterated.Slack.upperLoss_budget (clock : ) (compilerLoss : ) (inst : MINCKT.Instance) :
(ordinaryParameters clock).logarithmicSlack ((plan clock compilerLoss).conditionInput inst) + (plan clock compilerLoss).pairUpperLoss inst (plan clock compilerLoss).correction inst

The constructive correction exactly pays the condition-query and compiler losses.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Iterated.Slack.IsRegularClock.compatible {ordinaryTapes conditionalTapes : } {clock : } {additive compilerLoss : } {ordinaryMachine : TM ordinaryTapes} {conditionalMachine : OracleTM conditionalTapes} (hclock : IsRegularClock clock) (hpair : ∀ (inst : MINCKT.Instance), ordinaryMachine.timeBoundedKolmogorovComplexity (pair inst.output inst.condition) ((plan clock compilerLoss).pairInputTime inst) inst.complexity conditionalMachine + ordinaryMachine.timeBoundedKolmogorovComplexity inst.condition inst.time + ((plan clock compilerLoss).pairUpperLoss inst)) :
Compatible (plan clock compilerLoss) ordinaryMachine conditionalMachine (ordinaryParameters clock) (parameters clock additive compilerLoss) clock (logarithmicSoILoss clock additive)

Slack amplification and the paired upper-chain theorem produce the full compatibility contract with no remaining clock or loss hypotheses.

theorem Complexity.GapMINCKT.DifferenceEstimator.Unconditional.Iterated.Slack.IsRegularClock.compatible_of_pairComposition {ordinaryTapes conditionalTapes : } {clock : } {additive compilerLoss : } {composition : PairCompositionPlan} {ordinaryMachine : TM ordinaryTapes} {conditionalMachine : OracleTM conditionalTapes} (hclock : IsRegularClock clock) (hsupports : SupportsPairUpper (plan clock compilerLoss) composition ordinaryMachine conditionalMachine) :
Compatible (plan clock compilerLoss) ordinaryMachine conditionalMachine (ordinaryParameters clock) (parameters clock additive compilerLoss) clock (logarithmicSoILoss clock additive)

The operational condition-first compiler closes the last machine-specific premise of the slack-amplified schedule.