Analysis of Algorithms | NP-Completeness

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다. 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

모든 계산 문제는 컴퓨터로 해결가능한가?

컴퓨터의 등장으로 매우 빠른 연산력을 앞세워 다양한 문제들을 해결할 수 있었다. 그와 함께 모든 계산적 문제들은 컴퓨터로 해결가능한가에 대한 의문점이 제기되었다. 컴퓨터로 해결할 수 없는 대표적 문제를 예로 들자면 정지 문제(Halitng Problem)가 있다.

튜링 정지 문제(Turing Halting Problem)

정지 문제를 요약하면 주어진 프로그램이 해결하고자 하는 문제가 해결되었는지 미리 정답을 말해줄 수 있는 알고리즘이 존재하는가에 대한 문제이다.

증명

정지 문제에 대한 엄밀한 증명은 다루지 않고 대략적인 증명법만을 다루려고 한다. 간단한 증명은 귀류법으로 증명가능한데, 해결할 수 있다는 가정에서 출발하여 가정에 모순이 발생할 수밖에 없음을 보임으로써 증명해야 한다.

임의의 알고리즘 a와 input i를 인자로 받는 함수 halt(a, i)가 존재한다고 하자. 그리고 halt(a, i)는 알고리즘 a에 input i를 입력했을 경우 해결이 된다면 참, 그렇지 않고 반환되지 않는다면 거짓을 출력한다. 이제 이 halt 함수에 대해 존재가능성을 증명하기 위해 halt 함수가 하는 작업을 모순되게 하는 프로그램을 하나 작성한다.

func problem(p){ #인자로 루틴 p를 받으면 복사하여 halt 함수에 입력한다
    if halt(p,p)==false: #만약 p를 입력받은 p가 무한루프에 빠지면
        return true #루한루프에 빠지지 않는다고 출력
    else: #만약 p가 무한루프에 빠지지 않는다면
        loop infinite #무한루프에 빠짐
}

이제 위 문제에 대해 halt(p,p)는 어떤 값을 갖는지 확인하자.

• 만약 halt(p,p)가 참이라면 problem(p)는 정상적으로 종료되어야 한다. 하지만 내부 로직에 따라 halt(p,p)가 참일 경우 무한루프에 빠진다고 정의하였으므로 전제에 모순된다.
• 만약 halt(p,p)가 거짓이라면 problem(p)는 무한루프에 빠져야 한다. 그러나 로직에 따라 halt(p,p)가 거짓이라면 problem(p)는 무한루프에 빠지지 않으므로 전제에 모순된다.

따라서, halt(p,p)가 참이든 거짓이든 모순을 가지므로 halt함수는 존재할 수가 없다는 결론을 도출할 수 있다. 그러므로 halt함수에 대한 정의인 정지 문제를 해결할 알고리즘이 존재한다는 전제가 거짓이므로 정지 문제를 해결할 알고리즘은 존재하지 않는다는 결론을 얻을 수 있다. 정지 문제는 유한 번의 연산으로 판정이 불가능한 문제이므로 NP에 속하지 않는다.

위 문제를 통해 계산적 문제라도 컴퓨터로 해결할 수 없는 경우가 존재한다는 점을 확인할 수 있다.

P-NP 문제

이전 포스팅까지 다양한 시간복잡도와 관련된 개념을 돌아보면서 알고리즘의 해결시간이 다항시간으로 정의되는 경우를 다뤘다. 크게 계산적 문제들에 대한 난이도를 말할 때 P-NP에 대한 개념을 사용한다. 우리가 봤던 문제들을 흔히 P 문제(Polynomial problem)이라 하고 이제 다른 유형인 NP 문제(Non-deterministic Polynomial Problem)가 있다. 각 유형에 대해 도식화를 한다면 아래 그림과 같이 표현할 수 있다.

• P 문제 (Polynomial Problem) : 결정론적 튜링기계로 다항시간 내에 해결할 수 있는 문제
• NP 문제 (Non-deterministic Polynomial Problem) : 비 결정론적 튜링기계로 다항시간 내에 해결할 수 있는 문제

결정론적-비결정론적 튜링 기계

튜링 기계(Turing machine)란 간단하게 정해진 명령에 따라 원하는 작업을 수행하는 가상의 기계를 의미한다.

결정론적 튜링 기계는 위의 정의에 따라 정해진 명령표대로 정확하게 원하는 작업을 수행하는 튜링 기계이다. 그리고 해당 기계에 대한 정의와 함께 P 문제는 이 튜링 머신이 다항 시간 내에 해결할 수 있는 문제를 말한다.

비결정론적 튜링 기계는 튜링 기계가 작동할 때 결정론적 튜링 기계와는 달리 특정 상태에서 움직일 수 있는 상태가 정해져 있지 않은 튜링 기계이다. 단적으로 새로 정의하자면 특정 입력 값이 주어진 문제에 대해 정답 여부를 판별하는 기계로 이해할 수 있다.

요약하자면 결정론적 튜링 기계로 다항 시간 내에 해결할 수 있는 문제를 P문제라 부른다. 결결정론적 튜링 기계로 다항 시간 내에 해결할 수 없는 문제, 비결정론 튜링 기계로 다항시간 내에 주어진 특정 입력 값이 정답인지 아닌지 판별하는 데 다항시간이 걸리는 문제를 NP문제라고 한다.

두 문제의 유형에 대해 완전히 나뉜 개념으로 오해할 수 있는데 비결정론적 튜링기계로 P 문제 또한 다항기간 내에 해결할 수 있으므로 P 문제는 NP 문제의 부분집합이다. 추가로 설명하자면 결정론적 튜링 기계도 비결정론적 튜링 기계이 개념에 대입하면 비결정의 정도가 1이기 때문이다.

NP-hard(NP-난해) 문제

NP-hard 문제는 NP 집합에 속한 모든 문제를 다항 시간 내에 환원시킬 수 있는 문제이다. 그러므로 NP-hard 문제는 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이다.

환원(reduction)

환원(reduction)은 알고리즘에서 문제의 난이도를 다룰 때 사용되는 개념이다. 간단하게 곱셈에 대한 문제와 덧셈에 대한 문제가 있을 때, 곱셉은 곱하는 수만큼 덧셈을 반복하는 과정일 뿐이므로 덧셈을 할 수 있다면 곱셉 문제를 해결할 수 있다. 이 경우 덧셈 문제를 곱셈 문제보다 어렵다고 정의한다. 따라서, 정의에 따라 NP-hard 문제는 모든 NP문제보다 난이도가 어렵다고 말할 수 있다.

위 과정을 도식화 하면 아래 그림과 같다. 두 결정 문제 $L_1,\ L_2$가 존재하고 각 문제에 대한 정답을 도출하는 알고리즘을 $A_1,\ A_2$ 하자. $L_1$의 input 값인 x를 $A_1$에 넣었을 때 일정 환원과정을 거쳐 $L_2$의 input 값인 y로 변환된다면, 해당 값을 $A_2$에 입력하여 결과를 얻을 수 있고 결국 x에 대한 $L_1$의 답이 된다. 그러므로, $A_2$또한 $L_1$을 해결하기 위한 $A_1$의 일부가 됨을 확인함으로써 $L_1$이 $L_2$로 환원가능하다는 결론을 내릴 수 있다.

환원 과정을 찾는다는 것은 중요한 의미를 갖는다. 어떠한 복잡한 문제가 주어졌을 때 이미 알고있는 문제의 반복 과정으로 해결할 수 있다는 점을 알 수 있다면 완전히 새로운 코드를 작성하는 것보다 응용된 코드를 작성하는 것이 시간 절약에서 유리하기 때문이다.

NP-complete(NP-완전) 문제

NP 집합에 속하는 결정 문제 중 가장 어려운 문제들에 대한 부분집합으로 모든 NP문제는 다항 시간 내에 NP-complete 문제로 환원할 수 있다. 만약 해당 부분집합의 문제 중 단 한개라도 P 집합에 속함을 증명한다면 P=NP를 증명하는 것이 되지만 단 하나라도 속하지 않음이 증명되면 P=NP에 대한 반례이므로 여전히 P!=NP이게 된다.

참고사항 : co-NP 문제

NP 문제의 coplement(보완)를 co-NP문제라고 한다. 예를 들어 소수 판정 문제의 경우 주어진 input이 소수인가에 대해 소수가 아니라고 판정하는 문제가 NP라면 주어진 값이 소수가 맞다고 판정하는 문제가 co-NP가 되는 것이다. 어떤 명제의 역이 서로 동치가 아닐 수도 있듯이 NP 문제와 co-NP 문제는 서로 동일한 집합이 아니다.

NP와 co-NP가 동일 집합이 아닌 이유

co-NP 집합에 속하는 NP-complete 문제가 있을 때, 모든 NP문제는 NP-complete로 환원 가능하므로 모든 NP 문제의 co-NP 문제를 다항 시간에 해법을 도출할 수 있는 비결정론적 튜링 기계를 만들 수 있다. 따라서, NP가 co-NP의 부분집합이 되고 NP 문제의 보완 문제(co-NP)에 대한 집합이 co-NP 문제의 보완 문제(NP)의 부분집합이 되어 NP=co-NP가 된다. 그런데 co-NP는 NP와 보완 관계이므로 같을 수가 없어 모순이다.

참고자료

1. NP-Completeness | Set 1 (Introduction)
2. Proof That Computers Can't Do Everything (The Halting Problem)
3. wikipedia_co-NP
4. P, NP문제와 co-NP, NP-난해(NP-Hard), NP-완전(NP-complete) 개념 정리