Tietojenkäsittelyteoria, kevät 2000
Harjoitus 12, to 13.4. klo 10-12 sali MaD381

1. Tarkastellaan optimimointiongelmaa MAX SAT: annetulle cnf-muotoiselle Boolen kaavalle on löydettävä kaavassa esiintyvien muuttujien totuusarvojakauma, joka maksimoi toteuttamiensa :n tekijöiden määrän. Suunnittele ongelmalle polynomisessa ajassa toimiva 1/2-approksimointialgoritmi. (Vihje: Valitse kunkin muuttujan totuusarvo ``ahneesti''.)
2. Olkoon MAX 3SAT ongelman MAX SAT erikoistapaus, jossa tarkasteltavat kaavat ovat 3cnf-muotoisia. Muodosta approksimoinnin säilyttävä palautus MAX 3SAT MAX CLIQUE.
3. Osoita, että jos , niin MAX SAT PTAS, so. ongelmalla MAX SAT ei voi olla polynomisessa ajassa toimivia -approksimointialgoritmeja mielivaltaisen pienillä . (Vihje: Olkoon M jonkin NP-täydellisen kielen -todistuskone. Muodosta kaava, joka kuvaa kaikilla mahdollisilla satunnaisjonoilla r, , niitä oraakkelivastausjonoja, joilla kone M hyväksyy syötteen.) Miten MAX SAT -ongelman approksimoituvuuden -kynnysarvo riippuu PCP-teoreeman parametrista q?