J.A. Makowsky (Haifa, Israel) and K. Meer (Cottbus, Germany)
The ESSLLI-2014 Lectures:
P versus NP over arbitrary structures
to be held in Tuebingen, Germany, 11-15 August, 2014
at the occasion of
Posted 05.08.2014, revised 15.08.2014
In the actual course given, Lecture 2 consisted only of Part QE.
Lecture 3 contained TABLE, FORTRAN and FAGIN.
Please send comments to
Johann A. Makowsky:
The links inside the pdf-files may not function if you open the files in a separate window.
They do function if you open the pdf-files of the lectures within your browser using
Lectures 1-5 were delivered at ESSLLI-2014.
Title and overview Overview
Lecture 1: (J.A. Makowsky)
Turing machines over relational structures NEWBSS
Short quantifier elimination. SHORTQE
Lecture 2: (J.A. Makowsky)
Introduction to quantifier elimination. QE
Fields, rings and other structures. TABLE
Lecture 3: (J.A. Makowsky)
Computing with the reals: Removing order or multiplication.
Comparing Poizat's Theorem with descriptive complexity. FAGIN
Lecture 4: (K. Meer)
Inside NP and analogues of Ladner's Theorem
Lecture 5: (K. Meer)
The PCP Theorem over the reals
Here are some more lectures (from JAM's regular course at the Technion)
Quantifier elimination in algebraically closed Fields. ACF0
P is different from NP for all infinite abelian groups. ABELIAN
P is different from NP for all infinite boolean algebras.
P is different from NP for the ring of real (n x n)-matrices.