Mihai Prunescu, A model-theoretic proof for P $\neq$ NP
over all infinite abelian groups, The Journal of Symbolic Logic,
Vol. 67, Number 1, 235-238. (I can give you paper copies if you are
interested).
Mihai Prunescu, P $\neq$ NP for all infinite Boolean algebras,
Mathematical Logic Quarterly, Vol. 49, Number 2, 210-213.
(I can give you paper copies.)
This year the course is given mainly as a "reading course" with only five scheduled lectures during January to May.
Below I briefly explain what I will talk about in the
next lecture.
12/5: The class DP, polynomial machines using an oracle,
and the polynomial hierarchy; chap. 17. Notes from the 5th lecture.
20/4: More about P and NP, computation with oracles and
results about P=?NP relative to oracles, computation over
structures and results about P=?NP over structures; chap. 14;
see also the articles above.
Notes from the 4th lecture.
17/2: The reachability method and theorems in chap. 7.3;
reductions and completeness including Cook's theorem, chap. 8.
You should also read about the "art of" proving that various
problems are NP-complete,
chap. 9, and about the relationship between NP and
second order logic, in particular Fagin's theorem,
chap. 5.7 and 8.3. Notes from the 2nd lecture.
28/1: Grundläggande saker; kursbokens specifika Turing-maskin modeller samt
definitioner av tids- och minnesbegränsade Turingmaskiner och komplexitetsklasser,
och varför valet inte inverkar på de frågor vi kommer arbeta med (jämfört med andra
rimliga val av definitioner).
Kapitel 1 och 2; läs också kapitel 5.7 om andra ordningens logik.
Kanske hinner vi gå in på relationer mellan komplexitetsklasser; framför allt, vilka som
är inkluderade i vilka, för de mest grundläggande klasserna, samt hierarkisatsen; kapitel 7.
What to read (in English): Chapters 1, 2 and 7. If you are not familiar
with the material in chapters 3-5 you should also read this; for the moment at least, we can do without chap. 6. Notes from the 1st lecture.
Assignments
The assignments marked with '*' must be completed successfully
in order to pass the course.
Having achieved this the grade depends on how many among
the other (not *-star marked) assignments that one has completed successfully;
more information below; different subproblems, or "parts" (a, b, c etc.),
are each counted once when calculating the percentage.
Unless other directives are given, the numbers refer to
problems in Computational Complexity by Papadimitriou.
When solving the assignments/problems you may use
any results which are proved in the book, but not the
conclusions of other problems unless you solve them too.
Oracles, DP, the polynomial hierarchy:
14.5.10 (a), to show that P_h is included in NP and in coNP is
a *-assignement, the other inclusion is a non-*-assignment.
17.3.2 (a)* (b) (c), 17.3.3*, 17.3.4 (a) (b),
17.3.8*, 17.3.10, 17.3.12.
Deadline for all assignments, including those
from previous sets of assignments:
4 June.
coNP, function problems, random computation:
10.4.3*, 10.4.6, 10.4.7, 10.4.8*, 10.4.13*, 10.4.16*,
10.4.19 (a) (b), 11.5.5, 11.5.6, 11.5.13*, 11.5.14*,
11.5.15*, 11.4.16(a)*, 11.5.18, 11.5.23 (a) (b),
and assignements 3.1 (i)*, (ii)*, (iii)*, (iv) and 3.2
found
here. In assignment 3.1, |a-b| denotes the number of binary
digits which differ in the binary strings a and b; for example,
|1011 - 1101| = 2 because differences occur in two places. Deadline for *-assignments: 20 April.
Basics, complexity hierarchies, the reachability method,
reductions, completeness: 2.8.7*, 2.8.14*, 2.8.4, 2.8.5, 2.8.12,
7.4.3*, 7.4.4*, 7.4.5*, 7.4.6*, 7.4.7, 7.4.8, 7.4.9*,
8.4.3*, 8.4.4*, 8.4.9 (contains an a-part and another part just
labeled 'problem'), 8.4.15, 9.5.7*, 9.5.23(a)*, 9.5.23(b)*
(in the last two assignments you can reduce the problems to
other graph theoretic problems; for the notion 'subgraph'
see a note at the end of this page),
9.5.4(a), 9.5.29 (you need only consider the case when k=1),
5.8.13(a)*, 5.8.13(b). Deadline for *-assignments:
18 March.
Examination
The passing grades for the course are 3, 4 and 5.
The examination consists of the following parts:
(i) Assignments which are continuously given, below, during the course, and should be solved continuously during the course
(at least the *-exercises); deadlines are given for each set of exercises.
For grade 3 one has to pass the written exam (point (ii)) and adequately complete all assignments of part (i) that are marked
by '*' (see above). For grade 4 the requirements for grade 3 has to be met and in addition at least 50 percent of
the exercises without '*' has to be adequately completed; for grade 5 the requirements for grade 3 has to be met and in addition at least 75 percent of
the exercises without '*' has to be adequately completed.
Notes
1. Since I could not find an explanation of 'subgraph' in the book
I assume that it uses the conventional definition from graph theory:
H is a subgraph of G if every vertex of H is a vertex
of G and every edge of H is an edge of G.
H is an induced subgraph of G (which corresponds to
substructure in model theoretic terminology),
if in addition to the above, whenever {a,b} is an edge of G
and a and b are vertices of H, then {a,b} is an edge of H.
With the given definition of 'subgraph' it is straightforward to
solve 9.5.23 (a) and (b) when you find an appropriate problem to
reduce.