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 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 , ?)(Vihje: Helppo palautus solmupeiteongelmasta (VC).)