AFTD Auto-Formalizing Theoretical Domains

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
  • ndegThe non-deterministic degree ndeg f of a Boolean function f : (Fin n → Bool) → Bool is the minimal natural number d such that f admits a…
  • ndeg_le_nFor any natural number n and any Boolean function f : (Fin n → Bool) → Bool, the non-deterministic degree of f is at most n.

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
See it in the graphDiscuss this resultChallenge it