st-anslutning

Inom datavetenskap är st-connectivity eller STCON ett beslutsproblem som frågar efter hörn s och t i en riktad graf , om t kan nås från s .

Formellt ges beslutsproblemet av

PATH = {⟨ D, s, t ⟩ | D är en riktad graf med en väg från vertex s till t}

.

Komplexitet

På en sekventiell dator kan st-anslutning enkelt lösas i linjär tid genom antingen djup-först-sökning eller bredd-först-sökning . Intresset för detta problem för beräkningskomplexitet gäller dess komplexitet med avseende på mer begränsade beräkningsformer. Till exempel, komplexitetsklassen av problem som kan lösas av en icke-deterministisk Turing-maskin som endast använder en logaritmisk mängd minne kallas NL . St-anslutningsproblemet kan visas vara i NL, eftersom en icke-deterministisk Turing-maskin kan gissa nästa nod på vägen, medan den enda information som måste lagras är den totala längden på vägen och vilken nod som för närvarande är under övervägande. Algoritmen avslutas om antingen målnoden t nås, eller om längden på vägen hittills överstiger n , antalet noder i grafen.

Komplementet av st-connectivity , känt som st-non-connectivity , är också i klassen NL, eftersom NL = coNL enligt Immerman–Szelepcsényi-satsen .

I synnerhet är problemet med st-anslutning faktiskt NL-komplett , det vill säga varje problem i klassen NL kan reduceras till anslutning under en loggutrymmesreduktion . Detta förblir sant för det starkare fallet med första ordningens reduktioner ( Immerman 1999, s. 51). Logrymdsreduktionen från vilket språk som helst i NL till STCON fortskrider enligt följande: Betrakta den icke-deterministiska logrymden Turing-maskinen M som accepterar ett språk i NL. Eftersom det bara finns logaritmiskt utrymme på arbetsbandet är Turingmaskinens alla möjliga tillstånd (där ett tillstånd är tillståndet för den interna finita tillståndsmaskinen, huvudets position och arbetsbandets innehåll) polynomiellt många. Kartlägg alla möjliga tillstånd i den deterministiska log-space-maskinen till hörn i en graf, och sätt en kant mellan u och v om tillståndet v kan nås från u inom ett steg av den icke-deterministiska maskinen. Nu är problemet med om maskinen accepterar detsamma som problemet med om det finns en väg från starttillståndet till det accepterande tillståndet.

Savitchs teorem garanterar att algoritmen kan simuleras i O (log ² n ) deterministiskt rymd.

Samma problem för oriktade grafer kallas oriktad st-anslutning och visades vara L -komplett av Omer Reingold . Denna forskning gav honom 2005 års Grace Murray Hopper Award . Oriktad st-anslutning var tidigare känd för att vara komplett för klassen SL , så Reingolds arbete visade att SL är samma klass som L. På alternerande grafer är problemet P -komplett ( Immerman 1999 , s. 54).

Sipser, Michael (2006), Introduction to the Theory of Computation , Thompson Course Technology, ISBN 0-534-95097-3
Immerman, Neil (1999), Descriptive Complexity , New York: Springer-Verlag, ISBN 0-387-98600-6