State-Separation and Hybrid Argument for Circuit Lower Bounds: A Structural Approach Toward P̸=NP

Read full text Summarise with VIRAT
Authors: Ryusho Nemoto
Cited by: 0
References: 8

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