Matfyz Wiki
Verze H
Ukaz, ze mnozina S = {e | |W<sub>e</sub> | >= e + 1} je RS. Alg overujuci pre dane e, ci patri do S staci popisat neformalne.
Ukaz, ze K <=<sub>1</sub> S
Ukaz, ze existuje PRF f(z) pre ktoru plati: Fi<sub>f(z)</sub>(x) = x<sup>z</sup>
Mas black-box, co vie odpovedat, ci je mozne vyriesit danu instanciu LOUP v konstantnom case. Popis polynom. alg, ktory najde rozdelenie mnoziny prvkov na na polovice s rovnakou velkostou.
Najvacsi spolocny podgraf, dokaz, ze je NP-uply.
cca Riesenia:
W<sub>e</sub> | >= e + 1 prepisat na existuje y : Fi<sub>e</sub>(y) konverguje a pocet takych y je aspon e+ 1. To znamena, ze existuje s, take, ze Fi<sub>e,s</sub>(y) konverguje. + pocitadlo, ze ich mam uz aspon e+1. veta => existuje a PRP => S je RS
vid dokaz Riceovej vety
s-m-n veta s<sub>1</sub><sup>1</sup> (e,z) a 3 for cykly, ktore pre pevny parameter z a dane x ( nepotrebujes while ) spocitaju x<sup>z</sup>
cca Hlavna mnozina A, vytvorim A' a B. A' = A[0], B=A-A'. postupne pre kazdy vrchol v z B zistim, ci B-v (black-box) ma riesenie, ak ano, tak v z B odoberiem a pridam do A. cca
vid minule pisomky. Z HK, G1 = G, G2 = kruznica nad |V| vrcholmi
snad niekomu pomoze, vela stastia !