결정문제와 비결정문제

Deterministic - 결정문제

  계산 이론의 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다.

일반적으로 모든 문제는 결정 문제로 환원될 수 있다고 정의하며, 이러한 결정 문제를 해결하는 절차를 정의한 것을 알고리즘이라고 한다. 어떤 결정 문제를 해결하는 알고리즘이 있으면 '결정 가능하다' 라고 말하며, 알고리즘이 없으면 '결정 불가능하다' 라고 한다.

 

  이를 컴퓨터 알고리즘의 정의를 바탕으로 말하면

"모든 입력값 n에 대해 유한 시간 내에 컴퓨터로 정확한 결과를 출력하는 알고리즘이 있으면 그 문제는 해결되었다."

과 같이 말할 수 있다.

 

유한 시간 : 알고리즘 성능 상의 '다항 시간 성능' 알고리즘

=> 자료구조 문제, 데이터 탐색 문제, 데이터 정렬 문제만이 다항 시간 성능 컴퓨터 알고리즘이 있는 문제들이다.

==> 결정 문제를 해결한 알고리즘은 정의된 모든 '과정'이 '유일'하게 '결정'되며, 유일한 결정을 따라 유한 시간 안에

       결과값을 출력하는 알고리즘

 

 

Nondeterministic - 비결정문제

  현재 상태에서 다음 상태로 변할 때 다음 상태가 유일하게 결정되지 않는 문제이다.

다음 상태의 결정이 상황에 따라 다를 수 있으며, 여러 개이거나 없을 수도 있다. 따라서 계산 경로가 트리 형태로 형성되며, 문제 해결이 보장되지 않는다. 

  결정 문제 기반 튜링 기계에서 비결정 문제를 해결하기 위해 우리는 다음과 같이 컴퓨터 알고리즘의 요건을 재정의하게 된다.

• 모든 입력 n에 대하여 → 현실적인 입력값
• 수행 시간 → 다항식 시간
• 정답 → 근사값 / 확인 문제로 전환한 결과

=> 휴리스틱 방법을 사용하기도 한다.

 

 

휴리스틱

  주어진 문제의 확률값이나 근사값을 다항 시간 안에 결과를 얻기 위하여 문제에 대한 경험치를 컴퓨터 알고리즘에 포함시키는 방법을 휴리스틱이라고 한다.

  튜링 기계의 알고리즘은 원래 기계적으로 순서를 정하여 문제를 해결하는 것을 원칙으로 하나, 정확한 값을 도출하기 위하여 인간의 경험치를 도입시킨 것으로 정답률을 높히기 위해 좋은 선택을 할 수 있도록 도와주는 역할을 하는 것이다.

또한 다항 시간안에 끝낼 수 있도록 하기 위한 방법이다.

=> 다항 시간 내에 정확한 결과를 출력하는 알고리즘은 없지만, 다항 시간 내에 답과 유사한 결과를 출력하는 알고리즘이 많이 연구되고 있다.

 

 

---

 

P 문제

  Polynomial 은 다항식을 의미하며  다항 시간에 해결되는 문제를 말한다. 이전 정의한 문제 해결을 바탕으로 입력값 n에 대해서 정확한 답을 다항 시간 내에 출력하는 성능을 가진 알고리즘이 있는 문제를 말한다.

  이때 다항 시간 성능은 로그, 선형, 로그 선형, 이차, 다차 시간을 말한다. 이 문제들은 컴퓨터로 해결된 쉬운 문제라고도 한다. 자료구조 문제, 데이터 탐색 문제, 데이터 정렬 문제가 대표적인 P 문제들이다.

 

 

NP문제

  Non-Deterministic Polynomial 은 비결정적 다항식을 의미하며, 다항 시간에 해결되는 비결정 문제를 말한다. 앞에서 재정의 요건을 만족하거나, 휴리스틱 방법을 사용하여 다항 시간에 해결되는 문제이다.

 기본적으로는 컴퓨터로 해결할 수 없는 문제들이기 떄문에 휴리스틱, 근사비율을 낮추기, 문제의 정답을 정의하고자 하는 방법 등을 이용하여 비결정 문제를 다항 시간 내에 해결할 수 있는 문제가 될 수 있다.

 

---

NP문제 종류

   NP-Complete / NP-Hard 

  Complete 

  완전 ,완성된 뜻을 가지는 NP-Complete는 NP 완전 문제에 대한 다항 시간 성능 알고리즘이 있으면 지금까지 알려진 모든 NP 문제들이 같은 해결된다는 것이다. 따라서 NP 완전 문제는 NP 문제들 중에서 가장 어려운 문제이며, 종결자 문제라고도 한다.

  NP 완전 문제에 대한 다항 시간 알고리즘으로 다른 NP 문제들을 해결하기 위해서는 다른 NP문제를 NP 완전 문제와 같은 문제로 변환해야 하는데, 이때 반드시 '다항 시간' 안에 변환되어야 한다. 이러한 방법을 건너 풀기 등으로 표현할 수 있다.

  1971 스티븐 쿡에 의해 확립되었으며 SAT(Satisfiability) 문제가 NP 문제이면서, 다른 모든 NP 문제들이 다항 시간 안에 SAT 문제로 변환 될 수 있는 NP 완전 문제임을 증명했다. 이후 많은이들이 NP 완전 문제라고 알려진 문제로부터 다항 시간 안에 변환하는 문제도 NP 완전 문제임을 증명했으며, SAT 이외에 수많은 문제들을 변환 할 수 있는 NP임을 밝혀냈다.

 

 

입력 변환 / B 알고리즘 / 출력 변환 알고리즘

 

그 값들 중 가장 높은 차수를 갖는 성능이 문제 A의 알고리즘임을 보여주는 O(n)표기법

 

NP-Hard

  NP 하드 문제는 NP 완전 문제이기도 하지만 반드시 NP 문제일 필요는 없다. 즉, NP 완전 문제는 반드시 NP 문제라는 조건을 갖지만, NP 하드 문제는 NP 문제는 아닌데, NP 완전 문제만큼 어려운 문제를 의미한다. 이때 모든 NP 완전 문제는 어려운 문제로 분류되어 NP 하드 문제에 속한다. NP 하드 중 NP 문제인 것이 NP 완전 문제라고 한다. NP 하드 문제는 완전문제만큼 어렵지만, NP 문제가 아닐 수도 있기 때문에 NP하드의 알고리즘으로는 다른 NP 문제들을 문제 변환을 통해 해결 될 수 없다는 것을 의미한다.

 

 

P/ NP / NP-C / NP-H 문제들의 관계

∀p ∈ NP  : 사실

∀np ∊ P or ∀np ∉ P // P ≠ NP or P = NP : 증명되지 않음   ( ∌∋∈∉ ∀  ≠=)

  현재 튜링 기계에 기반한 컴퓨터 세계에서는 P 문제와 NP 문제가 같지 않다고 추측하고 있다.

지금까지 밝혀진 정의에 기반한 포함 관계 그림