서론
P와 NP를 처음 마주하는 전공생들은 대부분 어질어질함을 느낄 것이다. 이곳 저곳 찾아봐도 이해할 수 없는 이야기들, 뭔가 추상적이고 뭔가 이치에 맞지 않는 듯한 느낌 혹은 내가 그 단어를 이해할 수 없어서 무슨 말을 하고자 하는 것인지 모르는 느낌. 나도 그런 느낌을 겪어 본 터라, 이 글을 통해 P와 NP의 정의와 NP-Hard, 그리고 Np-Complete가 무엇인지 알아보고자 한다.
아마 CS를 전공하거나, 알고리즘을 조금 공부해봤다 싶으면 P와 NP라는 단어를 한 번 즈음 들어봤을 것이다. 처음 직관적으로 들어보면, P와 NP는 서로 대척되는 개념이라 생각하기 쉽다. 왠지 Non-P일 것 같은 느낌이 강하게 들기 때문이다. 어쩌면 P와 NP를 이해하기 힘든 순간은 처음의 이 첫인상에서 시작되는 것일지도 모른다.
주의! 필자는 학부 수준의 지식만 보유하고 있다. 정의에 완벽히 부합하지 않을 가능성이 다소 존재한다.
NP문제
본론으로 들어가서, NP문제란 비결정론적 튜링 머신에서 답이 다항 시간 내에 구해질 수 있는 문제다. 여기서 CS지식이 부족하거나, 혹은 관련 된 지식을 습득하지 못한 전공자들은 해당 정의를 이해하기가 어렵다. 지극히 당연한 일이다. 1차 전직을 안 했는데, 2차 전직을 하려고 하는 거랑 비슷한 경우니까. 허나, 우리가 NP문제의 정의를 이해하기 위해서 굳이 오토마타의 영역에 발을 들이 밀 필요도 없다. 그저 우리가 필요한 건 ‘비결정론적’ 그리고 ‘튜링 머신’에 대한 지식이니까.
튜링 머신
튜링 머신의 시초는 위키백과에 잘 나와 있다. 그것도 틀리지 않은 원석과 같은 정보들로. 거기 적혀 있는 말들은 대부분 옳다. 하지만 읽어도 아리송할 수 있다. 마치 미슐랭 가이드에 오른 음식점을 방문해도, 집 앞 70년 할매 돼지국밥을 먹었을 때보다 덜 만족스러운 경우가 있을 수 있는 것처럼, 너무 고급진 말들이나 전문적인 어휘는 알지 못하는 계단 아래의 사람에겐 다소 어려울 수 있는 것이다.
거두절미하고, 쉽게 풀어서 쓰자면 주어진 ‘상태’와 ‘입력’아 있을 때 어떤 ‘결과’를 도출해내는 기계가 바로 튜링 머신이다. 여기서 ‘상태’에는 여러 정보가 들어갈 수 있는데, 우리가 예를 들어 C++로 swap(a,b)라는 함수를 작성했다고 했을 때, a와 b의 값(입력)도 상태가 될 수 있고, 현재 컴퓨터가 읽은 어셈블리어의 프로그램 카운터도 상태가 될 수 있다. 어떠한 기계가 작동할 때 주어진 모든 상황 그리고 입력을 모두 고려했을 때 해당 기계는 어떤 ‘결과’를 도출해낼 것이다.
예를 들어, 민수가 아침에 학교를 갔을 때 반에 친구가 몇 명이 먼저 와 있는지에 따라 민수의 행동이 달라질 수 있을 것이다. 여기서 상태는 ‘학교를 막 등교한 상태’ 그리고 입력값은 ‘친구의 수’일 수 있는 거다. 여기서 민수의 행동을 판단하는 기계를 우리가 개발했다. 영화 테이프를 가져와서, 민수가 학교를 등교한 상황과 안에 들어 있는 사람 수를 인식시켜, 민수의 행동을 도출시키도록 말이다. 여기서 우리가 만들어낸 기계가 바로 ‘튜링 머신’이라는 것이다.
비결정론적?
앞서 민수의 행동을 예측하는 튜링 머신을 만들었다. 여기서 우리는 ‘영화 테이프’니 ‘테이프를 인식하는 기계’니 하는 것들을 전부 없애고 그냥 개념만을 가져와서 생각해보자.
그냥 까놓고 말해서, 우리는 주어진 상태에 따라 어떤 결과를 내는 기계를 만들었다. 생각해보면, 이건 우리가 언제나 작성하는 알고리즘과 똑같다. 튜링머신이 계속되서 회자되는 이유는 그 영화 테이프로 알고리즘을 재현해낼 수 있기 때문이다. 결국 우리의 논점은 ‘알고리즘’이라는 거다.
비결정론적 튜링 머신은 같은 입력, 같은 상황에서도 다른 값을 뱉어내는 기계다. 예를 들어 프로그램을 다 작성하고, 패러미터를 넘겨 주었는데, 프로그램의 블랙박스에 랜덤함수가 들어가서 값이 넣을 때마다 다르게 나온다. 즉 우리가 넣어준 상태가 아무리 같아도 결과가 늘 정해져 있지 않다. 결정되어 있지 않다.
같은 상태에서도 같은 입력에서도 다른 결과가 도출 될 수 있다는 것, 결국 그것이 ‘비결정론적’의 핵심적인 의미이다.
비결정론적 튜링머신
즉 같은 상태, 같은 입력이어도, 같은 결과를 도출하지 않는 기계를 말한다.
그래서 NP가 뭔데?
결론적으로 말하자면, 비결정론적 튜링머신을 사용하면 다항시간 내에 풀 수 있는 문제라는 것이다.
여기 임의 문자열 생성기가 존재한다. 이 생성기는 임의로 아무 문자열을 뱉어낸다. 뱉어내는 것은 지극히 랜덤이며, 난수를 통해 제작되기 때문에 문자열의 길이 n에 대하여 O(n)의 시간복잡도가 소요된다. 기원이의 메이플 아이디가 너무 가지고 싶었던 덕휘는 이 ‘랜덤 문자열 생성기’를 사용하기로 마음 먹었다. 어쩌면, 정말 낮은 확률로 이 기계는 기원이의 메이플 아이디의 비밀번호를 알려줄 것이다.
여기서 우리가 기원이의 메이플 비밀번호가 맞는지 아닌지를 판별하는 방법은 간단하다. 그저 로그인 해보면 된다. 그러면 O(n)의 시간에 비밀번호를 판독할 것이다. 여기서 우리는 ‘비밀번호 맞추기’라는 문제에 대해서 비결정론적 튜링 머신을 통해 O(n)의 시간, 즉 다항 시간 내에 해당 문제를 풀어냈다.
‘비밀번호 맞추기 문제’는 결국 ‘비결정론적 튜링 머신’을 사용하면 다항 시간 내에 풀리는 문제라는 것이다. 우리는 이렇게 비결정론적 알고리즘에 의해 다항 시간 내에 풀 수 있는 문제들을 NP문제라고 부른다.
한 줄 요약
랜덤하게 아무 값을 가져다가 해당 문제가 옳음을 증명할 가능성이 다항 시간 내에 존재한다면 NP문제다.
P 문제
NP문제를 이해했다면, P문제를 이해하기는 쉽다. 다항 시간 내에 풀 수 있는 문제들이 바로 P문제다. 답이 주어졌을 때 해당 답이 옳은지 아닌지를 판별할 수 있는 문제가 NP문제라고 했는으니, 왜 P문제가 NP문제의 부분집합인지 쉽게 알 수 있다.
다항 시간 내에 풀 수 있다는 말은 당연히도, 주어진 답이 다항 시간 내에 옳은지 판별되었다는 의미이니 말이다.
NP-난해
NP-난해는 모든 NP 판정 문제들을 다항 시간 내에 환산할 수 있는 문제들의 집합이다. 잘 이해가 안 갈 것이다. 지극히 당연한 일이다. 저 말만 읽고 아 이게 NP-hard구나~ 하며 이해할 수 있는 사람이 있을까.
우리는 조금 더 쉽게 이해하기 위하여 NP-HARD라는 네이밍에 대해 생각해보도록 하자. 어렵다는 것은 무엇일까? 옹알이 하는 것보단 똑바로 말하는 것이 더 어렵다. 50미터를 10초에 뛰는 것보다 8초에 뛰는 것이 더 어렵다. 그렇다면 이렇게 생각해보자. 50m를 7초에 뛰는 사람은 10초에 뛸 수도 있을 것이다. 똑바로 말하는 성인이 애기처럼 옹알이를 따라할 수도 있다.
여기서 앞서 말했던 환산한다는 개념을 이해할 수 있다. 이미 더 어려운 것을 해낸다면 그 아래의 것들은 이미 풀린 것처럼 말이다. 이 환원의 개념에 대해 제일 이해하기 쉬운 예시가 있다.
1
2
3
4
주어진 N개의 숫자에 대하여,
1. 3번째로 큰 수를 구해라.
2. 가장 큰 차이가 나는 두 쌍을 구해라.
3. 정렬해라.
1번과 2번 문제의 경우 3번 문제에 비해 쉽다. 왜냐하면, 3번을 해낸 사람은 1번과 2번을 쉽게 풀 수 있을테니, 말이다. 이것과 같이 모든 NP 판정 문제가 다대일로 매핑 되는, 모든 NP문제보다 어려운 문제들을 NP-HARD라 부른다.
further..
사실 이렇게 말해도, 여전히 이해가지 않을 수 있다. 상당히 야만적인 표현을 가져와 말하자면, NP-HARD문제들이란 아직 다항 시간 내에 풀 수 있는 방법을 모르며, 동시에 모든 NP문제보다 어려운 녀석들이라 생각해면 될 것이다.
NP-완전
NP이면서 동시에 NP-HARD인 문제들을 NP-완전이라 부른다. 즉 비결정론적 알고리즘으로 다항시간 내에 풀 수 있지만, 다항 시간 내에 풀 수 있는지는 아직 여부가 밝혀지지 않았고, 동시에 모든 NP문제보다 어려운 문제들이다. 가장 흔한 예시로는 subset sum problem이 있다.
1
2
3
# subset sum problem
[1,2,3,4,5,6]
Q. 주어진 배열에서 합이 6인 부분 집합이 존재하는지 판별하라
배열의 원소 개수 n에 대하여 O(2^n)이라는 시간 복잡도를 보이지만, 답이 맞는지 아닌지 판별하는 것은 다항시간 내에 가능한 문제다.