유신의 "내일의 소프트웨어"

소프트웨어는 피시(PC) 밖에 더 많다. 스마트폰에서, 연구실 시뮬레이션에서, 위험관리 시스템에서…, 소프트웨어가 사회를 움직인다. 그러나 정작 우리는 소프트웨어에 관해 얼마나 많은 이야기를 알고 있을까?

[연재] 해도 해도 끝이 없는 계산

(3) 소프트웨어가 도무지 해결하지 못하는 세 가지: 두 번째, P=NP?


00package » "산으로 혹은 바다로 떠나는 사람이라면 누구나 여행 전 날 자기도 모르는 사이에 매우 복잡한 수학 문제를 풀고 있다고 하면 믿으시겠습니까?" 한겨레 자료사진




금 있으면 여름 휴가철이 다가옵니다. 그런데 산으로 혹은 바다로 떠나는 사람이라면 누구나 여행 전 날 자기도 모르는 사이에 매우 복잡한 수학 문제를 풀고 있다고 하면 믿으시겠습니까? 다름이 아니라 여행가방을 꾸리는 문제입니다. 이른바 배낭 문제(Knapsack Problem)를 쉽게 설명하면 다음과 같습니다.

 

“휴가지에 가져갔으면 싶은 물건을 모두 꺼내고 봤더니 불행히도 여행 가방에 다 들어가지 않는다. 여행 가방에 넣을 수 있는 최대한의 부분집합은 무엇인가?”

 

여행 가방을 싸는 것은 좀 귀찮은 일일지는 몰라도 누구나 흔히 해치우는 일이기 때문에, 왜 새삼스럽게 수학 문제로 다뤄야 하는지 의아해할지 모르겠습니다. 한데 배낭 문제는 결코 쉽지 않은 문제일 뿐 아니라 100만 달러의 상금이 걸린 컴퓨터과학 최대의 난제입니다. 상금이 100만 달러나 걸릴 만큼 대단한 문제가 무엇인지 알아보기 전에 각자가 여행 가방을 싸는 데 어떤 방법을 이용하는지 잠깐 생각해 보세요. 수학적으로(?) 여행가방을 꾸리는 방법은 글 말미에 나옵니다.

 

 

'계산복잡도'

00dotline

산복잡도(Computational Complexity)는 계산이론에서 '주어진 문제가 얼마나 어려운지를 나타내는 방법'입니다. 우리가 일상적으로 생각하는 문제의 '난이도'는 누가 푸는지에 따라 달라질 수 있는 주관적인 개념입니다. 고등학생에게 그다지 어렵지 않은 수학 문제가 초등학생에게는 생경한 기호로 가득찬 암호문 같이 보일 수 있으니까요. 계산복잡도는 객관적인 난이도를 측정하기 위해, 해당 문제를 푸는 데 필요한 사칙연산 혹은 비교의 횟수가 몇 번인지를 나타냅니다. 예를 몇 가지 들어 볼까요? 다음의 문제를 풀기 위해 몇 번의 계산 혹은 비교를 해야 하는지 생각해봅시다.

 

서로 다른 무작위의 숫자가 적힌 100개의 공이 있다.

(1) 공에 적힌 숫자 중 가장 큰 숫자는 무엇인가?

(2) 공 100개에 적힌 숫자의 합은 무엇인가?

(3) 적힌 숫자의 합이 42인 공 2개가 있는가?

(4) 공 X개를 골라서 적힌 숫자의 합이 정확히 100이 되게 할 수 있는가?

 

1번 문제를 푸는 방법은 일단 공 1개를 무작위로 골라서 든 다음에 나머지 공 99개를 한 개씩 검사하면서 더 큰 숫자를 발견할 때마다 손에 든 공을 바꾸는 것입니다. 결국 99번의 비교를 해야 합니다. 2번 문제는 숫자 100개를 더하는 것이므로 역시 99번의 덧셈을 해야 합니다. 3번 문제는 어떤가요? 모든 경우의 수를 검사하기 위해서는(학교에서 배운 '조합' 개념을 되살려보세요) 100 × 99 / 2 쌍을 모두 만든 다음 더해 봐야 합니다. 한 쌍에 덧셈 한 번이므로 결국 100 × 99 / 2 번의 덧셈을 해야 합니다. 가장 곤란한 것은 4번 문제입니다. 가능한 경우의 수가 무려 2의 100승이기 때문입니다 (100개의 공 각각에 대해 우리가 고른 X개의 부분집합에 속하거나 속하지 않는 2가지 경우가 있으므로 2를 100번 곱해야 합니다). 결국 4번 문제를 풀기 위해서는 2의 100승가지 경우에 대해 합을 구해봐야 합니다.

 

공의 갯수가 더 늘어나면 어떻게 될까요? 계산이론에 따르면 우리가 푼 문제의 '크기'는 공의 갯수에 따라 결정됩니다(공이 많을수록 더 '큰' 문제). 그럼 임의의 숫자 N개의 공에 대해 위의 문제를 다시 풀어봅시다.1번과 2번 문제를 풀기 위해서는 N-1 번의 비교와 덧셈을 해야 합니다. 3번 문제를 풀기 위해서는 N × (N - 1) / 2 번의 덧셈이 필요합니다. 4번 문제는 2의 N승가지 경우에 대해 합을 구해봐야 합니다. 계산복잡도는 바로 이 일반화된 계산의 양, 다리 말해서 주어진 크기의 문제를 풀기 위해 필요한 계산의 양을 말합니다.

 

N으로 표시된 계산복잡도를 관찰하면 1, 2, 3번 문제와 4번 문제 사이의 중요한 차이가 드러납니다. 1, 2, 3번을 푸는 데 필요한 계산의 양은 문제 크기 N의 다항식으로 나타낼 수 있습니다(N - 1 혹은 N × (N - 1) / 2). 그런데 4번 문제를 푸는 데 필요한 계산의 양은, 2의 N승가지 경우 각각에 대해 한 번에서 99번 사이의 덧셈을 해야 하므로, 아무리 적어도 N의 지수식인 2의 N승보다 큽니다. 이 차이는 문제의 크기가 커지면 커질수록 무섭게 벌어집니다. 공의 갯수를 100개에서 1000개로 늘린다고 해볼까요? 1번과 2번 문제를 푸는 데 필요한 계산의 양은 대략 10배가 늘어납니다(계산복잡도가 N의 1차식이므로 N이 10배 늘어나면 계산량도 10배 늘어남). 3번 문제를 푸는 데 필요한 계산의 양은 대략 100배가 늘어납니다(계산복잡도가 N의 2차식이므로). 그런데 4번 문제를 푸는 데 필요한 계산량은 2의 10승, 즉 1024배가 늘어납니다. 문제의 크기가 커지면 커질수록 4번 문제의 복잡도는 엄청난 속도로 증가합니다.

 

흥미로운 것은 누군가 4번 문제에 대한 답을 제출했을 때, 답이 맞는지 틀린지 확인하는 데에는 많은 계산이 필요하지 않다는 것입니다. 누군가 공 24개를 답으로 제출할 경우, 덧셈을 23번 해보면 합이 100인지 아닌지 확인할 수 있습니다. 답을 찾는 데에는 엄청난 양의 계산이 필요하지만, 답을 확인하는 것은 쉬운 이런 문제들이 바로 컴퓨터과학과 수학을 오랫동안 괴롭히고 있는 계산이론 문제 P = NP?의 주제입니다.

 

 

P = NP인가?

00dotline

00NPproblem1, 2, 3번 문제와 같이 계산복잡도가 문제 크기의 다항식으로 표현되는 문제의 집합을 P라고 합니다. 반면에 4번 문제와 같이 답을 확인에 필요한 계산은 문제 크기의 다항식으로 표현할 수 있지만 답을 구하는 데 필요한 계산량이 다항식보다 더 빨리 증가하는 식으로 주어지는 문제의 집합을 NP라고 합니다. 이전 글에서 알아본 '종료 문제'가 근본적으로 결정이 불가능한 문제라면, NP에 해당하는 문제들은 푸는 방법은 알지만 해도 해도 계산이 끝나지 않기 때문에 무서운 문제들입니다. 4번 문제를 공 100개에 대해서 컴퓨터로 푼다고 가정해 볼까요? 2의 100승가지 경우의 수를 1초에 100만개씩 계산한다고 해도 대략 4 × 10의 16승년이 걸립니다. 지구의 역사 45억년을 530억 번 반복할 수 있는 그야말로 상상조차 힘든 영겁의 시간입니다. 정말 더 빨리 푸는 방법이 없는 걸까요?

 

앞서 말한 계산이론의 난제란 P = NP (즉, 두 개의 집합이 서로 같은 집합이며 NP인줄 알았던 문제를 P인 것처럼 해결하는 방법이 있으나 다만 아직 모를 뿐이다) 혹은 P ≠ NP (P는 NP의 부분집합이지만 NP는 P의 부분집합이 아니며, 따라서 절대 P로 해결할 수 없는 NP 문제가 존재한다) 어느 한 쪽이 옳다는 것을 증명하는 과제를 말합니다. 만약 P = NP가 참이라면 위의 4번 문제를 1, 2, 3번과 비슷한 정도의 계산만 가지고 풀 수 있다는 뜻입니다. 반면에 P ≠ NP라면 4번 문제를 쉽게 푸는 방법은 없다는 뜻입니다. 많은 이들이 P ≠ NP가 참이라고 추측하고 있지만[1], 아직까지 어느 쪽도 정식으로 증명되지 않았습니다. 지난 2010년 휴렛패커드(Hewlett Packard) 연구소의 비나이 데오랄리카(Vinay Deolalikar, 위 인물사진)가 증명을 완료했다고 발표했지만, 얼마 지나지 않아 전문가들이 치명적인 오류로 보이는 부분을 지적해내고 말았습니다.

 

 

NP문제와 우리 생활

00dotline

리가 일상에서 쉽게 접할 수 있는 다양한 문제들이 NP에 속하는 것으로 밝혀져 있습니다. 앞서 예로 든 여행 가방 꾸리기, 즉 배낭 문제로 되돌아가볼까요? N개의 물품이 있을 때 가능한 모든 경우는 역시 2의 N승이므로 답을 구하는 데 필요한 계산량은 지수적으로 증가합니다. 하지만 일단 물품을 몇 가지 선택한 뒤 배낭에 들어가는지 확인하는 데에는 최대 N - 1 번의 계산이 필요합니다 (여기서 계산이라 함은 물품의 부피를 더하는 것인데, 실제로는 배낭에 넣어보는 행동이라고 하겠습니다). 따라서 배낭 문제는 NP에 속합니다. 그 밖에도 다음과 같은 문제가 NP에 속합니다:

 

  • 주어진 도시를 모두 방문하는데 필요한 최소한의 직선거리 구하기: 전력망, 수도 등의 사회기반시설의 계획과 연관이 있습니다
  • 한정된 강의실에 주어진 양의 수업을 모두 배정하는 시간표 짜기: 대규모 시간표 작성은 생각보다 수학적으로 매우 복잡한 문제입니다.
  • 한정된 예산으로 통화 가능 면적이 가장 넓어지도록 휴대폰 신호탑 건설하기: 건설 후보지가 N곳일 경우 가능한 경우의 수는 역시 2의 N승입니다.

 

만에 하나 P = NP라는 증명이 완료되면 여러 가지 문제를 손쉽게 풀 수 있게 돼서 좋은 일일까요? 불행히도 꼭 그렇지많은 않습니다. 일단은 구축에 의한 증명(constructive proof)이 가능하다는 보장이 없습니다. 구축에 의한 증명이란 증명하고자 하는 속성을 가진 예를 직접 만들어 보임으로써 증명한다는 뜻입니다[2]. P = NP가 구축에 의한 증명을 통해 참으로 밝혀진다면 NP 문제를 쉽게(즉 다항식 복잡도로) 푸는 방법이 알려지는 셈이겠습니다. 하지만 단순히 존재증명, 그러니까 “정확히 어떤 방법인지는 모르지만 NP 문제를 다항식 복잡도로 푸는 방법이 있는 것은 틀림없다”는 증명이 이루어질 경우, 실용적인 계산에서 직접적인 혜택은 제한적일 것입니다 (물론 존재증명 자체의 이론적 성취는 이루 말할 수 없는 것이겠지만).

 

여기서 잠깐, 구축에 의한 증명이 이루어진다고 해도 꼭 좋은 일이냐면 그렇지도 않습니다. 예를 들어 보안과 관련된 암호화 기술은 거의 대부분 특정한 계산의 복잡도가 매우 높다는 사실에 의존하고 있습니다. P = NP가 증명되고 NP문제의 복잡도 장벽이 사라지는 날엔 우리가 사용하는 거의 모든 암호화 기술이 무용지물이 되서 보안체계에 큰 혼선이 올 것입니다.

 

 

여행가방을 수학적으로 꾸리는 방법

00dotline

행 가방 꾸리기가 이렇게 힘든 일이라면 다들 여름 휴가는 어떻게 가는 걸까요? 다행히 많은 NP 문제에 대해, 최적의 답은 아니지만 최적값에 매우 가까운 답을 구하는 여러 가지 해결방법이 개발되어 있습니다. 배낭 문제의 답에 대한 근사값을 구하는 방법은 조금 짖궃게도 욕심쟁이 해결방법 (greedy heuristic)이라고 불립니다. 욕심쟁이 해결방법은 다음에 넣을 물품을 고를 때마다 가격(즉 부피, 배낭 공간을 얼마나 차지할 것인지) 대 성능(해당 물품이 여행에 얼마나 필요한지)에 따라서 욕심쟁이가 되는 것입니다 (여기서 욕심쟁이란 매 순간 가장 좋아보이는 선택을 한다는 뜻입니다). 가격(부피)대 성능비가 가장 높은 물건부터 차례로 더 이상 배낭에 아무 것도 넣을 수 없을 때까지 집어 넣으면 배낭 전체의 가격대 성능비가 최적값에 꽤 가까워집니다. 여행가방 꾸릴 때 꼭 필요한 물건인지 잘 생각해보고 정말 필요한 것 같지 않으면 과감하게 남겨두라는 여행 전문가들의 조언은 여행 물품의 가격(부피)대 성능비를 꼼꼼히 따지라는 뜻에 다름아닙니다.

 

지금까지 애초에 푸는 것이 불가능한 문제(종료문제)와 푸는 것이 너무 힘든 문제(NP)를 알아봤습니다. 다음 번엔 마지막으로 정답이 뭔지 결정하는 것 자체라 너무 어려운 문제, 인공지능의 가능성에 대해 알아보겠습니다.

 

 

00dotline

[1] 2002년에 전문가 100명을 대상으로 한 설문조사에서 61명이 P ≠ NP라고 생각한다고 답했습니다.

[2] 계산복잡도 이론을 조금 더 파고 들어가면 NP-완전(NP complete) 문제를 만날 수 있습니다. NP-완전 문제는 그 계산복잡도가 NP에 속하는 다른 문제 어느 것과 비교해도 같거나 더 높은 문제들입니다. 그야말로 알쏭달쏭한 고등수학의 세계이지만, NP-완전 문제가 뜻하는 바는 다음과 같습니다: 만약 NP-완전 문제를 다항식 복잡도(P)로 풀 수 있다면, NP에 속하는 다른 어떤 문제도 다항식 복잡도로 풀 수 있게 됩니다. 따라서 지금까지 알려진 NP-완전 문제 중 어느 것 하나라도 다항식 복잡도로 푸는 방법을 찾는다면 그것이 바로 구축에 의한 증명이 됩니다.

  • 구글
  • 카카오
  • 싸이월드 공감
  • 인쇄
  • 메일
유신 카이스트 교수, 전산학
소프트웨어 테스팅 연구로 박사학위를 받은 소프트웨어공학 연구자다. 진화 알고리즘과 인공지능 기술, 정보이론 등을 소프트웨어 공학 문제에 접목하는 데에 관심이 많다. 전 영국 런던 유니버시티칼리지 조교수, 현 카이스트 전산학부 조교수
이메일 : shin.yoo@kaist.ac.kr       트위터 : @ntrolls      
블로그 : londonforgeeks.tumblr.com

최신글




최근기사 목록

  • 검증불가능 프로그램, 어떻게 검증할 것인가?검증불가능 프로그램, 어떻게 검증할 것인가?

    내일의 소프트웨어유신 | 2013. 06. 28

    [6] ‘고차변형 테스팅’ 방법3차원으로 초신성의 핵을 시각화하는 컴퓨터 시뮬레이션. 이제는 천체물리학은 물론 과학 여러 분야의 연구 상당 부분이 컴퓨터 내부에서 벌어진다. 그런데 이 시뮬레이션 프로그램에는 과연 오류가 없을까? 초신성의 ...

  • “오류 존재를 보여도 오류 없음을 보일 순 없다”“오류 존재를 보여도 오류 없음을 보일 순 없다”

    내일의 소프트웨어유신 | 2013. 05. 24

    [5] 소프트웨어 테스팅과 ‘부족한 근사값’ 잠깐, 자신이 프로그래머라고 상상해 봅시다. 방금 회사의 다음 프로젝트 중 일부로 사용할 중요한 프로그램 하나를 작성했습니다. 상사에게 이 프로그램을 넘기기 전에 자신이 작성한 프로그램이 ‘제대로...

  • 강한 인공지능, 약한 인공지능강한 인공지능, 약한 인공지능

    내일의 소프트웨어유신 | 2012. 08. 14

    (4) 인공지능이란 대체 뭔가? 얼마 전 개봉한 영화 <프로메테우스(Prometheus)>에서 외계 생명체만큼이나 사람들의 관심을 끈 것은 인공지능 로봇 데이빗이었습니다. 뛰어난 계산 능력과 무한에 가까운 기억력을 지녔지만 감정을 느끼지 못하기 때...

  • [연재] 완벽한 백신SW 불가능한 이유, 튜링은 알고 있다[연재] 완벽한 백신SW 불가능한 이유, 튜링은 알고 있다

    내일의 소프트웨어유신 | 2012. 05. 22

    (2) 소프트웨어가 도무지 해결하지 못하는 세 가지: 첫 번째 '종료 문제' 지난해 과학계를 뜨겁게 달군 과학 뉴스 중 하나는 바로 중성미자 입자의 속력이 빛보다 더 빠르다는 어느 관측실험 결과였습니다. 이에 많은 사람들이 놀라움과 의구심을 나...

  • [새연재] PC 파란화면에 무오류 수학의 이상은 흩어지고[새연재] PC 파란화면에 무오류 수학의 이상은 흩어지고

    내일의 소프트웨어유신 | 2012. 04. 17

    (1) 연재를 시작하며 소프트웨어공학(Software Engineering)이라는 이름을 들으면 무엇이 연상되나요? 아마 대부분의 사람들이 “정보기술(IT) 강국” 혹은 “정보화시대” 등을 떠올리리라 생각합니다. 혹 주변에 IT업계에 종사하는 지인이 있는 경우...