-
#P-완전성, 그리고 완전 매칭의 개수
이 글은 튜링 기계와 NP-complete에 대한 기본 배경지식을 전제로 합니다. 서론 이분 그래프가 주어졌을 때 최대 매칭을 구하는 문제는 알고리즘 문제 풀이에서 잘 알려져 있습니다. 심지어 일반적인 그래프가 주어져도 최대 매칭을 다항 시간에 구할 수 있습니다. 그러므로 완전 매칭이 존재하는지도 같은 방법으로 구할 수 있습니다. 하지만 완전 매칭의 개수를 구하라고 하면 어떻게 될까요? 카운팅 문제와 #P-완전 NP-완전성을 이야기할 때는 문제가 결정 문제로 한정됩니다. 예를 들어 최대 클릭 문제는 “가장 큰 클릭은 무엇인가?”가 아니라 “크기가 $k$...
-
계산 복잡도 위계와 불리언 식
계산 복잡도 위계와 불리언 식 계산 이론은 전산학의 근간을 이루며, 컴퓨터를 사용하는 모든 학문의 수학적 분석에 있어서 중요한 역할을 한다. 계산 이론 분야의 $P = NP$ 난제는 컴퓨터 과학의 거의 모든 분야를 관통하는 중요한 문제이고. $P = NP$ 난제의 여러 중요한 실용적 의미와 그 악명높음은 이미 대중적으로도 잘 알려져 있다. 계산 이론의 내용은 전산학의 어떠한 부분을 다루더라도 만나게 되는 경우가 많지만, 대부분의 내용은 튜링 머신과 같은 복잡한 개념을 바탕으로 정의된다. 이러한 특징 때문에, 계산 이론의...