In spite of much work over the years, the main questions in complexity
theory such as P vs. NP remain unresolved. Is this question solvable at
all? Is P vs. NP independent of some logical theory? Indeed, on a
metalevel, there are several results that state that certain classes of
techniques, including Turing's celebrated diagonalization, cannot be used to
resolve these questions.
Such results we call the "barriers" of complexity theory.
In this talk, we will survey some of the main such barriers (Relativization,
Natural Proofs, Algebrization), and talk about how knowledge of such
barriers helps evaluate (and, so far, discard) proposed proofs of P vs. NP.
We will talk about the logic basis for such barriers, where a barrier means
an independence of a logic theory.
