ulottuvuusongelma

Ulottuvuusongelma on yleisnimi useille päätöksellisille ongelmille matematiikassa ja informatiikassa, joissa tutkitaan, voiko annettu rakenne laajentaa suuremmaksi rakenteeksi siten, että nykyiset osarakenteet säilyvät ja laajennus täyttää määritellyn ominaisuuden. Termi viittaa sekä teoreettiseen ulottuvuuteen että käytännön suunnittelutilanteisiin, joissa kokonaisuutta tarkastellaan suuremmassa kontekstissa. Ulottuvuusongelmaa esiintyy esimerkiksi graafeissa, relaatiomalleissa sekä erilaisissa mallintamiskonteksteissa.

Formaali muotoilu: Olkoon A annettu rakenne kielessä L ja P ominaisuus, jonka voi määritellä L:llä. Ulottuvuusongelma kysyy, onko olemassa rakenne B, jossa A esiintyy aliprakenteena ja B täyttää ominaisuuden P. Eri konteksteissa laajennus voi olla paikallinen (sovellettavissa vain osaan A:ta) tai globaali (koko rakenne muuttuu). Esimerkkinä graafeista: voidaan kysyä, voiko annettuun graafiin G laajentaa suuremmaksi graafiksi G' niin, että G' täyttää tietyn ominaisuuden, esimerkiksi planaarisuus tai tietty väritys.

Variaatiot ja kompleksisuus: Ongelman tarkka muoto ja tulokset riippuvat kielestä ja ominaisuudesta. Joissakin tapauksissa ulottuvuus on ratkeamaton (undecidable) tai NP-kova, kun taas tietyissä konteksteissa on kehitetty tehokkaita algoritmeja ja heuristiikkoja. Tutkimuksessa tarkastellaan myös eroa paikallisen ja globaalin ulottuvuuden välillä sekä sitä, millaista laajennusta on mahdollista saavuttaa.

Sovellukset: Ulottuvuusongelmia tarkastellaan muun muassa tietokantateoriassa, ohjelmistotarkastuksessa sekä verkkorakenteiden suunnittelussa ja mallien varmennuksessa. Ne auttavat ymmärtämään, millaisia laajennuksia järjestelmään voidaan tehdä säilyttäen nykyiset ominaisuudet ja mitkä lisävaatimukset ovat ratkaisevia.

Lisätietoa: Tutkimusaihe on monipuolinen ja kytkeytyy graafiteoriaan, logiikkaan ja mallintamisen teoriaan. Kirjallisuudessa käytetään usein termejä extendibility, embeddability ja upotettavuus riippuen kontekstista.