Otsikko:

Laskennallisten ominaisuuksien deskriptiivisestä vaativuudesta

Luennoija

• FT Juha Nurmonen
• Helsingin yliopisto

Aika ja paikka

• Perjantai, 27. huhtikuuta, 2001
• klo 12.15
• Sali A 414 (4. kerros), Tietojenkäsittelytieteen laitos

Lyhyt kuvaus

Deskriptiivisessä vaativuusteoriassa ongelman kompleksisuus pyritään kuvaamaan logiikan kielellä ja vaativuuden mittarina käytetään vaaditun logiikan voimakkuutta. Monet laskennalliset ominaisuudet ovat oleellisia vaativuusluokkien karakterisoinneissa. Tällaisia ovat esimerkiksi jaollisuusominaisuus piirivaativuusluokan ACC yhteydessä (ykkösiä on p:llä jaollinen määrä), majoriteettiominaisuus TC^0:n yhteydessä (vähintään puolet syötteen biteistä ovat ykkösiä) ja erilaiset aggregaattifunktiot SQL:ssä esiintyvässä laskennassa. Pyrimme tarkastelemaan joitakin loogisen ilmaisukyvyn rajoituksia tällaisille laskennallisille operaatioille.