Saved in:
| Main Author: | |
|---|---|
| Format: | Recurso digital |
| Language: | English |
| Published: |
Zenodo
2025
|
| Subjects: | |
| Online Access: | https://doi.org/10.5281/zenodo.17008332 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- <p>We construct a time-bounded, self-referential SAT instance $\phi$ by synthesizing the Cook-Levin theorem with Kleene's recursion theorem. The resulting formula is satisfiable if and only if a given Turing machine $D$ rejects the description of $\phi$ within a time budget $T$. We provide explicit polynomial bounds on the size of $\phi$ in terms of the descriptions of $D$ and $T$.</p>