About the work
The P vs NP conjecture remains one of the most profound open problems in computer science, with traditional barriers like relativization, natural proofs, and algebrization challenging progress. We introduce a novel treewidth-based framework leveraging Separator Information Lower Bounds (SILB) to derive robust time–space tradeoffs and approach this conjecture. By encoding problems into CNF formulas with incidence graphs of treewidth $\tw(G_I)$, we define a coherence parameter $\C(G_I) = 1/(1 + \tw(G_I))$ and use internal information complexity ($\IC$) to establish structural lower bounds. Our framework proves soundness for P subclasses with $\tw(G_I) = O(\log n)$, completeness for tractable instances, and structural bounds for UNSAT via incidence graphs. We derive explicit SILB bounds for RAM, Turing machines, and cell–probe models, supported by $\ETH$/$\SETH$-conditional separations. Key milestones include a No–Bypass property via $\IC$, sparse SDP–$\IC$ for $\DISJ_k \circ g$, and bounded–round/cell–probe strengthening, with empirical validation through treewidth estimation and rank diagnostics. The sole conjectural ingredient is a strong direct-product for $\IC$ in bounded rounds (target Theorem 3). Our approach is non-relativizing, non-natural, and distribution-specific, offering a promising path toward separating P from NP. Experimental results with the $\IC$-SAT solver demonstrate up to 40% fewer branches compared to Minisat22, underscoring practical implications.
José Manuel Mota Burruezo
Shown in
AI Availability Declaration
The work is allowed to be accessed by AI systems.
Print work information
Work information
Title Treewidth and Information Complexity: A New Framework for P vs NP Lower Bounds
The P vs NP conjecture remains one of the most profound open problems in computer science, with traditional barriers like relativization, natural proofs, and algebrization challenging progress. We introduce a novel treewidth-based framework leveraging Separator Information Lower Bounds (SILB) to derive robust time–space tradeoffs and approach this conjecture. By encoding problems into CNF formulas with incidence graphs of treewidth $\tw(G_I)$, we define a coherence parameter $\C(G_I) = 1/(1 + \tw(G_I))$ and use internal information complexity ($\IC$) to establish structural lower bounds. Our framework proves soundness for P subclasses with $\tw(G_I) = O(\log n)$, completeness for tractable instances, and structural bounds for UNSAT via incidence graphs. We derive explicit SILB bounds for RAM, Turing machines, and cell–probe models, supported by $\ETH$/$\SETH$-conditional separations. Key milestones include a No–Bypass property via $\IC$, sparse SDP–$\IC$ for $\DISJ_k \circ g$, and bounded–round/cell–probe strengthening, with empirical validation through treewidth estimation and rank diagnostics. The sole conjectural ingredient is a strong direct-product for $\IC$ in bounded rounds (target Theorem 3). Our approach is non-relativizing, non-natural, and distribution-specific, offering a promising path toward separating P from NP. Experimental results with the $\IC$-SAT solver demonstrate up to 40% fewer branches compared to Minisat22, underscoring practical implications.
José Manuel Mota Burruezo
Work type Education, Informative
Tags p vs np lower bounds
-------------------------
Registry info in Safe Creative
Identifier 2509012949584
Entry date Sep 1, 2025, 10:07 AM UTC
License All rights reserved
-------------------------
Copyright registered declarations
Author 100.00 %. Holder JOSE MANUEL MOTA BURRUEZO. Date Sep 1, 2025.
Information available at https://www.safecreative.org/work/2509012949584-treewidth-and-information-complexity-a-new-framework-for-p-vs-np-lower-bounds
/
Registration: 2509012949584
