복잡도 클래스 목록
List of complexity classes |
이것은 계산 복잡도 이론의 복잡도 클래스 목록입니다.기타 계산 및 복잡도 주제에 대해서는 계산 가능성 및 복잡도 항목 목록을 참조하십시오.
이러한 수업의 대부분은 원래 수업의 모든 언어를 보완하는 '코' 파트너를 가지고 있습니다.예를 들어 언어 L이 NP에 있는 경우 L의 보완은 co-NP에 있습니다(이것은 NP의 보완이 co-NP라는 것을 의미하지 않습니다.양쪽에 있는 것으로 알려진 언어와 어느 쪽에도 없는 다른 언어가 있습니다).
수업의 "가장 어려운 문제"는 그 수업의 다른 모든 문제를 그 수업으로 축소할 수 있도록 그 수업에 속하는 문제들을 말한다.게다가 그 감소는, 소정의 클래스 또는 그 서브셋의 문제이기도 합니다.
| #P | NP 문제에 대한 솔루션 카운트 |
| #P-완료 | #P에서 가장 어려운 문제 |
| 2회차 | 이중 지수 시간 내에 해결 가능 |
| AC0 | 유계 깊이의 회로 복잡도 클래스 |
| ACC0 | 유계 깊이 및 계수 게이트의 회로 복잡도 클래스 |
| AC | 회선 복잡도 클래스 |
| 아. | 산술 계층 |
| 액세스 포인트 | 튜링 기계를 번갈아 사용하는 문제의 클래스는 다항식 [1]시간에 해결할 수 있다. |
| APX | 일정한 근사[1] 비율을 갖는 근사 알고리즘이 있는 최적화 문제 |
| 오전 | Arthur-Merlin[1] 프로토콜에 의해 다항 시간에 해결 가능 |
| BPP | 랜덤화 알고리즘으로 다항 시간 내에 해결 가능(정답이 맞을 수 있음) |
| BQP | 양자 컴퓨터에서 다항식 시간으로 해결 가능(정답이 맞을 수 있음) |
| co-N | "아니오" 답변은 비결정론적 기계에 의해 다항식 시간 내에 확인할 수 있습니다. |
| co-NP-완전 | co-NP에서 가장 어려운 문제 |
| DSPACE(f(n)) | 공간 O(f(n)를 가진 결정론적 기계에 의해 해결 가능. |
| DTIME(f(n)) | 시간 O(f(n)에서 결정론적 기계에 의해 해결됩니다. |
| E | 선형 지수로 지수 시간 내에 해결 가능 |
| 초등 | 지수 계층 내 클래스 결합 |
| ESPACE | 선형 지수를 가진 지수 공간으로 해결 가능 |
| EXP | EXPTIME과 동일 |
| 엑스페이스 | 지수 공간으로 해결 가능 |
| 제외 시간 | 지수 시간 내에 해결 가능 |
| FNP | 기능 문제에 대한 NP의 유사점 |
| FP | 기능 문제에 대한 P의 유사점 |
| FPNP | 기능 문제에 대한 P의 유사점NP; 출장 세일즈맨 문제의 본거지 |
| FPT | 고정 파라미터 추적 가능 |
| 갭L | 행렬의 정수 행렬식을 계산할 수 있는 로그 공간 축소 가능 |
| 아이피 | 대화형 증명 시스템에 의해 다항식 시간으로 해결 가능 |
| L | 로그 공간(작은)으로 해결 가능 |
| LOGCFL | 문맥이 없는 언어로 로그스페이스 축소 가능 |
| 엄마. | 멀린-아더 프로토콜로 다항 시간에 해결 가능 |
| 엔씨 | 병렬 컴퓨터에서 효율적으로(다중 연산 시간) 해결 가능 |
| NE | 비결정론적 기계에 의해 선형 지수를 사용하여 지수 시간 내에 해결 가능 |
| 네스페이스 | 선형 지수를 가진 지수 공간을 가진 비결정론적 기계에 의해 해결 가능 |
| NEXP | NEXPTIME과 동일 |
| 넥스페이스 | 지수 공간을 가진 비결정론적 기계에 의해 해결 가능 |
| 넥스트 타임 | 비결정론적 기계에 의해 지수 시간 내에 해결 가능 |
| NL | 로그 공백으로 확인할 수 있는 "YES" 답변 |
| 보조 없음 | ELEMENTY의 보완. |
| NP | "YES" 답변은 다항식 시간으로 확인할 수 있습니다(복잡도 클래스 P 및 NP 참조). |
| NP-완전 | NP에서 가장 어렵거나 가장 표현하기 쉬운 문제 |
| NP-쉽다 | 기능 문제의 경우 P의 아날로그NP, FP의 다른NP 이름 |
| NP 등가 | FP에서 가장NP 어려운 문제 |
| NP 하드 | 적어도 NP의 모든 문제만큼 어렵지만 같은 복잡도 클래스에 있는 것으로 알려져 있지 않다. |
| NSPACE(f(n)) | 공간 O(f(n)를 가진 비결정론적 기계에 의해 해결 가능. |
| NTIME(f(n)) | 시간 O(f(n)에서 비결정론적 기계에 의해 해결 가능. |
| P | 다항식 시간으로 해결 가능 |
| P-완전 | 병렬 컴퓨터에서 P에서 가장 해결하기 어려운 문제 |
| 폴리 | 입력 크기에 따라 "어드바이스 문자열"이 지정된 다항식 시간 내에 해결 가능 |
| PCP | 확률적으로 확인할 수 있는 증명 |
| PH | 다항식 계층 구조에서 클래스의 결합 |
| PNP. | NP의 문제에 대한 오라클을 사용하여 다항 시간 내에 해결 가능(δP라고도2 함) |
| PP | 확률론적 다항식(answer보다 약간 높은 확률로 정답) |
| 패드 | 유도 그래프의 다항식 패리티 인수 |
| 홍보 | 산술 함수를 재귀적으로 구축하여 해결할 수 있습니다. |
| PSPACE | 다항식 공간으로 해결 가능. |
| PSPACE-완전 | PSPACE에서 가장 어려운 문제. |
| PTAS | 다항식 시간 근사 체계(APX의 하위 클래스). |
| QIP | 양자 인터랙티브 증명 시스템에 의해 다항 시간 내에 해결 가능. |
| 품질 관리 | NP의 양자 아날로그. |
| R | 한정된 시간 내에 해결할 수 있습니다. |
| 재생 | 한정된 시간 내에 "YES"라고 대답할 수 있지만 "NO"라고 대답할 수 없는 문제가 발생할 수 있습니다. |
| RL | 랜덤화 알고리즘에 의한 로그공간으로 해결 가능 (응답 없음, YES는 확실히 옳음) |
| RP | 랜덤화 알고리즘으로 다항 시간 내에 해결 가능(NO 답변이 맞을 수 있으며 YES가 맞을 수 있음) |
| SL | 무방향 그래프에서 지정된 정점 사이에 경로가 존재하는지 여부를 판별할 수 있는 문제 로그 공간입니다.2004년 10월, 이 클래스는 사실상 L과 동등하다는 것이 판명되었습니다. |
| S2P | 다항식 시간에[2] 결정적으로 결정적으로 동시 이동이 있는 한 라운드 게임 |
| TFNP | 비결정론적 다항식 시간으로 해결할 수 있는 총 함수 문제.이 클래스의 문제는 모든 입력이 유효성을 효율적으로 확인할 수 있는 출력을 갖는 속성을 가지고 있으며 계산상의 과제는 유효한 출력을 찾는 것입니다. |
| 업. | 모호하지 않은 비결정적 폴리타임 함수. |
| ZPL | 랜덤화 알고리즘으로 해결 가능(항상 정답이 맞고 평균 공간 사용량은 로그) |
| ZPP | 랜덤화 알고리즘으로 해결 가능(항상 정답이 맞고 평균 실행 시간은 다항식임) |
레퍼런스
- ^ a b c Sanjeev Arora, Boaz Barak (2009), Computational Complexity: A Modern Approach, Cambridge University Press; 1 edition, ISBN 978-0-521-42426-4
- ^ "S2P: Second Level of the Symmetric Hierarchy". Stanford University Complexity Zoo. Archived from the original on 2012-10-14. Retrieved 2011-10-27.
외부 링크
- 복잡성 동물원 - 500개 이상의 복잡성 클래스와 그 속성 목록
