Rekursiooni ja keerukusteooria eksami konspekt
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
ülesande saaks teisendada selle probleemi jaoks.
Eksponentsiaalne keerukus nt: vaatame graafi sõlmesid kui väärtuste komplekte, igas hargnemiskohas on
produktsioon, millega on antud semantikareegid. Võib juhtuda, et me peame nt A leidmiseks juba teadma
A-d - võivad tekkida ringsõltuvused, selle ära-arvamine on väga eksponentsiaalne (kasvab järsult).
30 Ülesannete polünomiaalne redutseeritavus ja NP-täielikud ülesanded. SAT kui NP täielik ülesanne.
DEF: Kui redutseerimisfunktsioon f on polünominaalne, siis A on polünomiaalselt redutseeritav B-ks.
Teoreem: Kui ülesanne A on polünomiaalselt redutseeritav B-ks ning B on P klassis, siis A on ka P klassis.
annaabi.ee 
