P Vs. NP

언젠가 포큐 아카데미를 보고 정리를 해둔 내용이다. 물론 삶에 의미가 있을까 싶어서 지우려했다.

근데 또 이런 주제가 재밌어서 이쪽 카테고리로 옮겨보았다.
양자 컴퓨터와도 관련이 있지 않나 싶어서, 한 때 열 올리고 이해해보고자 했던 주제.. 지금은.. 긁적..

---

1. P? Polynomial Time?

  1.1 다항식 시간

    Note) 브루트 포스 알고리듬이란게 있다.

      모든 가능한 경우의 수를 시도하는 알고리듬.

      그래서 최소 O(N) 시간 복잡도를 가진다.

 

    Note) 예로 들어, 완전 탐색이 대표적이다.

      배열에서 어떤 값의 색인 찾기.

      배열에서 최대 값 찾기.

      배열에 들어있는 정수들의 합 또는 평균 구하기

 

    Note) 이런 애들은 다항식 시간안에 풀 수 있다.

      이런 경우를 Deterministic Polynomial Time이라 함.

 

  1.2 지수 시간

    Note) 반면에, 비밀번호 깨기를 살펴보자.

      비밀번호 규칙에 맞는 새로운 비밀번호를 만들고,

      위 비밀번호가 올바른 비밀번호인지 시도해 본다.

      틀리면 다시 시도해보고 맞을때까지 해본다.

      브루트 포스 알고리듬이라면, 최대 몇 번을 시도해야할까?

 

    Note) 비밀번호 자릿수가 N이고,

      각 자리에 들어갈 수 있는 문자 수가 K라면

      O(K^N)이 되어버림. 

      게다가 K는 상식적으로 100자 정도.

      N은 뭐 무한하게 늘릴 수 있음.

      기하급수적인 증가(Exponential Growth)

 

    Note) 외판원 문제(Traveling Salesman Problem)

      줄여서 TSP라고도 부름.

      여러 도시를 방문해야 하는 외판원이 있다.

      각 도시를 최소 한 번씩 방문 해야만 함.

      가장 짧은 거리를 이동해서 완료해야한다고 해보자.

      운전이기 때문에 연료비를 아끼기 위함임.

      한 도시에서 시작해서 모든 도시를 방문 하고

      다시 원래 도시로 돌아와야 함.

 

    Note) 브루트 포스 알고리듬와 TSP

      1. 시작할 도시를 선택

      2. 모든 방문 순서 목록을 만듦.(모든 경우의 수)

      3. 각 목록의 총 이동거리를 계산.

      4. 그 결과 중 총 이동거리가 짧은 목록을 선택.

      즉, 시간 복잡도는 O(N!)

      마찬가지로 기하급수적 증가(Exponetial Growth)

 

    Note) 기하급수적 증가 알고리듬의 문제점

      N이 커질수록 문제를 푸는 속도가 매우 느려짐.

      즉, 실무에서 사용하기 어려운 경우가 많음.

      ex. 무한루프는 아닌데, 몇 분안에 결과가 안나오는 코드.

      지수 시간 알고리듬은 실무에 적용 불가능한 경우가 매우 많음.

      그래서 다항식 시간 알고리듬(Polynomial Time Algorithm)을 선호

 

    Note) 결론적으로, 어떤 문제 해결에 걸리는 시간이

      다항식 시간이라면 P 문제라고 분류함.

 

 

아래는 정리 안됨 ^^;;;;

 

---

 

2.3 P, NP, NP-완전

 

2.3-0 P Vs. NP 문제

  - 아직까지 풀리지 않은 미해결 수학 난제 7개 중 하나

 

 

2.3-1 P 분류(P Class)

  - 판정 문제들을 분류하는 방법 중 하나

    판정 문제: 입력 값에 대해 예/아니오 답을 내릴 수 있는 문제.

 

  - 결정론적 튜링 기계에서 다항식 시간 안에 풀 수 있는

    모든 문제를 포함

 

 

2.3-2 결정론적 튜링 기계

  - 튜링 기계: 무언가를 계산하는 기계를 대표하는 가상의 장치

                  일반적인 컴퓨터 알고리듬을 수행할 수 있음.

 

  - 결정론적 튜링 기계란

    어떤 명령어 실행 뒤, 다음 실행할 명령어가 확정됨.

    코어 하나에서 명령어를 순서대로 실행하는 거라고 생각하자.

    즉, 코어 하나에서 실행되는 다항식 시간 알고리듬이

    있는 문제는 P Class.

 

 

2.3-3 NP 분류(NP Class)

  - NP: 비결정적 다항식 시간(Nondeterministic Polynomial Time)

    Not P가 아님. 이에 매우 주의하길.

 

 

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

  - 어떤 명령어 실행 뒤, 다음 실행할 명령어가 확정되지 않음.

    여러 개의 다음 명령어를 병렬적으로 실행하는 기계라고 생각하자.

 

 

2.3-5 결정론적 튜링 기계에서의 NP 문제

  - 일단 답이 있으면 그 답이 맞는지는

    다항식 시간안에 검증하는 것은 가능.

 

  - 푸는데는 지수 시간이 걸릴 수도 있음.

    그래도 다항식 시간 안에 검증 가능

 

 

2.3-6 랜덤 접근 기계는 결정론적 튜링 기계

  - 랜덤 접근 기계: 레지스터를 갖춘 CPU 1개

 

  - 결정론적 튜링 기계

    어떤 명령어 실행 즉시, 다음 실행할 명령어가 확정됨.

    코어 하나에서 명령어를 순서대로 실행한다 생각해도됨.

 

  - 앞으로 별도 언급이 없으면 결정론적 튜링 기계를 의미.

 

  - NP 문제를 일반적인 방법으로 풀기에는 좀 느림.

    대신 무작위, 근사, 휴리스틱 알고리듬 등을 이용

 

2.3-7 P일까 NP일까

  - Ex020307_hasGreater

/* main.cpp */

#include <iostream>

using namespace std;

enum { LENGTH = 8 };

bool hasGreater(int nums[], size_t length, int k);

int main(void)
{
    int arr[LENGTH] = { 0, 1, 2, 3, 4, 5, 6, 7};
    int k1 = 9;
    int k2 = 3;

    cout << boolalpha << hasGreater(arr, LENGTH, k1) << endl;
    cout << hasGreater(arr, LENGTH, k2) << endl;

    return 0;
}

bool hasGreater(int nums[], size_t length, int k)
{
    for (size_t i = 0; i < length; ++i) {
        if (k < nums[i]) {
            return true;
        }
    }

    return false;
}

 

  - 배열에 어떤 값보다 큰 값이 있는지 알아내는 문제는

    P일까 NP일까?

 

  - 일단 다항식 시간(O(N))안에 풀 수 있으니,

    P는 맞음.

 

  - 병렬적으로도 다항식 시간 안에 풀 수 있는 문제이므로

    NP이기도 함.

    NP가 Not P의 준말이 아님에 주의 해야함.

 

 

2.3-8 NP를 다항식 시간안에 검증할 수 있다

  - 검증이란, 답이 맞는지 확인하는 과정.

    즉, 답은 알고 있다는 뜻.

 

  - 답이란, 비결정론적 문제의 경우의 수들 중

    각 분기마다 따라야 하는 가지들

 

  - 다음 둘을 비교하는 것이 검증임.

    가지를 따라 명령어를 실행한 결과

    올바른 값

 

  - 같으면 검증 완료

결정론적 Vs. 비결정론적

 

 

2.3-8 P 또는 NP가 아님.

  - 둘 사이의 판단 기준이 아예 다름.

    NP가 Not P의 약자가 아니라고 말한 이유.

 

 - 사실 모든 P 문제는 NP. 따라서 아래 그림 형태.

2.4 NP-완전과 NP-난해

 

2.4-0 NP-완전(NP-Complete, NPC) 문제

  - NP 문제 중의 일부

 

  - 모든 NP 문제들은 NP-완전 문제로 환원 가능.

    그것도 다항식 시간 안에.

    여전히 NP 문제이니 다항식 시간 안에 검증 가능

 

  - 최소 다른 NP 문제들만큼 어려운 문제

    따라서 NP 문제들 중에서도

    가장 어려운 문제라고 할 수 있음.

 

2.4-1 NP-완전 문제의 예

  - 외판원 문제(판정 버전)

    어떤 정해진 길이 L이 있음.

    이 길이를 넘지 않는 경로가 있는지 판정

    나중에 그래프 배우면서 보게 됨.

 

  - 배낭(knapsack) 문제

    크기와 가격이 다른 여러 물품이 있음.

    값어치가 최대가 되도록 물건 넣기

    당연히 배낭에는 크기 제한이 있음.

    판정 버정: 최소 어떤 값어치 V만큼 넣을 수 있는가?

                  약한 NP-완전 문제: 의사 다항식 시간안에 풀 수 있음.

 

  - 해법은 추후에 배움.

    동적 계획법(Dynamic Programming)

    그리디(Greedy) 알고리듬

 

  - 그런데 위 문제들은 어떤 제약이 있을 때임.

    그럼 제약이 없으면 더 어렵다는 뜻일까?

 

 

2.4-2 NP-난해(NP-hard) 문제

  - 최소 NP-완전 문제만큼 어려운 문제들

 

  - NP-완전 문제는 모두 NP-난해 문제

 

  - NP가 아닌 문제도 있음.

    즉, 다항식 시간 안에 검증조차 불가능한 문제

    당연히 NP보다 복잡도가 높은 문제

 

2.5 P == NP Vs. P != NP

 

2.5-0 P-NP 문제

  - P냐 NP냐를 논하는 문제가 아님.

    P와 NP가 같은지 다른지를 논하는 문제임.

 

2.5-1 P == NP Vs. P != NP

  - NP-완전 문제는 NP 문제 중 가장 어려운 문제

 

  - NP-완전 문제 중 하나라도 다항식 시간 안에 풀 수 있다면?

    이 문제는 P가 됨.

    모든 NP 문제를 NP-완전 문제로 다항식 시간 안에 환원할 수 있음.

    따라서 모든 NP 문제가 P 문제가 됨. (P == NP)

    그러나, 아직 다항식 시간 알고리듬을 발견 못했기에 P가 아님.

 

  - P == NP가 증명되명 디지털 사회에 미치는 여파는?

    느려서 못 풀던 그 많은 문제를 효율적으로 풀 수 있어짐.

 

 

2.5-2 P-NP 문제 증명법

  - NP-완전 문제 중에 하나라도 다항식 시간 안에 풀면 됨.

    발견하는 순간 이 논란은 종식됨.

 

  - 반대로 P != NP를 증명하는 방법은?

    없음. P == NP를 증명 못하는 시간이 길어질수록

    개연성만 높아짐. 따라서 현재에는 P != NP일거라 추측 중