Exact Structural Abstraction and Tractability Limits

📰 ArXiv cs.AI

arXiv:2604.07349v2 Announce Type: replace-cross Abstract: Any rigorously specified problem determines an admissible-output relation $R$, and the only state distinctions that matter are the classes $s \sim_R s' \iff \mathrm{Adm}_R(s)=\mathrm{Adm}_R(s')$. Every exact correctness claim reduces to the same quotient-recovery problem, and the no-go concerns tractability of the underlying problem, not of its presentation. Exact means agreement with $R$, not zero-error determinism or absence of approxim

Published 14 Apr 2026
Read full paper → ← Back to Reads