"redutseerimisfunktsioon" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

ü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. DEF: Ülesanne B on NP täielik, kui ta rahuldab järgmisi tingimusi: B on NP klassis ja iga NP ülesanne A on polünomiaalselt redutseeritav ülesandeks B. Teoreem: SAT on polünomiaalselt redutseeritav ülesandeks CLIQUE. SAT: kas Boole’i valem on antud väärtuste korral tõene? Boole’i valemi saab alati