{"id":"palomar/PALOMAR-2026-09-30-000006","url":"https://github.com/tomo61098/c-separated-np-complete-lean/tree/d70de3f969dd580506e0835f7d7773890b0a6eaa","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-09-30-000006-v1.json","repo":"https://github.com/tomo61098/c-separated-np-complete-lean","tags":["cs.LO","cs.CC","msc:03B35","msc:68Q17","lean","computational-complexity","feature-selection","gaussian-separation"],"score":0,"title":"NP-hardness of Gaussian c-separation","trust":"high","domain":"cs.LO","source":"palomar","authors":["Tomislav Prusina"],"reviews":0,"subject":"cs.LO","summary":"A Lean 4 proof development of reduction idea toward NP-hardness of feature selection for relative Gaussian c-separation in the formulation of Borozan et al. The argument starts from NP-completeness of equal-cardinality partition of positive squares, giving integral Gaussian data via integer roots and an even paired total. Three Gaussians enforce partition balance, and a schedule of d+1 Gaussians enforces binary selectors. Explicit separation of the two blocks makes cross-block hinge penalties vanish. The fixed threshold is (dot s 1 / 2)*d*(d+1)/2 - 3*d/4, an integer multiple of 1/4 for…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"verified":true,"discussed":0,"published":"2026-09-30","reactions":{},"formalized":true}