톱니바퀴

컴퓨터 과학에서 st-연결성 또는 STCON은 지시된 그래프에서 t가 s에서 도달할 수 있는 경우 정점 s와 t를 묻는 결정 문제다.

공식적으로, 의사결정 문제는 다음과 같이 주어진다.

PATH = {tuD, s, t t D는 꼭지점 s에서 t}까지의 경로를 갖는 방향 그래프다.

복잡성

비결정론적 튜링 기계는 경로의 다음 노드를 추측할 수 있는 반면, 저장해야 하는 정보는 경로의 총 길이와 현재 고려 중인 노드뿐이므로 문제는 NL에 있는 것으로 보일 수 있다.알고리즘은 대상 노드 t에 도달하거나 지금까지 그래프의 노드 수인 n개를 초과하면 종료된다.

St-비연결성으로 알려진 St-연결성의 보완도 클래스 NL에 있는데, 이는 Immerman-Szepcsnei 정리에 의한 NL = coNL이기 때문이다.

특히, st-연결성의 문제는 실제로 NL-완전하다. 즉, 등급 NL의 모든 문제는 로그 공간 감소에 따라 연결로 환원할 수 있다.이는 더 강력한 1차 주문 감소 사례에 대해 여전히 유효하다(Umerman 1999, 페이지 51).NL의 모든 언어에서 STCON으로의 로그 공간 축소는 다음과 같이 진행된다.NL의 언어를 받아들이는 비결정적 로그 공간 튜링 머신 M을 고려한다. 작업 테이프에는 로그 공간만 있으므로 튜링 머신의 모든 가능한 상태(상태는 내부 유한 상태 머신의 상태, 머리 위치 및 작업 테이프의 내용)는 다항적으로 많다.결정론적 로그 공간 시스템의 가능한 모든 상태를 그래프의 정점에 매핑하고, 비결정론적 시스템의 한 단계 내에서 u에서 상태 v에 도달할 수 있는 경우 u와 v 사이에 에지를 넣으십시오.이제 기계가 받아들이는지의 문제는 시작 상태에서 받아들이는 상태에 이르는 경로가 존재하는지의 문제와 같다.

사비치의 정리는 알고리즘이 O(log² n) 결정론적 공간에서 시뮬레이션될 수 있음을 보장한다.

비방향 그래프에서도 동일한 문제를 비방향 s-t 연결이라고 하며, Omer Reingold에 의해 L-완전한 것으로 나타났다.이 연구는 그에게 2005년 Grace Murray Hopper 상을 수여했다.이전에는 SL 등급에 대해 비간접적인 st-연결성이 완결된 것으로 알려져 있었기 때문에, Ringold의 연구는 SL이 L 등급과 동일한 등급이라는 것을 보여주었다.교번 그래프에서 문제는 P-완전이다(Umerman 1999, 페이지 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