on NLOG-täydellinen deterministisillä Turingin koneilla logaritmisessa
työtilassa laskettavien -palautusten suhteen.
(Miksi tulos ei ole mielenkiintoinen
-palautuksia käyttäen?)
Ratkaisuohje: Sovella harjoitusten 3 tehtävän 6 konstruktiota.
Edustajien valinta (engl. Hitting Set): Annettu kokoelma äärellisen perusjoukon S osajoukkoja(Vihje: Helppo palautus solmupeiteongelmasta (VC).)ja luonnollinen luku
. Voidaanko joukoista
valita sellaiset enintään k alkiota, että valittujen alkioiden joukossa on ainakin yksi edustaja kustakin joukosta
,
? (Toisin sanoen: onko olemassa sellaista joukkoa
,
, että
kullakin
,
?)