복잡도 종류 목록

이 문서는 계산 복잡도 이론에서 다루는 복잡도 종류 목록이다. 다른 계산·복잡도 관련 내용이 궁금하면 계산 가능성과 복잡도 관련 주제 목록을 보자.

복잡도 종류 가운데 원래 종류에 들어 있는 모든 언어의 보완()으로 이루어진 'co'짝이 있는 종류가 많다. 예를 들어 어떤 언어 L이 NP에 들어 있으면 L의 보완은 co-NP에 들어 있다. (이건 NP의 보완이 co-NP라는 뜻은 아니다. 둘 다에 들어 있는 언어도 있고, 어느 쪽에도 들어 있지 않은 언어도 있다.)

복잡도 종류에서 "가장 어려운 문제"는 같은 종류에 들어 있는 문제라면 모두 그 문제로 환산할 수 있는 문제를 말한다. 환산을 하는 문제 자체도 그 종류에 들어 있거나, 그 종류의 부분집합에 들어 있다.

목록에 없는 문제가 있다면, 짝을 찾아 보면 된다. 이를테면 co-UP가 궁금하면 UP를 본다.

외부 링크 
  복잡도 동물원(The Complexity Zoo) - 400개가 넘는 복잡도 종류와 그 성질을 모아놓은 곳