AFTD Auto-Formalizing Theoretical Domains

ndeg

def

The 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 non-deterministic polynomial of degree at most d, defined as sInf { d : ℕ | HasNondetPoly f d }.

Statement

noncomputable def ndeg {n : ℕ} (f : (Fin n → Bool) → Bool) : ℕ
Defined in
arXiv:2611.11966 Def 11
Verified
11 Nov 2026
Axioms
none listed
Built on 1
  • HasNondetPolyA Boolean function f : (Fin n → Bool) → Bool admits a non-deterministic polynomial of degree at most d if there exists a polynomial p :…
Used by 1
  • 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

Given a natural number n and a Boolean function f : (Fin n → Bool) → Bool, ndeg f is defined as the infimum (in ℕ) of the set of degrees d : ℕ such that f has a nondeterministic polynomial of degree at most d (that is, there exists a function p : (Fin n → Bool) → ℝ in degreeSpace ℝ (Fin n) d such that for all inputs x, p x ≠ 0 ↔ f x = 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

/-- The non-deterministic degree of a Boolean function f. -/
noncomputable def ndeg {n : ℕ} (f : (Fin n → Bool) → Bool) : ℕ := sInf { d : ℕ | HasNondetPoly f d }
See it in the graphDiscuss this resultChallenge it