State-Separation and Hybrid Argument for Circuit Lower Bounds: A Structural Approach Toward P̸=NP
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
The P versus NP problem is a central open question in theoretical computer science, and proving that SAT cannot be solved by polynomial-size circuits is one of its key challenges. In this paper, we introduce a structural framework that rigorously analyzes the complexity of self-reducible SAT instances through a combination of state-separation and hybrid arguments. We define a high-information witness selection function (Sel) based on Inner Product con- structions, where each input bit independently contributes to the output. By constructing a sequence of hybrid inputs that gradually transition between distinct prefixes, we track the accumulation of independent information that any circuit must preserve. This demonstrates a fundamental limitation: any polynomial-size circuit attempting to compute Sel must maintain an exponentially large number of internal states. We embed Sel into CNF form using standard Tseitin transformations, linking the hybrid argument directly to SAT instances. As a result, poly-size circuits cannot correctly compute these SAT instances, establishing an exponential lower bound on the number of circuit states required. This provides a concrete structural pathway demonstrating that SAT / ∈P/poly and hence that P ̸= NP, while clearly delineating the remaining formalization challenges for general non-uniform circuits.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Computability
Logic
AI Algorithms
Publication details
- Journal / source
- PhilPapers (PhilPapers Foundation)
- Publication date
- 25 March 2026
- Language
- EN