{
  "annotation_id": "20bea880-d0c8-4a9d-8886-1cdd34d8f5f9",
  "date_created": "2026-02-17T05:53:20.175000Z",
  "date_modified": "2026-02-17T05:53:20.175000Z",
  "file_hash": "8db92914a4b12df04f34adfd5dd280814b81d46c38524b918c4b4c359cd990bf",
  "private": false,
  "record": {
    "abstract": "We already know that several problems like the inequivalence of P and EXP as well as the undecidability of the acceptance problem and halting problem relativize. However, relativization is a limited tool which cannot separate other complexity classes. What has not been proven explicitly is whether the Turing-recognizability of the acceptance problem relativizes. We will consider an oracle for which R and RE are equivalent; RA = REA, where A is an oracle for the equivalence problem in the class ALL, but not in RE nor co-RE. We will then differentiate between relativization and what we will call \"semi-relativization\", i.e., separating classes using only the acceptance problem oracle. We argue the separation of R and RE is a fact that only \"semi-relativization\" proves. We will then \"scale down\" to the polynomial analog of R and RE, to evade the Baker-Gill-Solovay barrier using \"semi-relativized\" diagonalization, noting this subtle distinction between diagonalization and relativization. This \"polynomial acceptance problem\" is then reducible to CIRCUIT-SAT and 3-CNF-SAT proving that these problems are undecidable in polynomial time yet verifiable in polynomial time. \"Semi-relativization\" does not employ arithmetization to evade the relativization barrier, and so itself evades the algebrization barrier of Aaronson and Wigderson. Finally, since semi-relativization is a non-constructive technique, the natural proofs barrier of Razborov and Rudich is evaded. Thus the separation of R and RE as well as P and NP both do not relativize but do \"semi-relativize\", evading all three barriers.",
    "arxiv_id": "2601.09702",
    "authors": [
      "Baruch Garcia"
    ],
    "categories": [
      "cs.CC"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "title": "Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem",
    "url": "https://arxiv.org/abs/2601.09702",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "c27dbf16-1913-42cc-b123-be1fda7ecf5f",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}