Tröskelkretsar och kommunikationskomplexitet

Abstrakt:

Inom kretskomplexitet försöker man visa att problem är svåra genom att visa att det krävs stora kretsar för att lösa dem. Hur kraftfull en krets är beror, förutom storleken, på vilken typ av beräkningselement (grindar) kretsen är uppbyggd av.

En majoritetsgrind med n indata ger utdata 1 om mer än hälften av indatabitarna är 1 och ger utdata 0 annars. Tröskelgrinden är en generalisering av majoritetsgrinden. Den beräknar en viktad summa av indatabitarna och ger utdata 1 om summan är större än ett visst tröskelvärde. Exempelvis kan man med en tröskelgrind jämföra två binärkodade heltal och avgöra vilket som är störst.

Tröskelkretsar av konstant djup och polynomisk storlek har visat sig vara ganska kraftfulla, till skillnad från kretsar med AND- och OR-grindar med samma begränsningar på storlek och djup. De är de enklaste "naturliga" kretsar för vilka man inte kunnat visa några starka undre gränser förutom i vissa mycket begränsade fall (väsentligen för majoritetskretsar av djup två).

Seminariet kommer att handla om en del av de övre och undre gränser som finns för tröskelkretsar. I samband med det kommer jag också att ta upp en annan beräkningsmodell där två eller flera spelare ska evaluera en funktion tillsammans. Kruxet är att ingen ensam spelare har tillgång till hela indatat, och målet är att evaluera funktionen genom att skicka så få och så små meddelanden som möjligt till andra deltagare. Kommunikationskomplexitet är ett användbart verktyg i många delar av komplexitetsteori, och i vårt fall visar det sig att problem som har hög kommunikationskomplexitet också kräver stora majoritetskretsar av djup två.