J.A. Makowsky
The ISLA-2014 Lectures:
P = NP over arbitrary structures
Held in Tezpur, India, 6-17 January, 2014
Posted 06.08.2014 , original slides are disabled.
NEW:
An updated version of this course may be found at
ESSLLI-2014
Please send comments to
janos@cs.technion.ac.il
The links in 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.
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 FORTRAN-libraries.
-
Lecture 5: ACF0
Quantifier elimination in algebraically closed Fields.
-
Lecture 6: FAGIN
Comparing Poizat's Theorem with descriptive complexity.
Lectures 1-6 were delivered at ISLA-2014.
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)
