설명의 복잡성

기술 복잡도는 닐 이머먼이 쓴 수리 논리와 계산 복잡도 이론의 책이다.그것은 다른 종류의 논리를 사용하는 수학적 속성의 표현성이 다른 종류의 자원 경계 계산 모델에서 계산 가능성과 동등함을 보여주는 영역인 기술 복잡성 이론에 관한 것이다.그것은 1999년 스프링거-벨라그에 의해 그들의 책 시리즈인 컴퓨터 과학 대학원 교재에서 출판되었다.

토픽

이 책은 대략 1차 논리 5장, 2차 논리 3장,^[1][2] 고급 주제 7장으로 구성된 15장으로 구성되어 있다.

첫 번째 두 장에서는 1차 논리(1차 연산, BIT 술어 및 1차 쿼리 개념 포함)와 복잡도 이론(공식 언어, 리소스 경계 복잡도 클래스 및 완전한 문제 포함)의 배경 자료를 제공합니다.제3장은 1차 인식 가능한 언어가 로그 공간에서 인식될 수 있다는 증거와 로그 공간, 비결정론적 로그 공간 및 다항식 시간에 대한 완전한 언어의 구축을 통해 논리와 복잡성 사이의 연결을 시작한다.네 번째 장에서는 유도 정의, 고정 소수점 연산자 및 최소 고정 소수점 연산자와의 1차 로직 측면에서 다항식 시간의 특성에 대해 설명합니다.1차 주제에 대한 이 책의 부분은 병렬 랜덤 액세스 머신 및 회선의 ^[1][2][3]복잡성에 대한 리소스 경계의 논리적 특성에 대한 장으로 끝납니다.

6장에서는 논리적 표현 가능성을 입증하는 핵심 도구인 에렌푸흐트-프라세 게임을 소개하고 7장에서는 2차 논리를 소개합니다.그것은 존재론적 2차 논리의 관점에서 비결정론적 다항식 시간을 특징짓는 페이긴의 정리, NP-완전 문제의 존재에 대한 쿡-레빈 정리, 그리고 이러한 결과의 확장을 포함한다.8장에서는 게임을 사용하여 2차 ^[1][2][3]논리로 특정 언어의 표현 불능성을 증명합니다.

제9장은 비결정론적 로그 공간이 보완 하에서 닫힌다는 이머만-제렙세니 정리를 포함하여 언어의 보완과 전이적 닫힘 연산자에 관한 것이다.10장에서는 완전한 문제와 다항식 공간의 2차 논리 특성을 설명합니다.11장은 회로 복잡성의 균일성(문제 해결을 위한 회로의 존재와 알고리즘 구성성의 구별)에 관한 것이고, 12장은 복잡도 클래스의 논리적 특성에서 술어의 순서와 계수의 역할에 관한 것이다.13장에서는 하한에 대한 스위칭 보조항목을 사용하고 14장에서는 데이터베이스 및 모델 확인에 대한 적용에 대해 설명합니다.마지막 장에서는 이 ^[1][2][3]분야에서 여전히 연구가 필요한 주제들에 대해 간략히 설명합니다.

청중과 리셉션

이 책은 주로 이 ^[1]분야의 연구자에 대한 참조를 목적으로 하고 있지만, 대학원 과정의 기초로서도 사용될 수 있고, 이러한 목적을 위한 연습도 갖추어져 있다.논문이 자급자족적이라고 주장하지만, 리뷰어 W. 클로노스키(W. Klonowski)는 독자들이 고전적인 복잡성과 수학적 ^[2]논리의 기초 모두를 이미 이해할 필요가 있다고 쓰고 있다.

리뷰어 Anuj Dawar는 복잡성 이론의 핵심 문제에 논리적인 도구를 도입할 수 없는 점, 그리고 계산을 특징짓기 위해 논리 언어에 연산과 같은 추가사항을 추가해야 하는 점 등으로 인해 기술 복잡성의 초기 전망 중 일부가 위축되었다고 쓰고 있다.그럼에도 불구하고, 이 책은 연구자들에게 이러한 연구 라인과 덜 탐구된 ^[4]계산 복잡성에 접근하는 방법을 소개하는 방법으로서 유용하다고 그는 쓰고 있다.

레퍼런스