Locality, Consistency, and the Tractability Frontier
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910262795173888 |
|---|---|
| author | Simas, Tristan |
| author_facet | Simas, Tristan |
| contents | Rice's theorem shows that nontrivial extensional properties of partial recursive functions are undecidable. For finite weighted Boolean optimization/CSP-style slices, a Rice-style structural analogue holds for tractability classification: correctness forces invariance under theorem-forced presentation moves, and orbit gaps are exactly the obstruction to exact classification by closure-invariant predicates.
The scope is universal for exact specifications. Any rigorously specified problem determines an admissible-output relation, and exact certification depends only on the induced equivalence relation $s \sim_R s' \iff \operatorname{Adm}_R(s)=\operatorname{Adm}_R(s')$. Decision, search, approximation, randomized-output, statistical, and distributional guarantees all enter through this admissible-output quotient.
On closure-closed domains with polynomial-time-computable transports, every correct tractability classifier must be constant on closure orbits. Exact closure-invariant classification is possible exactly when positive and negative orbit hulls are disjoint; in that case the closure hull is a closure operator giving the least exact classifier. The finite structural regime is a basic-local first-order fragment over extracted pairwise syntax. Four binary-pairwise obstruction families--dominant-pair concentration, margin masking, ghost-action support, and action-specific offsets--witness same-orbit disagreement for natural finite structural predicates, while the hull-separation theorem gives the positive criterion when classification is possible. Without explicit margin control, arbitrarily small utility perturbations can flip relevance and sufficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_07349 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Locality, Consistency, and the Tractability Frontier Simas, Tristan Computational Complexity Artificial Intelligence Logic in Computer Science 90C31, 68Q15, 03D20, 68T20 F.2.2; F.4.1; I.2.4 Rice's theorem shows that nontrivial extensional properties of partial recursive functions are undecidable. For finite weighted Boolean optimization/CSP-style slices, a Rice-style structural analogue holds for tractability classification: correctness forces invariance under theorem-forced presentation moves, and orbit gaps are exactly the obstruction to exact classification by closure-invariant predicates. The scope is universal for exact specifications. Any rigorously specified problem determines an admissible-output relation, and exact certification depends only on the induced equivalence relation $s \sim_R s' \iff \operatorname{Adm}_R(s)=\operatorname{Adm}_R(s')$. Decision, search, approximation, randomized-output, statistical, and distributional guarantees all enter through this admissible-output quotient. On closure-closed domains with polynomial-time-computable transports, every correct tractability classifier must be constant on closure orbits. Exact closure-invariant classification is possible exactly when positive and negative orbit hulls are disjoint; in that case the closure hull is a closure operator giving the least exact classifier. The finite structural regime is a basic-local first-order fragment over extracted pairwise syntax. Four binary-pairwise obstruction families--dominant-pair concentration, margin masking, ghost-action support, and action-specific offsets--witness same-orbit disagreement for natural finite structural predicates, while the hull-separation theorem gives the positive criterion when classification is possible. Without explicit margin control, arbitrarily small utility perturbations can flip relevance and sufficiency. |
| title | Locality, Consistency, and the Tractability Frontier |
| topic | Computational Complexity Artificial Intelligence Logic in Computer Science 90C31, 68Q15, 03D20, 68T20 F.2.2; F.4.1; I.2.4 |
| url | https://arxiv.org/abs/2604.07349 |