Gap conditional MinKT #
For a canonical input (x, y, 1^t, 1^s), this module exposes the exact
depth-adjusted promise used in Hirahara's 2022 route toward excluding
Heuristica:
- yes:
C_cond^t(x | y) + cd^(t,tau)(y) <= s; - no:
C_cond^tau(x | y) > s + log_2(tau).
The ordinary depth machine and conditional oracle machine remain explicit. Malformed encodings and intermediate-gap instances lie outside the promise.
The identity transform is an admissible conditional MinKT clock.
The unary threshold has exactly the represented length.
Canonical conditional gap encoding is injective.
Widening places the transformed clock after the source clock.
Under widening, depth plus later-clock complexity reconstructs the source-clock complexity of the condition exactly.
The depth-adjusted yes inequality is equivalent to a concrete source-clock program obeying that same adjusted description budget.
Every depth-adjusted yes-instance is, in particular, below its unadjusted source threshold.
The no condition says exactly that no program meets the transformed clock and logarithmically relaxed description budget.
Increasing the stored threshold preserves a yes-instance.
Decreasing the stored threshold preserves a no-instance.
Widening the clock prevents a depth-adjusted yes-instance from also satisfying the logarithmic no condition.
The estimator's upper sandwich bound places it below the threshold of every depth-adjusted yes-instance.
The estimator's lower sandwich bound places it strictly above the threshold of every logarithmic no-instance.
Canonical yes-language membership is the depth-adjusted upper bound.
Canonical no-language membership is the transformed-clock lower bound.
Under clock widening, the two encoded gap languages are disjoint.
On canonical codes, the estimator completion accepts exactly when its value is at most the stored threshold.
Executable estimator thresholding is the characteristic function of its completion language.
A valid estimator's completion contains every promised yes-instance.
A valid estimator's completion excludes every promised no-instance.
Thresholding a valid estimator accepts every promised yes-instance.
Thresholding a valid estimator rejects every promised no-instance.
Hirahara's widening-certified depth-adjusted conditional MinKT promise.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The promise's yes side is definitionally the canonical depth-adjusted language.
The promise's no side is definitionally the canonical transformed-clock language.
Proposition 6.2's numerical core: thresholding any function satisfying the two-sided conditional-complexity sandwich solves the exact gap promise.
If a valid estimator's threshold language is in P, it is a deterministic
polynomial-time completion of the conditional gap promise. This isolates the
remaining algorithmic obligation in Proposition 6.2.