Komplexitätstheorie Hausaufgaben 1

(181.040 VO SS 2,0)

Hausaufgabe 1.1

You overhear the following dialogue about x and y, both in [2, 3, ..., 100], between two mathematicians, let's call them Prof. P. and Prof. S. w.l.o.g.:

Well, I know xy, but I don't know x and y.
I know x+y, and I knew that you don't know x and y.
Hoho, but then I know x and y.
In that case I also know x and y.

Your task: Find x and y. If you know the answer, you can contact me to check whether we found the same solution.

Hausaufgabe 1.2

Beweise, dass Ramsey(3,4)=9.

Wolfgang Slany
Last modified: Tue Mar 7 18:40:37 CET 2000