Set Theory in the Foundation of Math: Internal Classes, External Sets

TBA

Logic in the Age of AI: What can it be? What should it be? What will it be?

TBA

Relativization and Complexity

Relativization is a technique which saw its birth in set theory and

in computability theory, notably in Turing’s 1939 paper where Turing

defined what it meant for a set X to be A-computable. Classically, the

collection of A-computable sets are defined to be {B | B ≤T A}.

Relativization in computability theory is a longstanding love-affair,

notably allowing for effortless proofs of results about the jump operator

from results about the halting problem for example. These effortless results

also generated a number of false conjectures such as the homogenity

conjecture.

Computational complexity theory has a more turbulent relationship

with relativization. This is particularly since the classical results of Baker-

Gill-Solovay saying that there are oracles A and B such that PA ̸= NPA

and PB = NPB. Their conclusion is that methods that relativize are not

sufficient to settle the P =?NP question. The Baker-Gill-Solovay results

spawned a huge cottage industry of results showing similar separation

methods could not be settled by methods that relativized. This caused

computational complexity to think about methods such as arithmetization,

algebraization, etc.

In this talk, I will analyse relativization in complexity theory and argue

that it is wrongly applied; arguing that the current techniques are only

concerned with partial relativization. This argument resurrects the hope

that there might be some method of using oracles to settle questions such

as the P =?NP one.

TBA

TBA