relu_width3_unit_interval_zero_language
The verification language at width 3 on the unit interval, for the fixed encoding relu_network3_encode: the set of Bool words w such that w = relu_network3_encode net for some width-3 feedforward ReLU network net with rational weights and biases (ReLUNetwork 3) that has a zero in [0, 1] (relu_network_has_unit_interval_zero net).
Statement
def relu_width3_unit_interval_zero_language : Language Bool- Defined in
- arXiv:2610.06092 (Fractal Gadgets for Neural Networks: The Complexity of the Narrow Regime), Section 2.1 (network representation: rational entries as pairs of integers written in binary) and Remark 5.15. The bit-level layout is a choice made here; the paper fixes only binary numerators and denominators.
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Built on 3
- relu_network3_encodeEncoding of a width-3 ReLU network as a Bool word, of length linear in the total bit length of its rational entries: input weights, input…
- relu_network_has_unit_interval_zeroA feedforward ReLU neural network
netof width $k$ has a zero in the unit interval $[0, 1]$ if there exists some real number… - ReLUNetworkA feedforward ReLU neural network from the real line to the real line with hidden layers of width k, specified by rational affine input…
- Used by 7
- op75_subset_reduction_hardIf the canonical subset-sum source language is NP-hard and reduces in polynomial time to the width-three zero language, then the…
- op75_invalid_input_fallback_nonmemberThe encoding of the empty-weight target-one network is a no-instance of the width-three unit-interval zero language.
- op75_subset_compiler_correct_reductionA total polynomial-time Boolean compiler with the specified canonical output and a no-instance output on malformed words gives the desired…
- op75_subset_compiler_semanticsAny total binary function that maps canonical subset-sum instances to their specified networks and maps malformed inputs outside the zero…
- op75_subset_compiler_function_correctThe explicit total compiler preserves language membership.
- relu_width3_language_mem_iffSanity check of the language: the encoding of a width-3 ReLU network lies in the verification language exactly when the network has a zero…
- op75_subset_compiler_machine_sufficesIf the explicit compiler is polynomial-time TM2 computable, the claimed subset-sum to network Karp reduction follows.
Read back from the Lean
The definition relu_width3_unit_interval_zero_language defines the formal language over the boolean alphabet Bool (i.e., a set of lists of booleans List Bool) consisting of all words w such that there exists a ReLU neural network of width 3 with rational parameters (net : ReLUNetwork 3) satisfying:
1. The binary encoding of net under relu_network3_encode is equal to w, and
2. net has a zero in the closed unit interval $[0, 1]$ (i.e., there exists $x \in [0, 1] \subseteq \mathbb{R}$ such that evalNetwork net x = 0).
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
def relu_width3_unit_interval_zero_language : Language Bool :=
{w | ∃ net : ReLUNetwork 3, relu_network3_encode net = w ∧
relu_network_has_unit_interval_zero net}