Kompaktioprobleemat

Kompaktioprobleemat ovat teoreettisen laskennan tutkimukseen liittyvä käsite, jolla tarkoitetaan ongelmia, joiden instanssit esitetään kompaktilla koodauksella sen sijaan, että ne kuvataan eksplisiittisesti. Esitystapa voi käyttää esimerkiksi boolean-lausekkeita, piirikaavioita tai muita tiiviitä rakenteita, joiden avulla voidaan kuvata suuria tai eksponentiaalisia rakenteita pienellä tekstivaralla. Tällainen esitys on keskeinen tiivistettyjen esitysten tutkimuksessa.

Formalisoidusti: ongelman syöte on tiivis kuvauksen pituuden mukaan mitattava, ja ratkaisu määritellään tämän tiiviin esityksen perusteella. Ratkaisu voi edellyttää instanssin purkamista tai arviointia suoraan tiiviin kuvauksen perusteella.

Monet kompaktioprobleemat ovat huomattavasti vaikeampia eksplisiittisesti esitettyjä versioita. Tiivistetyt muodot kuuluvat usein korkeammille monimutkaisuusluokille, kuten EXP. Tutkimus tarkastelee, miten koon kasvaessa laskenta-aika ja resurssit muuttuvat tiiviissä esityksissä.

Esimerkkejä ovat tiivistetyt versiot klassisista ongelmista, kuten SAT, Vertex Cover tai Hamiltonian Path, joissa grafiikka tai kaavat esitetään circuit- tai boolean-formulineina sen sijaan, että kaikkien yksittäisten komponenttien havainnointi tehtäisiin eksplisiittisesti.

Käytännössä kompaktioprobleemat tarjoavat välineitä suurten järjestelmien, kuten verkkojen tai biologisten verkostojen, teoreettiseen analysointiin ilman eksplisiittistä instanssiluetteloa. Alaan kuuluu tiiviiden esitysten laskennallinen vaikeus sekä yhteydet succinct-enkoodauksiin ja kompleksisuusteoriaan.