"nomiaalne" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

Teoreem: Iga mitme lindiga TM-l ajalise keerukusega O(t(n)) töötava programmi jaoks leidub sama tööd tegev programm ühe lindiga TM-l, nii et tema ajaline keerukus on O(t2(n)). Teoreem: Iga 1 lindiga mittedeterministlikul TM-l ajalise keerukusega O(t(n)) töötava programmi jaoks leidub sama tööd tegev programm 1 lindiga deterministlikul TM-l, nii et tema ajaline keerukus on 2O(t(n)).
 DEF: DEF: Polünomiaalne keerukusklass P on nende ülesannete hulk, mis on lahenduvad ühe lindiga deterministlikul TM-l polünomiaalse ajaga : Summa, korrutamine, kui pikk on graaf, arvutil lahendatavad. DEF: Omadus C on lahenduv hulgal A (ja mõnel x-l hulgas A on omadus C), kui leidub arvutatav predikaat DEF: Omadus C on tuvastatav hulgal A, kui leidub arvutatav predikaat kus iga x korral leidub väärtus s (tõestus/sertifikaat).
 See V on verifitseerija.