Pražský informatický seminář - Pavel Pudlák: Complexity and Infinity

Vůdčím principem při axiomatizaci teorie množin bylo zachovat co nejvíce vlastností konečných množin také pro nekonečné množiny. Dnes, kdy nám chybí metody k řešení problémů v teorii složitosti, děláme v jistém smyslu opak: vytváříme domněnky o konečných strukturách na základě podobných nekonečných struktur. Například naše víra, že P ≠ NP se hlavně opírá o skutečnost, že rekurzivně spočetné množiny nejsou rekurzivní.

Ukážu několik příkladů takových domněnek v teorii složitosti a zmíním se o výsledcích, jež je možné chápat jako evidenci podporující platnost oněch domněnek. Tyto příklady pocházejí z důkazové složitosti – oblasti, která studuje složitost z hlediska logiky – ale mohou být formulovány v čistě výpočetních termínech. Jedna z těchto domněnek je, že neexistuje úplný problém pro jistou třídu vyhledávacích problémů.