Theorem 1 — Hardness with independent mean-zero error
OpenFBMSP.theorem1_hardnessThere are fixed positive integers such that the following binary-input decision problem is NP-hard under polynomial-time many-one reductions. An input specifies distinct nonnegative rational predicted values with positive rational probability masses, a common rational finite noise law of mean zero with at most listed atoms, a price budget , and a rational revenue threshold. Decide whether some assignment to nonnegative real prices reaches the threshold.
The number of segments is part of the input. Input size is the explicit self-delimiting binary description length. NP verifiers and reductions are finite Turing machines with polynomial transition bounds; an arbitrary computable reduction is insufficient.
Review note. The open reduction proof must verify probability normalization, centering of the common error, and preservation of nonnegative predicted means. The paper's unweighted revenue threshold must be rescaled consistently when customer weights sum to one.
import Definitions.Def_FBMSP_Hardness
namespace FBMSP
theorem theorem1_hardness :
∃ C d : ℕ, 0 < C ∧ 0 < d ∧
NPHard (pricingLanguageWithShockBound C d) := by sorry
end FBMSPRead-back
What the Lean code literally says, in plain math · gpt-6-astra
There exist positive natural numbers , fixed independently of the source language, such that every binary language with the following certificate property has a polynomial many-one reduction to the pricing language described below: the certificate property is existence of a total Boolean verifier and a natural-coefficient polynomial such that, for every finite Boolean string , membership of is equivalent to existence of a finite Boolean witness with and , where is polynomial-time computable on the encoding consisting of the Boolean symbols of , one distinct separator, then the Boolean symbols of , with singleton-Boolean output. A polynomial-time computation here means existence of a TM2 stack machine with finitely many stacks, control labels, and internal states, designated input and output alphabets identified with the indicated symbol types, and a polynomial with natural coefficients bounding its number of TM2 step transitions in the encoded input length. One such step executes the statement at the current control label through its next jump or halt. The required computation starts with the encoded input on the input stack, other stacks empty and the designated initial internal state, and reaches the designated halted configuration with the encoded output on the output stack, other stacks empty and that initial internal state restored. The reduction may depend on the source language; it is a total map from finite Boolean strings to finite Boolean strings, computed in that sense in time polynomial in the input bit length with identity input and output encodings, and it satisfies in the source language if and only if is in the target language, for every including the empty string. The target consists precisely of the specified encodings of valid markets meeting a revenue threshold with a supplied shock list of length at most . A valid market consists of lists of rational means and rational weights with , pairwise distinct nonnegative means, strictly positive weights, and ; lists of rational shocks and rational weights with , all , , and ; a natural number of slots ; and an arbitrary rational threshold . The two mean lists have equal lengths and the two shock lists have equal lengths. Means need not be sorted; shocks need not be distinct, shock weights may vanish, and no condition is imposed. It meets the threshold when there exist nonnegative real prices and an assignment for which . The same shock list and probabilities are used at every mean. The prices need not be rational or distinct, unused slots are allowed, and the assignment depends on the mean index but not the shock index. The encoding used is the following exact bit encoding: a bit list is encoded as one-bits, one zero-bit, then ; a natural number uses this encoding of its little-endian base-two digits, with having an empty digit list and hence encoding as one zero-bit; an integer uses a sign bit, true exactly when it is negative, followed by the natural encoding of its absolute value; a rational uses the integer encoding of its canonical numerator followed by the natural encoding of its positive denominator; and a list uses the natural encoding of its length followed by the encodings of its elements. A market encoding concatenates, in order, the encoded mean list, mean-weight list, shock list, shock-weight list, number of price slots, and rational threshold. The shock bound counts all supplied entries, including repetitions and zero-weight entries; is the number of distinct supplied means. The number of slots is part of each encoded input and has no upper bound or fixed-value restriction. Strings not equal to the encoding of such a valid threshold-meeting market are outside the target language. Nonpositive thresholds are permitted and are met by zero prices whenever the other membership conditions hold. The assertion is hardness under these reductions and does not additionally assert membership of the target language in NP.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.