- ...c.
-
Tapausvaativuuskäsitteiden määrittelystä ks. artikkeli
``Laskentaongelmien yksittäistapausten vaativuudesta''
(http://www.math.jyu.fi/ orponen/papers/ic_lmt.ps).
Artikkelista on kopio myös kurssimapissa.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...todistuksesta
-
Lähde: D. P. Bovet & P. Crescenzi, Introduction to the Theory
of Complexity, ss. 216-217.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...NP.
-
Itse asiassa em. approksimoitumattomuustuloksen todistamiseksi riittää
PCP-lauseesta heikompikin muoto NP = PCP(O(log n), O(log n)),
ja klikkiongelman kombinatorisista ominaisuuksista seuraa, että
ongelma on 1/2-approksimoituva jos ja vain jos se on
k-approksimoituva jollakin vakiolla k.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.