Suunnittele kombinaatiopiirit seuraavien funktioiden toteuttamiseen:
jos ja vain jos
jollakin .
jos ja vain jos
.
Voit yksinkertaisuuden vuoksi olettaa, että kantaporttina on
käytettävissä AND-, OR- ja NOT-porttien lisäksi myös kahden bitin XOR.
Mikä on suunnittelemiesi piirien koko ja syvyys?
Totea, että mikä tahansa n muuttujan Boolen funktio
voidaan laventaa seuraavasti:
Minkä kokoinen kombinaatiopiiri funktiolle f saadaan tästä
kehitelmästä? Sovella kehitelmää funktioon
[Jatkoa edelliseen.]
Osoita, että mikä tahansa Boolen funktio
voidaan laskea
kombinaatiopiirillä, jonka koko on porttia.
(Idea: Muodosta edellisen tehtävän konstruktiota soveltaen
piiri, joka sopivasti valitulla parametrin
k arvolla toisaalta laskee kaikkik muuttujan Boolen funktiot,
toisaalta koostaa halutun n muuttujan funktion f sen k muuttujan
alifunktioista, so. käyttäen edellisen tehtävän lavennuskaavaa
n-k kertaa.)
Kieltä T, joka sisältää pelkästään muotoa olevia
merkkijonoja (so. ) sanotaan
laskurikieleksi (engl. tally language). Osoita,
että
Osoita,
että luokka P/poly sisältää myös ei-rekursiivisia kieliä.
Osoita, että .
(Vihje: Muodosta luokat erottava laskurikieli.)
Osoita, että mitään -palautusten suhteen ESPACE-kovaa
kieltä ei voida tunnistaa polynomista kokoa olevilla
kombinaatiopiireillä. Onko tulos voimassa myös -palautuksille?