Paper 2024/2035

A Note on P $\neq$ NP

Abstract

We study the Add/XNOR decision problem: given $n$ words of $n$ bits each, choose between addition modulo $2^n$ and bitwise XNOR at each position of a left-associative expression so that its final value is zero. We prove NP-completeness by a deterministic polynomial-time reduction from binary SUBSET-SUM. Independent four-bit guard fields force each successful four-operation gadget to consist entirely of additions or entirely of XNORs. Normalization by XNOR parity prevents later gadgets from repairing a failed guard, while control bits and zero padding enforce the target and the equality of operand count and word width. The reduction also yields a $2^{o(n)}$-time exclusion under the Exponential Time Hypothesis and NP-completeness when the word width is a fixed positive rational power of the operand count. An exact meet-in-the-middle algorithm uses $O^*(2^{(n-1)/2})$ time and space, where $O^*$ suppresses polynomial factors in $n$. We also quantify the reduction's solution multiplicity and the output marginals for independently uniform operands. The optimal exponential rate and average-case complexity remain questions for further work.