"faktoriaalid" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

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. Hamiltoni ahel on tee graafi tipust s tippu t, läbides iga tippu täpselt üks kord. DEF: Universaalsed probleemid, mis on omavahel NP klassis teisendatavad on NP-täielikud probleemid. NP-keeruline: kui on teada, et see probleem on lahenduv NP klassis, kuid pole teada, et mõne NP-täieliku