Dinámica estructural de la resolubilidad polinómica: espacios de estados estratificados y navegabilidad polinómica

Esta nota introduce un punto de vista estructural y geométrico sobre la resolubilidad en tiempo polinómico basado en la dinámica de los espacios de estados computacionales. En lugar de tratar \(\mathrm{P}\) y \(\mathrm{NP}\) principalmente a través de la oposición entre búsqueda y verificación, nos centramos en la evolución, la compresión y la navegabilidad de los espacios de estados estratificados que surgen durante el cómputo.

El artículo es de carácter exploratorio y está concebido como un paso introductorio hacia un enfoque estructural más amplio de la teoría de la complejidad. Su propósito no es proponer una base alternativa acabada de la teoría de la complejidad, sino desarrollar un vocabulario preliminar para discutir mecanismos de colapso estructural global en el cómputo.

Un formalismo computacional se representa como una terna \(F=(M,R,D)\) que consiste en una clase de modelos computacionales, una escala de recursos y una clase de descripciones admisibles. Esta distinción se utiliza para separar estructuras genuinamente realizables en tiempo polinómico de representaciones cuya aparente eficiencia depende de operaciones primitivas más fuertes o de supuestos alternativos sobre recursos.

La noción técnica central es la de una realización estructural de un lenguaje mediante un sistema de estados con divergencia, frontera acotada y completación. Mostramos que todo lenguaje que admite tal realización pertenece a \(\mathrm{P}\). El marco se ilustra en Horn-SAT, \(2\) -SAT, emparejamiento bipartito y \(3\) -SAT, enfatizando diferentes formas de colapso estructural y diferentes obstáculos a la navegabilidad polinómica.

La interpretación resultante es que la resolubilidad polinómica no es meramente la ausencia de búsqueda, sino la existencia de mecanismos globales que impiden la expansión descontrolada de la frontera computacional activa. Los conceptos introducidos aquí están destinados principalmente como herramientas organizativas y programáticas para desarrollos futuros, más que como una teoría estructural acabada.

Palabras clave: complejidad computacional; resolubilidad polinómica; espacios de estados estratificados; navegabilidad polinómica; realizaciones estructurales; colapso estructural; dinámica del espacio de estados; complejidad de pruebas; SAT; formalismos computacionales; compresión admisible; simulación robusta; dinámica estratificada; crecimiento de la frontera; estructura global