HasNondetPoly
def
A Boolean function f : (Fin n → Bool) → Bool admits a non-deterministic polynomial of degree at most d if there exists a polynomial p : (Fin n → Bool) → ℝ satisfying IsNondetPolynomial f d p.
Statement
def HasNondetPoly {n : ℕ} (f : (Fin n → Bool) → Bool) (d : ℕ) : Prop
- Defined in
- arXiv:2611.11966 Def 11
- Verified
- 11 Nov 2026
- Axioms
- none listed
- Built on 1
- IsNondetPolynomialA real-valued function p on the Boolean hypercube (Fin n → Bool) is a non-deterministic polynomial for a Boolean function f of degree at…
- Used by 2
Read back from the Lean
For a natural number $n$, a Boolean function $f : (\text{Fin } n \to \text{Bool}) \to \text{Bool}$, and a degree bound $d : \mathbb{N}$, HasNondetPoly f d asserts that there exists a function $p : (\text{Fin } n \to \text{Bool}) \to \mathbb{R}$ such that:
1. $p \in \text{degreeSpace } \mathbb{R} \ (\text{Fin } n) \ d$, and
2. for all $x : \text{Fin } n \to \text{Bool}$, $p(x) \neq 0 \iff f(x) = \text{true}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Predicate asserting that f has a non-deterministic polynomial of degree at most d. -/ def HasNondetPoly {n : ℕ} (f : (Fin n → Bool) → Bool) (d : ℕ) : Prop := ∃ p : (Fin n → Bool) → ℝ, IsNondetPolynomial f d p