Weighted satisfiability for unambiguous DNFs is in P
OpenWeightedUDNF.binary_weights_satisfiability_in_polytimeboolean-functionscomplexity-theorydnf
For every valid unambiguous DNF input with positive binary-encoded variable weights and positive binary-encoded threshold, one fixed deterministic Turing machine decides whether there is a satisfying assignment of weight at least the threshold, in time polynomial in the explicit binary input-code length. This is the weighted-satisfiability baseline recorded in the cited open-problem entry; it is not the falsifiability goal.
Preamble
import Definitions.Def_WeightedUDNF import Mathlib.Computability.TuringMachine.Computable
Formal statement
namespace WeightedUDNF
theorem binary_weights_satisfiability_in_polytime :
∃ f : Input → Bool,
∃ machine : Turing.TM2ComputableInPolyTime encodeInput
Computability.encodingBoolBool.encode f,
∀ input, validInput input → f input = satisfyingDecision 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 weighted-satisfiability paragraph.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.