P and NP with atoms

Date: Thursday, November 08, 2012
Speaker: Szymon Toruńczyk
Venue: IST Austria

I will talk about notions of computation in a model of set theory extended by “atoms”. Sets with atoms where introduced in 1922 by Fraenkel in order to construct a model of a variant of the Zermelo-Frankel axioms in which the axiom of choice fails. They where rediscovered many times under various names (sets with urelements, Fraenkel-Mostowski models, nominal sets, permutation models); in automata theory they appeared in the context of register automata over data words, in a paper by Bojańczyk, Klin, Lasota from LICS’11.

I will recall the basic notions of this set theory. Afterwards, I will define several models of computation based on sets with atoms, including automata, Turing machines and imperative while-programs. Finally, I will sketch a proof that P is not equal to NP for this model of computation.More precisely, I will show a language that is in NP, but is not recognizable by any deterministic Turing machine (even with unlimited time resources). This language is related to the Cai-Fürer-Immerman construction known from finite model theory.

Posted in RiSE Seminar