Connectivitat-st
En teoria de la complexitat, el problema de connectivitat-st o STCON (pel nom en anglès st-connectivity) és un problema de decisió tal que donat un graf dirigit, cal saber si un vèrtex t és accessible des de s.[1]
Formalment, el problema es descriu així:
CAMÍ = | D és un graf dirigit amb un camí del vèrtex s cap al vèrtex t
Complexitat
[modifica]Es pot demostrar que aquest problema pertany a la classe NL, ja que una màquina de Turing no determinista pot suposar el següent node d'un camí, mentre que la informació que ha de guardar és la longitud total del camí i quin node s'està avaluant. L'algorisme acaba si ha pogut arribar al node destí t o la longitud del camí excedeix n, el nombre de nodes del graf.
El complement d'aquest problema, conegut com no-connectivitat-st també està a la classe NL, ja que NL = coNL.
De fet el problema connectivitat-st és NL-complet, i per tant tot problema de la classe NL es pot reduir a aquest sota una reducció d'espai logarítmic.
El teorema de Savitch garanteix que l'algorisme es pot simular en O(log² n) d'espai determinista.
El mateix problema per grafs no dirigits s'anomena connectivitat-st no dirigit, i es va demostrar que està dins de la classe L-complet.
Referències
[modifica]- ↑ Michael., Sipser,. Introduction to the theory of computation. 2a edició. Boston: Thomson Course Technology, 2006. ISBN 0534950973.