Kokoonpanoteoria kuvaa kappaleen monimutkaisuutta, jota ei määritellä avaruudessa olevien hiukkasten kokoelmana, vaan sen kokoamishistoriana. Kemiallisten yhdisteiden monimutkaisuuteen sovellettuna tämä on ensimmäinen menetelmä, joka voidaan kokeellisesti todentaa, toisin kuin muut algoritmit, joilta puuttuu kokeellinen todentamiskyky .
Kokoonpanoteorian kehitti vuonna 2017 kemisti Leroy Croninin johtama ryhmä Glasgow'n yliopistossa.
Kokoonpanoteoriassa kappaleita ei määritellä avaruudessa olevien hiukkasten kokoelmina, vaan niiden mahdollisen muodostumishistorian perusteella. Kappaleen monimutkaisuuden laskemiseksi se jaetaan rekursiivisesti sen osiin, jolloin tämän kappaleen "kokoonpanoavaruus" määritellään poluksi, jota pitkin tämä kappale voidaan koota sen alkeisosista.
"Kokoonpanoindeksi" määritellään pienimmäksi vaihemääräksi, joka tarvitaan kappaleen kokoamiseksi alkeisosista ja kappaleista, jotka ovat saattaneet olla olemassa aiemmin ja siten päätyä kokoonpanojoukkoon. Tämän lyhimmän polun tapauksessa kokoonpanoavaruus vastaa pienintä muistia eli pienintä operaatioiden määrää, joka tarvitaan tietyn kappaleen kokoamiseksi. Alkeisosien lukumäärästä riippumatta, tällaisista osista koostuvan objektin pienin kokoonpanoindeksi määräytyy lyhimmän yhteenlaskuketjun mukaan OEIS A003313.. Maksimaalinen kokoonpanoindeksi riippuu alkeisosien lukumäärästä . Lisäksi kokoonpanoindeksin määrittäminen on NP-täydellinen ongelma .
"Kokoonpanoavaruus" (engl. assembly space) voidaan määritellä merkkijonojen suunnattuna syklittömänä verkkona, jossa kaikki yksikön pituiset merkkijonot (alkeisosat) ovat saavuttamattomia lähdesolmuja ja loput merkkijonot ovat solmuja, joiden tuloaste on kaksi ja jotka vastaavat kokoonpanovaiheita. Solmut indeksoidaan riippumatta niiden kantamista merkkijonoista, joten kaksi eri solmua voi kantaa samaa merkkijonoa, kunhan niiden muodostumishistoriat ovat erilaiset.
Kokoonpanoavaruuden käsite voidaan laajentaa yhteiseksi kokoonpanoavaruudeksi, jossa useita kappaleita kootaan samanaikaisesti. Kolme keskenään epäekvivalenttia yhteistä kokoonpanoavaruutta on erotettu toisistaan: yksittäisoptimaalinen, jossa jokainen kohde kootaan optimaalisesti ja jokainen merkkijono esiintyy vain kerran; kertaluvultaan optimaalinen, jossa jokainen kohde kootaan optimaalisesti, mutta samaa merkkijonoa voi kantaa useampi solmu, joiden muodostumishistoriat eroavat toisistaan; sekä kollektiivisesti optimaalinen, joka minimoi koko avaruuden koon silläkin hinnalla, että jokin kohde kootaan epäoptimaalisella tavalla. Kollektiivisesti optimaalinen avaruus ei ole suurempi kuin kertaluvultaan optimaalinen, eikä tämä puolestaan suurempi kuin yksittäisoptimaalinen, joskin kaikki kolme kokoa voivat poiketa toisistaan. Näitä kolmea suuretta vastaavien päätösongelmien vaativuus eroaa toisistaan: kollektiivisesti optimaalisen avaruuden tapauksessa ongelma on NP-täydellinen, kun taas kahden muun tapauksessa se on NP-vaikea, eikä niiden kuulumista luokkaan NP ole ratkaistu.
Kokoonpanoavaruuteen voidaan liittää myös diskreetti Dirichlet'n energia, jolloin kokoonpanoindeksi, polun syvyys ja Dirichlet'n energia ovat keskenään riippumattomia.
Esimerkiksi kahdella binäärimerkkijonolla ja on sama pituus N bittiä ja sama entropia. Sekvenssin kokoonpanoindeksi on kuitenkin ((1.) luo "01":n lisäämällä sen kokoonpanojoukkoon, (2.) yhdistää "01":n kokoonpanojoukon "01":een lisäämällä "0101" kokoonpanojoukkoon, ja (3.) yhdistää toisessa vaiheessa luodun "0101":n kokoonpanojoukosta otetun "0101":n kanssa), kun taas sekvenssin kokoonpanoindeksi on , koska vain "01" kokoonpanojoukosta voidaan käyttää uudelleen.
Lähteet
Luokka:Graafiteoria Luokka:Biologiset teoriat Luokka:Termodynamiikka