J.A. Makowsky
The ISLA2014 Lectures:
P = NP over arbitrary structures
Held in Tezpur, India, 617 January, 2014
Posted 06.08.2014 , original slides are disabled.
NEW:
An updated version of this course may be found at
ESSLLI2014
Please send comments to
janos@cs.technion.ac.il
The links in 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.
GANESHA is the god of problem solving and trickery,
hence also of Logic and Mathematics,
see
Ganesha and
consorts SIDDHI and BUDDHI.

Here are two pictures of my own Ganesha
This is a SHAKTI GANAPATI version, one of the 32 forms of GANAPATI, see the
Sritattvanidhi,
"The Illustrious Treasure of Realities".
(height 34cm with podest, 25cm without, ivory carving, origin unknow)
Click the pictures to get big versions
Comments about its origin and time are sollicited. Thanks.

Lecture 1: Overview
Title and overview

Lecture 1a: INTRO
Introduction

Lecture 1b: NEWBSS
Turing machines over relational structures

Lecture 1c: SHORTQE
Short quantifier elimination.

Lecture 2: QE
Introduction to quantifier elimination.

Lecture 3: TABLE
Fields, rings and other structures.

Lecture 4: FORTRAN
Computing with the reals: Removing order or multiplication.
Adding FORTRANlibraries.

Lecture 5: ACF0
Quantifier elimination in algebraically closed Fields.

Lecture 6: FAGIN
Comparing Poizat's Theorem with descriptive complexity.
Lectures 16 were delivered at ISLA2014.
Here are some more lectures (to be extended):

Lecture 7: ABELIAN
P is different from NP for all infinite abelian groups.
(after M. Prunescu)

Lecture 8: BOOLEAN (posted on 30.01.2014)
P is different from NP for all infinite boolean algebras.
(after M. Prunescu)

Lecture 9: MATRICES (to be posted)
P is different from NP for the ring of real (n x n)matrices.
(after A. Rybalov)