Positive 1-in-3-SAT → Normalized planar ReLU training with an error gap Complexity open
Solution submitted Research history & proof on GitHub ↗
Why this question matters
This targets exact training complexity in two input dimensions under normalization, closer to a basic learning model than unrestricted constructions.
Hardness with unrestricted dimension or scaling does not establish the stated two-dimensional, normalized, positive-error-gap theorem.
The reduction to construct
A source instance has clauses of three unnegated variables. A valid assignment makes exactly one variable true in each clause; an infeasible instance returns NO-SOLUTION.
The target has rational two-dimensional data in [-1,1], a hidden-unit budget, signed output weights in {−1,+1}, and a rational squared-error threshold 0<τ≤1. The theorem must separate satisfiable from unsatisfiable sources by the stated error gap and give finite encoded accepted parameters.
Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is NP-hardness for the stated target problem.
The soundness proof must control all real networks and justify finite witness recovery; an intended network alone is insufficient.
What a complete answer must include
Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.
References
Literature checked 2026-09-15. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.