Complexity Theory
General
The course is taught by Lev Beklemishev and the afternoon work sessions
are led by Sander en Joost respectively. We work from the book
"Introduction to the Theory of Computation" by Michael Sipser.
(ISBN 0-534-94728-X bla bla bla.)
Lev
can be found at room 436 and Joost can be found at room 438.
Students whose sur-name is not
before "Heuvel" in the lexicographical order are in group 2 which is led
by Joost. The others are in group 1. There are no other working groups.
Every week a student can obtain one bonus point by making some homework.
Assignments will be handed out during the lessons but can also be retrieved
from this page. In the end the final mark (0= < f = < 10 (prove this!))
is computable from the
bonus (0= < b = < 6) and the exam mark (0= < e = < 10) by means of the
following formula: f=e+ b*(100-e^2)/300.
Week 1
The exercises of the first week can be retrieved from here.
Exercises week 1,
including homework
[
DVI |
Postscript|
Pdf formaat]
In Class a general introduction has been given to the theory of
computational complexity. Students who will solve the P=NP problem will
be exempted from the exam. Definition of Turing machine
has beens given.
Decidable and RE languages have been introduced. A language is RE iff there
is a (total) computable function enumerating it.
In group 2 the exercises up to and including 7 have been treated. Exercise
4 is this weeks homework. The homework includes an implementation of
exercise 4 in Turings world. This can be found on the macs. The homework
has to be hand in before the beginning of the lecture on the next tuesday.
The homework was valuated in the following way. Actually this way is just
a genaral philosophy and most likely the real valuation function will not
be computable. So here a general indication. In total one point could be
obtained. We gave 0.2 for idea and specification, 0.2 for syntax,
0.2 for elegance, 0.4 for correctness and 0.1 for doing it in a
second format. The final score will be something like
max(0.4, min(1, total score)). Anyway we'll make something up.
Week 2
In classes we spoke on the Halting problem, on Universal Turing machines
and RE sets in general. (A set is decidable iff both the set and its
complement is RE.)(A fuction is computable iff its graph is RE.) In the
work-session after the class we went over the class and did exercise 8, 9
and 11 of the previous week.
Exercises week 2,
including homework
[
DVI |
Postscript|
Pdf formaat]
In the workgroup of Joost, only exc. 1 and two have been treated. The lecture
on wednesday provided a proof of the non decidability of HALT.
We also spoke of other non decidable RE sets. After the break the notion
of m-reducability has been introduced. We have seen this to be a partial
order (reflexive and transitive). Also we know that decidabilty and RE-ness
of certain sets can be obtained e.g. if A m-reduces to B and B is
decidable resp. RE, then A is decidable resp. RE. We also know that
A m- < = B iff A^c m-<= B^c. We have seen that HALT is RE-complete.
Finally a proof of Rice's Theorem is given.
For correcting the homework we used the following vague criteria: for the
a question you could obtain 0.5 and for the b-question too. In a 0.1
for the definition of re, 0.2 for the idea (using either \phi or the
universal TM) and 0.2 for working this out idea. In the b-question
approximately 0.1 for spelling out the situation for example by using
a diagram, 0.2 for a serious attempt with a typical complexity
theory structure (suppose it were ...., now consider ...., apply this to
itself and behold). 0.2 point for correctness.
Week 3
In week 3 a proof of the undecidability of first order logic is presented.
This proof makes use of coding turing machines in fo logic and is in its
basic form extracted from the following:
G. Boolos and R. Jeffrey, Computability and Logic, 2nd ed.,
CUP, Cambridge, 1982.
ISBN 0 521 29967 5 blablabla.
Chapter 10.
In class on tuesday a hisorical treatment has been given from
Leibniz's dream to the solution of the "Entscheidungsproblem" by A. Church.
An outline is given to code Turing machines in some formulation of
mathematics. A good candidate was ZFC but we actually spoke of some
stronger system, GB of G\"odel Bernays, which was finitely axiomatizable.
Eventally we saw that also FOL can be seen (because GB
is finitely axiomatized) as strong enough to formulate mathematics.
In the work groups we studied exercise 2,3,4 of previous week and read an
article on how to code Turing machines in the language of arithmetic.
Exercises week 3,
including homework
[
DVI |
Postscript|
Pdf formaat]
On wednesday we moved into the topic of computational complexity. The notions
of small o symbol and big O symbol have been introduced. This was seen not
to be robust in the sense that it is depending on the machine model you are
using. It is also depending on the way you represent the input. The class
P was introduced (P=TIME(n^(O(1)))). P is robust. This actually is a thesis
which has the same status as CT-thesis. Will this thesis hold.......?
In the workgroup exercises 1,3 and 6 have been treated. Also we looked at
f=o(g) --> f=O(g) and the converse.
For correcting the execrcises we used more or less the following criteria:
analysis of the problem:1; sketch the idea of the solution:2;
showing that this is indeed P-time:2; giving in some detail a correct
algorithm:5.
Week 4
On tuesday we introduced the NP time complexity class. We spoke on
p-reducability and obtained similar results as with m-reducibility. So
A<=_p B and B is P respectively NP then A is also P respectively NP. We
introduced the notion of NP completeness. ClIQUE is NP-complete. (no
proof yet). Most likely compositeness of numbers is neither P nor NP.
Cryptography makes essential use of this. (RSA). In the workgroup we finished
the exercises of previous week and started on the first one of this week.
Exercises week 4,
including homework
[
DVI |
Postscript|
Pdf formaat]
On wednesday we embarked on the notion of NP-completeness. Without proof
we considered the NP-completeness of SAT, we also saw NP-completeness of
CNF-SAT (of formulas in conjunctive normal form) and of 3-SAT (of formulas
in CNF with at most 3 literals at each clause). We gave a reduction of
3-SAT to CLIQUE. A proof idea is given of the proof of NP-completeness
of SAT (Cook, Levin). In the workgroup we finished the exercises of week 4
(actually without doing 3).
For correcting the homework we more or less used the following criterium:
reformulating the problem and using the fact that SAT is NP complete: 0.3,
0.5 for a correct algorithm and 0.2 for checking that the algorithm runs
in polinomial time.
Week 5
Joost estava en Sevilla. Ole!
We spent Tuesday proving Cook's theorem on NP-completeness of SAT.
On Wednesday we studied another NP-complete problem called SUBSET SUM
(from a given multiset of natural numbers select a subset which sums up
to a given target number). We polynomially reduced 3-SAT to SUBSET SUM.
Then we embarked upon space complexity.
Simple relationships between time and space complexity bounds were discussed.
Then we defined the class PSPACE
and introduced the notion of PSPACE-completeness. Quantified boolean logic
was presented, the problem of deciding the truth of quantified
boolean formuas (TQBF) has been introduced and some overview of other
PSPACE-complete problems was given.
Exercises week 5,
including homework
[
DVI |
Postscript|
Pdf formaat]
In the workgroup we solved all (non-housework) excercises for this week.
We spent some time discussing the difficult problem No.1, which was
supplied with a wrong hint in the previously circulated version of the
list of problems. In correcting the homework we used the following
arithmetic: rephrasing the problem and spelling out the definitions: 0.2,
giving a reduction, 0.6 (2 * 0.3 for k< n/2 and n/2< k), polynomiality 0.2.
Week 6
On Tuesday we proved PSPACE-completeness of TQBF. Then we explained
a relationship between quantifiers and games and proved PSPACE-completeness
of the problem of whether the first player has a winning strategy
in the so-called generalized georgraphy game.
On Wednesday we introduced probabilistic Turing machines and the class
BPP. We discussed the amplification lemma and probabilistic
polynomial primality tests. In the course of discussing primality
we introduced residue rings and Fermat's Little Theorem and
pseudoprime numbers.
Finally we discussed cryptography. The system of one-time pad
was one example. The main example was RSA public key cryptosystem.
Exercises week 6,
including homework
[
DVI |
Postscript|
Pdf formaat]
The RSA protocol is treated in the textbook on page 377.
Homework can be handed in any time before the final exam. Give a copy
either Lev or Joost or send it as a .ps-file to Joost.
Our program leading up to the exam will be as follows. There will be a
question session on Wednesday, 13-12-00, from 15:00 till 17:00 in room
465 of "het Bestuursgebouw".
The exam will be held on 21-12-00 in T1:A .
Students are also welcome to bother either Joost or Lev at their rooms.
Here goes a list of specified items which constitute the content of our course:
"Logical Complexity"
A course program by L. Beklemishev
1. Turing machines. Church-Turing thesis.
2. Computable partial functions.
Decidable and RE languages and sets.
3. Graph theorem, Enumeration theorem for RE languages.
5. Universal Turing machine. Undecidability of the halting problem.
6. m-reducibility. m-completeness of the halting problem.
6. Undecidability of invariant properties of programs.
Rice theorem. (* Only formulated as a problem in Sipser *)
7. Undecidability of first order logic. (* not to be found in Sipser,
see Boolos/Jeffrey *)
8. Time and space complexity measures.
9. Big "O" and small "o" symbols.
10. Time and space complexity classes. Class P.
Polynomial simulation of natural computation models.
11. Class NP. Examples of problems in NP. The status of
P=NP question.
12. p-reducibility. The notion of NP-completeness.
13. NP-completeness of satisfiability problem (Cook/Levin).
14. NP-completeness of CLIQUE problem.
15. NP-completeness of SUBSET SUM problem.
16. Basic relationships between time and space complexity
measures. The class PSPACE and PSPACE-complete problems.
17. Quantified boolean logic.
18. PSPACE-completeness of the problem of validity of
quantified boolean formulas.
19. Quantifiers and games. PSPACE-completeness of the
problem of having a winning strategy in a generalized
geography game.
20. Elements of cryptography. "One-time pad" cryptosystem.
22. Probabilistic Turing machines. The class BPP.
Amplification lemma (without proof).
23. Probabilistic primality testing (idea).
Fermat's little theorem (without proof). Pseudoprime numbers.
The idea of how to generate large primes.
24. Public key cryptosystems. The system RSA.
LET OP!!!!! HET TENTAMEN GAAT ONDANKS DE TREINSTAKING GEWOON DOOR!!!!
Hier een stukje correspondentie ter voorbereiding van het tentamen:
Dag L,
Er zijn een boel functies die partieel berekenbaar zijn maar niet kunnen
worden uitgebreid door een totale berekenbare functie.
Met al bekende gegevens kun je laten zien dat \phi_x (x) een voorbeeld
is. Immers stel hij is wel uitbreidbaar, dan met het huiswerk van week
twee, kun je een tegenspraak afleiden, want zullen de twee verzamelingen
wel sepereerbaar zijn.
Je kunt het ook direct doen. Beschouw daarvoor \phi_x (x) + 1. Stel deze
is wel uitbreidbaar dan heeft deze uitbreiding een code e. En nu, what
about \phi_e(e). Hier moet een antwoord uit komen omdat \phi_e totaal is,
maar hieruit volgt dat \phi_e(e)=\phi_e(e)+1. Bizar, dus niet...
Weet je overigens dat de treinen staken??
On Tue, 19 Dec 2000, Laura Korte wrote:
> Hoi,
>
> Wat is het antwoord op vraag 11 van week 1?
> Alvast bedankt :-)
>
> YS,
> Laura.
>
>
Ciao Yohann,
If you could give me tomorrow the calculations also of your answer, that
would be fine. There was in the book also some info on RSA. The pagenumber
is on the webpage.
On generating big primes. This is a highly non-trivial business making use
of advanced number theory. This is of course off course, I mean to say, not
included in the exam.
See you tomorrow,
Joost.
On Wed, 20 Dec 2000, Yohann Le Yaouanc wrote:
> Dear Joost,
....
....
> P.S.:it seems i ve lost my last lecture's notes before writting them down
> properly on my handbook,and if i ve find about RSA and pseudo primes on the
> web,i still do not remember how to produce high prime numbers.
> If you think it would be easier to explain it "physically",i guess i can
> pass to your office today (even if i m still working for tomorrow).
> hope you ll get this mail in time,
> sincerely yours,
> Yohann.
Final exam ,
[
DVI |
Postscript|
Pdf formaat]
Joost Joosten
Last modified: Fri Jan 12 15:00:11 MET 2001