NL(복잡성)

NL (complexity)
컴퓨터 과학의 미해결 문제:

(컴퓨터 과학에서 더 풀리지 않은 문제)

계산 복잡성 이론에서 NL(Nondeterministic Logarithmic-space)은 로그의 메모리 공간을 사용하여 비결정론적 튜링 기계가 해결할 수 있는 의사결정 문제를 포함하는 복잡도 등급이다.

NL은 결정론적 튜링 기계의 로그 공간 문제에 대한 등급인 L을 일반화한 것이다.어떤 결정론적 튜링 기계도 비결정론적 튜링 기계이기 때문에 우리는 L이 NL에 포함되어 있다는 것을 알고 있다.

NL은 계산 자원이 아닌 공간(또는 NSPACE)의 관점에서 NL = NSPACE(log n)로 공식적으로 정의할 수 있다.

복잡성 이론의 중요한 결과는 이 복잡성 클래스를 다른 클래스와 연관시킬 수 있게 하며, 관련 자원의 상대적 힘에 대해 말해준다.반면에 알고리즘 분야의 결과는 우리에게 어떤 문제들이 이 자원으로 해결될 수 있는지 알려준다.많은 복잡성 이론과 마찬가지로, NL에 대한 많은 중요한 질문들이 여전히 열려 있다. 컴퓨터 과학의 미해결 문제 참조.

간혹 아래 확률론적 정의 때문에 NL을 RL이라고 부르기도 하지만, 이 명칭은 NL과 같지 않은 임의의 로그 공간을 가리키는 데 더 자주 사용된다.

NL 완료 문제

ST 연결성 및 2만족도 등 로그 공간 감소 시 NL-완전성이 문제인 것으로 알려져 있다.ST-연결성은 지시된 그래프에서 노드 S와 T에 대해 각 조항이 2 리터의 분리인 명제 공식에 따라 T가 S. 2 만족도에서 도달할 수 있는지 여부를 묻는다. 이(가) 그렇지 않음을 나타내는 예는 다음과 같을 수 있다.

밀폐합물

2-만족을 위한 다항식 시간 알고리즘이 있어 P에 NL이 포함된 것으로 알려져 있으나, NL = P인지, L = NL인지는 알 수 없다.NL = co-NL로 알려져 있는데 여기서 co-NL은 보완이 NL인 언어의 등급이다.이 결과(이메르만-셀레프세니 정리)는 1987년 닐 이머만과 로베르트 스셀레프세니에 의해 독자적으로 발견되었고, 그들은 이 작품으로 1995년 괴델상을 받았다.

회로 복잡도에서 NL은 NC 계층 구조 내에 배치될 수 있다.1994년 파파디미트리오 16.1에서 우리는 다음과 같은 것을 가지고 있다.

C

더 정확히 말하면, NL은 AC에1 포함되어 있다.NL은 로그 공간에서 무작위화된 알고리즘으로 해결할 수 있는 문제의 등급인 ZPL과 오차 없이 동일한 것으로 알려져 있다.그러나 일부 저자들이 RL과 ZPL이라고 부르는 RL과 ZPL의 다항 시간 제한인 RLP 또는 ZPLP와 같거나 같지 않다고 알려져 있거나 믿어지고 있다.

우리는 사비치의 정리를 이용하여 NL을 결정론적 공간과 연관시킬 수 있는데, 이것은 어떤 비결정론적 알고리즘도 최대 2차적으로 더 많은 공간에서 결정론적 기계에 의해 시뮬레이션될 수 있음을 말해준다.사비치의 정리로부터 우리는 직접적으로 다음과 같은 것을 가지고 있다.

이는 1994년에 알려진 가장 강력한 결정론적 공간 포함이었다(Papadimitriou 1994년 문제 16.4.10, "대칭적 공간").더 큰 공간 클래스는 2차적 증가의 영향을 받지 않기 때문에 비계수적 및 결정론적 클래스는 동일한 것으로 알려져 있으므로 예를 들어 PSPACE = NPSPACE가 있다.

대체 정의

확률론적 정의

C가 절대 잘못 수용하지 않지만 1/3 미만의 시간 동안 잘못 거부될 수 있는 확률론적 튜링 기계가 있는 로그 공간에서 해결할 수 있는 의사결정 문제의 복잡도 등급이라고 가정하자. 이를 일방적인 오류라고 한다.상수 1/3은 임의적이다; 0 ≤ x < 1/2을 가진 x이면 충분하다.

C = NL. C는 결정론적 상대인 L과 달리 다항식 시간에만 한정되지 않는다는 점에 주목한다. C는 다항식 구성의 수를 가지고 있지만 무한 루프에서 벗어나기 위해 임의성을 사용할 수 있기 때문이다.다항식 시간으로 제한하면 RL 등급이 나오는데, RL 등급은 NL에 포함되지만 알려져 있지 않거나 NL과 동등하다고 믿어지는 등급이다.

다음과 같은 이유로 C = NL을 설정하는 간단한 알고리즘이 있다. 명백하게 C는 NL에 포함되어 있다.

  • 문자열이 언어에 없는 경우, 두 문자열 모두 모든 계산 경로를 따라 거부하십시오.
  • 문자열이 언어에 있는 경우, NL 알고리즘은 적어도 하나의 계산 경로를 따라, C 알고리즘은 계산 경로의 3분의 2를 따라 허용한다.

NL이 C에 포함되어 있다는 것을 보여주기 위해 NL 알고리즘을 이용하여 길이 n의 랜덤 계산 경로를 선택하고, 이것을 2회n 실행한다.길이 n을 초과하는 연산경로는 없고, 모두 2개의n 연산경로가 있기 때문에 수용경로(아래 상수에 의해 경계)를 타격할 가능성이 충분하다.

유일한 문제는 우리가n 2까지 올라가는 이진 카운터를 위한 로그 공간에 공간이 없다는 것이다.이것을 극복하기 위해 우리는 그것을 무작위화된 카운터로 대체한다. 그것은 단순히 동전 n개를 던져버리고 그들이 모두 정면에 착륙하면 멈추어 버리고 거부한다.이 사건은 확률 2가−n 있기 때문에, 우리는 멈추기n 전에 평균적으로 두 단계를 밟을 것으로 예상한다.로그 공간에서 카운트할 수 있는, 보이는 행에 있는 헤드의 수의 총계만 유지하면 된다.

NL이 보완에 따라 닫히는 임메르만-셀렙세니 정리 때문에, 이러한 확률론적 계산의 단측 오류는 영측 오류로 대체할 수 있다.즉, 이러한 문제는 로그 공간을 사용하고 절대 오류를 범하지 않는 확률론적 튜링 기계로 해결할 수 있다.또한 기계가 다항식 시간만 사용해야 하는 해당 복잡도 클래스를 ZPLP라고 한다.

따라서 우리가 우주만을 바라볼 때 무작위화와 비결정론은 똑같이 강력한 것으로 보인다.

인증서 정의

NL은 NP와 같은 클래스와 유사하게 인증서에 의해 동등하게 특성화될 수 있다. 추가 읽기 전용 1회 읽기 전용 입력 테이프가 있는 결정론적 로그 공간 경계 튜링 기계를 고려한다.언어는 그러한 튜링 기계가 추가 입력 테이프에서 적절한 인증서 선택을 위해 언어의 어떤 단어를 수락하고 인증서와 상관없이 해당 언어에 없는 단어를 거부할 경우에만 NL로 되어 있다.[1]

Cem Say와 Abuzzer Yakaryarylmaz는 위 문장의 결정론적 로그-공간 튜링 기계가 일정한 수의 무작위 비트만 사용할 수 있는 경계 오류 확률론적 공간 튜링 기계로 대체될 수 있다는 것을 증명했다.[2]

서술적 복잡성

NL의 간단한 논리적 특성화가 있는데, 여기에는 1차 로직으로 표현할 수 있는 언어와 추가적인 전이적 폐쇄 운영자가 포함된 정확한 언어가 포함되어 있다.

마감 속성

NL 등급은 운영보완, 유니온, 교차로, 결합, 클레인 스타에 의해 폐쇄된다.

메모들

  1. ^ Arora, Sanjeev; Barak, Boaz (2009). "Definition 4.19". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
  2. ^ A. C. Cem Say, Abuzzer Yakarillmaz, "불규칙한 무작위성을 가진 최종 상태 검증자", 컴퓨터 과학의 논리적 방법, Vol. 10(3:6) 2014, 페이지 1-17.

참조