구조 복잡성 이론

이 페이지는 컴퓨터 과학의 계산 복잡성 이론의 구조적 복잡성 이론에 관한 것이다.응용 수학의 구조적 복잡성은 구조 복잡성(응용 수학)을 참조한다.

컴퓨터 과학의 계산 복잡성 이론에서, 구조 복잡성 이론이나 단순한 구조 복잡성은 개별적인 문제와 알고리즘의 계산 복잡성보다는 복잡성 등급에 대한 학문이다.그것은 다양한 복잡성 계층의 내부 구조와 다른 복잡성 계층 간의 관계에 대한 연구를 포함한다.^[1]

역사

이 이론은 이러한 종류의 가장 중요한 첫 번째 문제인 P = NP 문제를 해결하려는 (아직도 실패) 시도의 결과로 나타났다.대부분의 연구는 P가 NP와 같지 않다는 가정과 복잡성 계층의 다항 시간 계층이 무한하다는 더 광범위한 추측에 근거하여 행해진다.^[1]

중요한 결과

압축 정리

압축 정리는 계산 가능한 기능의 복잡성에 관한 중요한 정리다.

정리는 계산 가능한 경계를 가진 가장 큰 복잡도 등급은 존재하지 않으며, 계산 가능한 모든 함수를 포함한다.

공간 계층 구조 정리

공간 계층 구조 이론은 결정론적 기계와 비결정론적 기계 모두 특정 조건에 따라 더 많은 공간(비결정론적)에서 더 많은 문제를 해결할 수 있다는 것을 보여주는 분리 결과들이다.예를 들어 결정론적 튜링 기계는 공간 n보다 공간 n 로그 n에서 더 많은 의사결정 문제를 해결할 수 있다.시간에 대한 다소 약한 유사 이론은 시간 계층 구조 이론이다.

시간 계층 구조 정리

시간 계층 구조 이론은 튜링 기계에 대한 시간 경계 계산에 관한 중요한 진술이다.비공식적으로, 이러한 이론들은 더 많은 시간이 주어지면 튜링 기계가 더 많은 문제를 해결할 수 있다고 말한다.예를 들어 n시간으로는² 해결할 수 있지만 n시간으로는 해결할 수 없는 문제가 있다.

발리안트-바지라니 정리

발리안트-바지라니 정리는 계산 복잡성 이론의 정리다.레슬리 발리언트와 비제이 바지라니에 의해 1986년에 출판된 독특한 해결책을 탐지하는 것만큼이나 쉽다는 제목의 논문에서 증명되었다.^[2]정리에서는 Unambiguous-SAT에 대한 다항 시간 알고리즘이 있으면 NP=RP라고 기술하고 있다.그 증거는 물물무리-바지라니 분리 보조정리(Mulmuley-Vazirani)에 기초하고 있으며, 이후 이론 컴퓨터 과학에서 많은 중요한 응용에 사용되었다.

시퍼-라우테만 정리

Sipser-Lautemann 정리 또는 Sipser-Gacs-Lautemann 정리에서는 BPP(Bounded-error Probabilistic Polyomial) 시간이 다항 시간 계층에 포함되며, 보다 구체적으로 specifically₂ ∩ π이라고₂ 기술하고 있다.

사비치의 정리

1970년 월터 사비치(Walter Savitch)에 의해 증명된 사비치(Savitch)의 정리는 결정론적 공간 복잡성과 비결정적 공간 복잡성 사이의 관계를 제공한다.\$Oomega(\log(n$\log(n$)}$ 함수 f${\displaystyle \mathrm{\Omega }}$(${\displaystyle \log }$(n)})에 대해$,$

${\displaystyle {\mathsf {NSPACE}\좌(f\좌(n\우)\우)\subseteq {\mathsf {DSPACE}}\좌(f\좌)(n\우)^{2}\우)}$

토다의 정리

도다의 정리는 도다 세이노스케가 논문 'PP는 다항식-시간 서열처럼 딱딱하다'(1991)에서 입증한 결과로서 1998년 괴델상을 받았다.정리는 전체 다항식 계층 구조 PH가 P에^PP 포함되어 있다고 기술하고 있다. 이는 PH가 P에^#P 포함되어 있다는 밀접하게 관련된 진술을 암시한다.

임메르만-셀레프세니 정리

임메르만-셀렙세니 정리는 1987년 닐 이머만과 로베르트 스셀렙세니에 의해 독립적으로 증명되었으며, 이 정리는 1995년 괴델상을 공동 수상했다.그 일반적인 형태에서, 정리는 어떤 함수 s(n) ≥ 로그 n에 대해 NSPACE(s)(n) = co-NSPACE(s) = co-NSPACE(s)를 명시한다.결과는 NL = co-NL로 동등하게 명시된다. s(n) = log n일 경우 특별한 경우지만, 표준 패딩 인수에^{[citation needed]} 의한 일반 정리를 암시한다.그 결과는 두 번째 LBA 문제를 해결했다.

연구 주제

이 분야의 주요 연구 방향은 다음과 같다.^[1]

• 복잡성 계층에 대한 다양한 미해결 문제에서 기인하는 의미에 대한 연구
• 다양한 유형의 자원 제한 감소와 그에 상응하는 완전한 언어에 대한 연구
• 저장 및 데이터 액세스에 대한 다양한 제한 및 메커니즘의 결과 연구

참조