PCPs und Programme

Betrachte

abbb ccc ddd d

a b c dd

$\Rightarrow$ mit PCPs kann man ,,rechnen``.

$\Rightarrow$ man kann jedes Programm in PCPs übersetzen.

Eigenschaften von PCPs (z. B. Lösbarkeit) sind (wenigstens) genauso schwer wie Eigenschaften von Programmen (z. B. Halteproblem).

Halteproblem algorithmisch unlösbar
$\Rightarrow$ PCP algorithmisch unlösbar.

Indiz: sehr kleine und trotzdem schwere PCP-Instanzen (d. h. mit sehr langer Lösung).

http://www.theory.informatik.uni-kassel.de/~stamer/pcp/