# [Zk] 8.6.2011

<{ForumPost(poster="eis", timestamp=2011-06-08 17:51:18)}>
Verze H  
  
1) 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.  
2) Ukaz, ze K <=<sub>1</sub> S   
3) Ukaz, ze existuje PRF f(z) pre ktoru plati: Fi<sub>f(z)</sub>(x) = x<sup>z</sup>  
4) 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.  
5) Najvacsi spolocny podgraf, dokaz, ze je NP-uply.  
  
cca Riesenia:  
1) 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  
2) vid dokaz Riceovej vety  
3) 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>  
4) 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  
5) vid minule pisomky. Z HK, G1 = G, G2 = kruznica nad |V| vrcholmi  
  
snad niekomu pomoze, vela stastia !
<{/ForumPost}>

<{ForumPost(poster="rur", timestamp=2012-01-19 01:28:18)}>
Řekl bych, že na 5. jde převést obecně hledání čehokoliv rozumného v grafu, ať už HK, HC, kliky nebo nezávislé množiny.
<{/ForumPost}>