Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
Baruch Garcia · 2026
Read Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem by Baruch Garcia (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-09702.txt.
Introduction
Baruch Garcia takes a fresh look at a landmark result about the limits of proof methods. The 2026 arXiv paper revisits the Baker-Gill-Solovay theorem on relativization in complexity theory. Some separations, like P versus EXP, survive when all machines gain an oracle; others, famously, cannot be settled that way.
Garcia asks a specific point that he says was never proven outright: whether the Turing-recognizability of the acceptance problem relativizes. Diagonalization is the classic tool behind such results. Clarifying exactly what it can and cannot do keeps the foundations of complexity theory honest.
Catalog record
| CREATOR | Baruch Garcia |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-09702
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem Baruch Garcia 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; R A = R E A R^{A}=RE^{A} , 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. 1 Prologue La verdad adelgaza y no quiebra ... 1 1 1 ”The truth may be stretched thin, but does not break[…]” - Don Quixote de La Mancha, Miguel de Cervantes To clearly understand the foundations of computational complexity, we will examine the foundations of computability as discussed by Stephen Cook in the early 1970’s 11 : My advisor as a graduate student, Hao Wang at Harvard, was interested in logic and recursion theory and what led me to this idea was exactly the theory of computable functions, which had the so-called recursively enumerable sets and so the same phenomenon was there. You had recursively enumerable complete sets and they were all equivalent to the hardest recursively enumerable sets, and of course the difference was these sets were not decidable, there was no algorithm to solve them at all, but that was the analogy. It’s different of course for NP-complete sets. They were computable, but not feasibly computable[….]It presumably takes exponential amount of time to solve the problems, but the analogy is there. That’s where I got the idea. Wigderson 38 further explains the analog: A very appealing feature of the P versus NP question (which was a source of early optimism about its possible quick resolution) is that it can be naturally viewed as a bounded analog of the decidability question from computability theory[….] To see this, replace the polynomial-time bound by a finite bound in both classes. For P , the analog becomes all problmes having finite algorithms, namely the decidable problems sometimes called Recursive problems and denoted by R . For NP , the analog is the class of properties for which membership can be certified by a finite witness via a finite algorithm. This class is called Recursively Enumerable , or RE . We will talk of finite verification or equivalently recursively enumerability or computable enumerability or semi-decidability or Turing-recognizability . Take the halting problem, for example; although there is no generalized algorithm for the halting problem, if it does halt, it can be verified in finite time t . We will refer to this class as: RE . Its polynomial analog is always referred to as ”non-deterministic polynomial time” or: NP We will also use the terms finite co-verification equivalently to co-recursive enumerability or co-computable enumerability or co-semi-decidability or co-Turing-recognizability . Take the complement of the halting problem, for example; although there is no generalized algorithm for the complement of the halting problem (”does the Turing machine never halt?”), its complement is verifiable, i.e. if it halts, it can be verified in finite time t . We will refer to this class as: co-\textbf{RE} Its polynomial analog of the complement is: co-\textbf{NP} We will also talk of recursion or equivalently decidability or equivalently computability or algorithmic . We will refer to this class as: R Problems outside this class are said to be non-recursive or undecidable or uncomputable 2 2 2 ”Decidable” may refer to a two-valued decision and ”computable” or ”solvable” may refer to a multi-valued solution, which can be made of several binary ”decisions”. or may be said to have no generalized algorithm . Its polynomial analog is referred to as ”polynomial time” or P This class includes all problems for which there is a generalized algorithm to decide (or solve) in a feasible , i.e., polynomial, amount of time. In this paper, we will rely heavily on notation used in Sipser’s Introduction to the Theory of Computation (3rd edition), differing notably in our use of RE for ”Turing-recognizability” and R for ”decidability”. 2 Background Gödel’s letter to von Neumann 15 3 3 3 John Nash discovered a partial version of the problem involving the infeasibility of \textbf{NP}-intermediate problems 4 . established a problem later recognized as the ” P versus NP ” problem. Can a the class of problems that can be verified in polynomial, i.e. ”feasible”, time, also be solved (decided) in polynomial time? Reviews of the problem can be found by Sipser 31 , Cook 10 and Aaronson 4 . Textbooks by Sipser 32 , Wigderson 38 , Arora and Barak 7 , and Aaronson 3 also shed light on the problem. It is important to note that if \textbf{P}\neq\textbf{NP} , Ladner’s theorem 21 tells us there will be an intermediate class, i.e., \textbf{NP}-intermediate which must exist. While it is conceivable that natural problems like graph isomorphism, integer factorization, and discrete logarithm, may change 4 4 4 …as the problem of primality changed from an \textbf{NP}-intermediate problem to problem in P , with the algorithm of Agrawal, Kayal, and Saxena 6 into either P or \textbf{NP}-complete , the \textbf{NP}-intermediate class would exist in perpetuity, as we see with the \textbf{RE}-intermediate class, which contains no natural problems 26 20 13 23 3 . If \textbf{P}\neq\textbf{NP} , then the problems which will always be undecidable in feasible time are called ” \textbf{NP}-complete ”. 3-CNF-SAT —otherwise known as 3SAT or SAT for short---is a canonical problem 5 5 5 An example of of an \textbf{NP}-complete problem is 3-CNF-SAT which asks whether the following statement is satisfiable: (x_{1}\vee\neg x_{2}\vee x_{3})\wedge(\neg x_{1}\vee x_{3}\vee\neg x_{4})\wedge(x_{2}\vee\neg x_{3}\vee x_{4}) from which we provide polynomial-time reductions to prove that other well-known problems, like CLIQUE and SUDOKU , are also \textbf{NP}-complete . However, if P were to equal NP , then P , \textbf{NP}-intermediate and \textbf{NP}-complete problems would collapse to one class. The inequivalence of P and NP seems so obvious for many reasons. For example, there are a multitude of \textbf{NP}-intermediate problems, yet not a single one has been found to have a polynomial-time decision algorithm. A second reason is that, although there are quantum polynomial-time ( BQP ) algorithms for