Pojem polynomiálně počitatelné funkce je intuitivně poměrně jasný: funkce je polynomiálně počitatelná, jestliže ji počítá algoritmus, který pro zpracování libovolného vstupu vystačí s počtem kroků, který je omezen polynomem v délce onoho vstupu. Exaktní definice je ale ne tak jasná, neboť pro explikaci toho, jak se počítají ony kroky a čeho kroky to jsou, je nutný nějaký výpočtový model, například Turingovy stroje. Je ale zajímavé, že existuje i "bezestrojová" charakterizace tohoto pojmu, která je podobná definici primitivně rekurzívních funkcí. Tomuto tématu jsou věnovány články [1] a [2]. Vypracujte vlastní verzi výkladu této problematiky. Rozmyslete si obsah článku [1], doplňte všechny vynechané detaily a udělejte si vlastní názor na to, zda a jaký účel onen článek splnil. Podle vlastní úvahy případně porovnejte články [1] a [2]. Použijte, ovšem s korektní citací, cokoliv z [3]. Vypracujte teorii polynomiálně počitatelných funkcí ve stylu teorie primitivně rekurzívních funkcí. K [3] případně přidejte důkaz nebo náznak důkazu, že bezestrojová definice je ekvivalentní definici založené například na Turingových strojích.
Seznam odborné literatury
[1] S. Bellantoni, S. Cook. A New Recursion-Theoretic Characterization of the Polytime Functions. Computational Complexity 2:297-110, 1992. [2] A. Cobham. The Intrinsic Computational Difficulty of Functions, in: Proc. Logic, Methodology, and Philosophy of Science II, Y. Bar-Hillel ed., pp. 24-30. North Holland, 1965. [3] P. Mach. Bezestrojová charakterizace funkcí počitatelných v polynomiálním čase. Předběžná verze nefinalizované ročníkové práce. Katedra logiky FF UK, 1998.
- zadáno a potvrzeno stud. odd.