J.A. Makowsky (Haifa, Israel) and K. Meer (Cottbus, Germany)
The ESSLLI2014 Lectures:
P versus NP over arbitrary structures
Lectures
to be held in Tuebingen, Germany, 1115 August, 2014
at the occasion of
ESSLLI2014
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.tuCottbus.de
respectively.
The links inside the pdffiles may not function if you open the files in a separate window.
They do function if you open the pdffiles 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 FORTRANlibraries.
FORTRAN

Comparing Poizat's Theorem with descriptive complexity. FAGIN

Lecture 4: (K. Meer)
Inside NP and analogues of Ladner's Theorem
Meer1

Lecture 5: (K. Meer)
The PCP Theorem over the reals
Meer2
Lectures 15 were delivered at ESSLLI2014.
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