페이긴의 정리

Fagin's theorem

파긴의 정리는 복잡도 이론의 가장 오래된 결과이며, 복잡도 이론은 문제를 해결하기 위한 알고리즘의 행동보다는 논리적인 관점에서 복잡도 클래스를 특징짓는 계산 복잡도 이론의 한 분야이다.이 정리는 실존적 2차 논리로 표현 가능한 모든 성질의 집합이 정확히 복잡도 클래스 NP라고 말한다.

그것은 1973년 로널드 페이긴에 의해 그의 박사학위 논문에서 증명되었고 1974년 그의 논문에 실렸다.2차 공식에 의해 요구되는 특성(한 방향으로)은 Lynch의 정리에서 개선되었고, Grandjean의 몇몇 결과는 비결정론적 랜덤 액세스 기계에 더 엄격한 경계를 제공했다.

증명

페이긴의 1974년 논문과 더불어, 임머맨 1999는 이 정리에 대한 상세한 증거를 제공한다.모든 실존적 2차 공식은 비결정론적으로 모든 실존적 수식 변수의 값을 선택함으로써 NP에서 인식될 수 있다는 것을 보여주는 것은 간단하다. 따라서 증명의 주요 부분은 NP의 모든 언어가 실존적 2차 공식에 의해 설명될 수 있다는 것을 보여주는 것이다.이를 위해 2차 실존 수량자를 사용하여 계산 테이블을 임의로 선택할 수 있습니다.보다 상세하게 말하면, 비결정론적 튜링 기계의 실행 트레이스의 모든 시간 단계에 대해, 이 표는 튜링 기계의 상태, 테이프 내의 위치, 모든 테이프 셀의 내용 및 그 단계에서 기계가 어떤 비결정론적 선택을 하는지를 부호화한다.이 부호화된 정보를 구속함으로써 테이프 내용 및 각 시간 스텝에서의 튜링 머신 상태 및 위치가 이전 시간 스텝에서 이어지는 유효한 실행 트레이스를 기술하도록 1차 공식을 사용하여 할 수 있다.

증명에 이용되는 주요 약어는 길이 n의k 선형 순서(예를 들어 임의의 시간 단계에서의 시간 단계 및 테이프 내용의 선형 순서)를 크기 n의 우주 A의 2k-ary 관계 R로 부호화할 수 있다는 것이다.이를 위한 한 가지 방법은 A의 선형 순서 L을 선택한 다음 R을 L에 대한 A의 k-튜플 사전 순서로 정의하는 것입니다.

「 」를 참조해 주세요.

레퍼런스

  • Fagin, Ronald (1974). "Generalized first-order spectra and polynomial-time recognizable sets". In Karp, Richard M. (ed.). Complexity of Computation: Proceedings of a Symposium in Applied Mathematics of the American Mathematical Society and the Society for industrial and Applied Mathematics held in New York City, April 18–19, 1973. SIAM–AMS Proceedings. Vol. 7. American Mathematical Society. pp. 43–73. ISBN 978-0-8218-1327-0. MR 0371622.
  • Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. pp. 113–119. ISBN 0-387-98600-6.

추가 정보