Theorem 5.1 — SearchNP for a fixed Avoid family implies promise NP
OpenAMRangeAvoid.Characterization.Supplement.theorem_5_1complexity-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1range-avoidance
Fix a promise problem , a verifier witnessing , and a particular deterministic polynomial-time targeted-hitting reduction . The circuit expands by one bit on every input, and has the verifier's challenge length on every input. If every input has an accepting nondeterministic polynomial-time branch producing a non-image of , and every accepting branch produces such a non-image, then
The hypothesis is specific to . Its totality includes YES and unpromised inputs; it does not assume a solver for arbitrary expanding circuits.
Differences from the source:
- encoding: a nondeterministic polynomial-time machine with totality and universal correctness of accepting paths → polynomial-length branch certificates, operational polynomial-time acceptance and output transducers, totality for every x, and correctness for every accepted certificate; reason: polynomially clocked nondeterministic paths and such certificates describe the same SearchNP class
Preamble
import Definitions.Def_AMRangeAvoid_Characterization_Supplement_Complexity import Definitions.Def_AMRangeAvoid_Characterization_SSLB
Formal statement
namespace AMRangeAvoid.Characterization.Supplement
theorem theorem_5_1 (A : PromiseProblem) (V : AMVerifier)
(hV : WitnessesAM A V) (f : Bits → Bits) (g : Bits → Bits → Bits)
(hfg : IsAvoidReduction (TargetedHitting A V) f g)
(hSearch : InSearchNP (AvoidFamily f)) : InPrNP A := by sorry
end AMRangeAvoid.Characterization.Supplement
Source
Zeyong Li, STOC 2027 submission #502 (October 2026), Theorem 5.1, printed p.24 (PDF p.26); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/502.pdf