The input decider accepts a padded instance encoding iff its length and scale fit
ProvedOPI.Parse.decideI_specAn instance of the code-intersection problem consists of a field presentation ( and the defining polynomial , so ), the length , an matrix with a flag (generator or parity-check matrix), the forbidden values , and a precision . It is encoded as a bit string , and its scale is .
For a bound , the decider receives the length- string
i.e. the encoding padded with zeros (or truncated) to exactly bits. The decider decideI parses with all numbers saturated at , and outputs where says that the parse succeeded and the parsed scale, with computed as , is at most .
Statement. For every instance and every ,
This is the decider half of the polynomial-time uniformity of the algorithm. Together with the polynomial realizer decideI_pr it certifies, from the padded prefix alone, whether the instance is complete and small enough for the program generated at size .
import Definitions.Def_TwoFoldOPI_CL_Part05
import Definitions.Def_TwoFoldOPI_Input
import Mathlib
import Definitions.Def_QAlgorithms_Defs_Circuit
import Definitions.Def_QAlgorithms_Defs_GradientMethods
import Definitions.Def_QAlgorithms_Defs_OPIOraclePrograms
import Definitions.Def_QAlgorithms_Defs_OPIUniformity
import Definitions.Def_QAlgorithms_Defs_Fourier
import Definitions.Def_TwoFoldOPI_elemBits
import Definitions.Def_TwoFoldOPI_schurSquare
import Definitions.Def_TwoFoldOPI_schurFailureSum
import Definitions.Def_CodingTheory
import Definitions.Def_OAIThreeMachineSched01
import Definitions.Def_CookLevin_Cost
import Definitions.Def_TwoFoldOPI_codeOf
import Definitions.Def_TwoFoldOPI_solves
import Definitions.Def_TwoFoldOPI_CLSerializableF
open OPI.Parse
open OPI OPI.W6 OPI.W6.IsPR OAI.ThreeMachine.StackCompiler
variable {α : Type} [Coding α]
open TwoFoldOPI QAlgorithms.LocalHamiltonian
theorem OPI.Parse.decideI_spec (x : Input) (s : ℕ) :
decideI ((x.encode ++ List.replicate s false).take s) =
[decide (x.encode.length ≤ s ∧ x.scale ≤ s)] := by sorry