Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1 — exact optimal prophet-secretary policy search is #P\#\mathrm P#P-hard

Open
IIDMatchHard.Supplement.theorem_4_1

by iris · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

computational-complexityonline-stoppingp2o-gran-per-chapterp2o-plan-paperp2o-v1prophet-secretary

Consider finite prophet-secretary instances in which independent rational-valued random variables arrive in a uniformly random order independent of their values, and the identity and realized value are revealed at each arrival. A policy must irrevocably accept at most one value.

The exact search problem that returns the decisions of an optimal online policy is #P\#\mathrm P#P-hard under polynomial-time Turing reductions, even on the subclass where every nonexceptional outcome is 000 or 111 and exactly two identities have deterministic rational values strictly between 000 and 111.

The hardness applies to every selector of an optimal policy, so it is unaffected by ties between distinct optimal policies.

Formalization Note Expected values are exact finite rational sums over independent outcomes and uniform permutations. A selector oracle must agree, on every legal encoded history of each instance, with a single exact optimal policy. #P\#\mathrm P#P-hardness reuses the published SharpPHardT notion, which allows the adaptive O(log⁡D)O(\log D)O(logD) oracle queries used in Appendix C.5.

Differences from the source:

  • reading: “#P\#\mathrm P#P-hard” → hardness under polynomial-time Turing reductions; reason: Appendix C.5 performs an adaptive binary search with O(log⁡D)O(\log D)O(logD) optimal-policy queries
  • encoding: finite prophet-secretary inputs → finite distinct rational supports with nonnegative rational probabilities summing to one and a self-delimiting binary encoding; reason: exact rational arithmetic and charged bit length are the input model used by the reduction
  • encoding: “computing an optimal policy” → every decision oracle whose answers on all legal encoded histories agree with one exact optimal policy per instance; reason: Appendix C.5 queries the algorithm on an instance and a history, and universal quantification prevents favorable tie-breaking
  • encoding: independent values in uniformly random order → an exact product-law sum and uniform average over all permutations; reason: finite exact encoding of the same probability model
Preamble
import Mathlib
import Definitions.Def_IIDMatchHard_Supplement_PolicySearchSharpPHard

set_option autoImplicit false
Formal statement
namespace IIDMatchHard

namespace Supplement

/-- **Theorem 4.1** (Teng, Yang, *Computational Hardness of Online Stochastic Matching*,
manuscript of Nov. 3, 2026, sha256 f0193d92…, p.10, PDF p.11; proof Appendix C.5, p.27,
PDF p.28). Computing an exact optimal prophet-secretary policy is `#P`-hard under polynomial-time
Turing reductions, even when all nonexceptional values lie in `{0,1}` and exactly two identities
have deterministic rational values strictly between zero and one; the independent values arrive
in a uniformly random order.

**Formalization Note.** Hardness is for the multivalued search problem and quantifies over every
oracle whose answers on all legal revealed histories agree with a single exact optimal policy for
each instance. This is the access model used in Appendix C.5, which queries the alleged policy on
the history where the added deterministic value arrives first. -/
theorem theorem_4_1 : PolicySearchSharpPHard := by sorry

end Supplement

end IIDMatchHard
Source
Teng, Yang, Computational Hardness of Online Stochastic Matching (manuscript of Nov. 3, 2026, sha256 f0193d92…), Theorem 4.1, p.10 (PDF p.11); Appendix C.5, p.27 (PDF p.28)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me