Unary-weight falsifiability for unambiguous DNFs is in P
OpenWeightedUDNF.unary_weights_falsifiability_in_polytimeboolean-functionscomplexity-theorydnf
For every valid unambiguous DNF input whose positive variable weights are encoded in unary and whose positive threshold remains binary-encoded, one fixed deterministic Turing machine decides whether some falsifying assignment has weight at least the threshold, in time polynomial in the explicit code length. This is the unary-weight partial result recorded in the cited source entry.
Preamble
import Definitions.Def_WeightedUDNF import Mathlib.Computability.TuringMachine.Computable
Formal statement
namespace WeightedUDNF
theorem unary_weights_falsifiability_in_polytime :
∃ f : Input → Bool,
∃ machine : Turing.TM2ComputableInPolyTime encodeInputUnaryWeights
Computability.encodingBoolBool.encode f,
∀ input, validInput input → f input = decision input := by sorry
end WeightedUDNFSource
Albertine Amarilli, “Weighted falsifiability for unambiguous DNFs,” List of open questions in theoretical computer science, section “Weighted falsifiability for unambiguous DNFs,” https://a3nm.net/work/research/questions/#weighted-falsifiability-for-unambiguous-dnfs. The entry's partial notes on unary weights.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.