J.A. Makowsky (Haifa, Israel) and K. Meer (Cottbus, Germany)
The ESSLLI-2014 Lectures:
P versus NP over arbitrary structures
Lectures
to be held in Tuebingen, Germany, 11-15 August, 2014
at the occasion of
ESSLLI-2014
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:
janos@cs.technion.ac.il
and
Klaus Meer:
meer@Informatik.tu-Cottbus.de
respectively.
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
acroread 9.5.
-
Title and overview Overview
-
Lecture 1: (J.A. Makowsky)
-
Introduction INTRO
-
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.
Adding FORTRAN-libraries.
FORTRAN
-
Comparing Poizat's Theorem with descriptive complexity. FAGIN
-
Lecture 4: (K. Meer)
Inside NP and analogues of Ladner's Theorem
Meer-1
-
Lecture 5: (K. Meer)
The PCP Theorem over the reals
Meer-2
Lectures 1-5 were delivered at ESSLLI-2014.
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.
BOOLEAN
-
P is different from NP for the ring of real (n x n)-matrices.
MATRICES