Proč je problém P vs. NP tak těžký?

Vycházíme z toho, že se nedaří dokázat netriviální dolní odhady výpočetní složitosti konkrétních problémů, a že kvůli tomu chybí přístupy k řešení fundamentálních problémů teorie složitosti jako je P vs. NP nebo DLOG vs. NLOG, a klademe si otázku po existenci důkazů podobného druhu. Uvažujeme matematiku jako výzkumný nástroj a jako jazyk s jednoznačnou interpretací každého tvrzení a s ověřitelnou argumentací. Formální systém nazveme algoritmicky ověřitelnou matematikou, tj. AV-matematikou (AV - algorithmically verifiable), jestliže je konzistentní a lze v něm algoritmicky rozhodnout, zda daný text je důkazem, či ne.

Ukážeme, že v každé AV-matematice existuje nekonečně mnoho algoritmů, pro které nelze dokázat, zda pracují v polynomiálním čase nebo ne a současně pro ně nelze dokázat, zda řeší nebo neřeší nějaký NP-těžký problém. To nás vede k nové verzi P jakožto třídy problémů rozhodnutelných pomocí algoritmů, o nichž lze dokázat, že pracují v polynomiálním čase. Nakonec ukážeme, že jestliže P = NP, potom existuje konstruktivní důkaz této skutečnosti.