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 }