"verifitseerija" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt


 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. NP keerukuse klass (non-deterministic polynomial time) 83% 9% tähendab selliseid ülesandeid mida mittedeterministlik Turingi nii palju teadlasi arvab nii. masin suudaks lahendada polünomiaalse ajaga. nt suured faktoriaalid, Clique’i probleem: suurim grupp, mille saab teha nii, et iga tipp on teisega ühendatud. Rändkaupmehe ülesanne: tee graafi tipust s tagasi tippu s, läbides iga tippu täpselt üks kord.