P-NP

다항 시간에 풀 수 있는가?

• 현재까지 배운 알고리즘의 시간 복잡도는 다음과 같다

  

• 그러나 exp하게 증가하는 문제가 있다: Search Problem

  • algorithm C, instance I, solution S

    • C runs in time polynomial of $|I|$
    • S is a Solution to I ↔ C(I,S)==true

    즉 정답을 확인하는 데에 다항 시간이 걸리는 문제들이다 S를 찾는 데에는 다항시간이 걸릴수도 안걸릴수도 있음

    <aside> 💡 Class NP: (Non-deterministic Polynomial) Class of ALL Search problems

    Class P: (Deterministic Polynomial) Class of all search problems that can be solved in Polynomial time

    </aside>

  • 예시

    

    • 1번, 3번은 P 2번, 4번은 NP이다
    • …………………………
    • 경로를 하나 찾는 것이 search problem이다! shortest, longest아님

P-NP Problem

• $P \subset NP$임은 자명하다
• $P=NP$라면
  • 이 세상의 모든 문제가 다항 시간 내에 풀린다
  • P≠NP라고 추측하지만 아직 증명되지는 않았다

Reductions 환원

대부분의 NP 문제는 동치이다

Undecidability

1. B가 쉬우면 A도 쉽게 풀 수 있다
2. A가 어렵다면 B도 어렵다

• 코멘트
  • 많은 NP 문제들은 같은 문제로 환원된다고 한다
  • 만약 NP인 B (ex. TSP)가 다항 시간에 풀리면 모든 NP가 다항시간에 풀려 P=NP를 증명할 수 있다
    • (사실 불가능하다)
    • (앞으로 증명할 것이 바로 “P=NP는 아니다” 이다)
    • (그렇다고 P≠NP를 증명하는 것은 아니다)

NP-Hard

A problem is NP-Hard if ALL search problems(NP) reduce to it

NP-Complete

A search problem is NP-complete if all other search problems reduce to it(NP-hard), and itself is NP class (NP)

• A가 NP-complete이면 우선 모든 NP search problem이 A로 환원되고 어떤 새로운 B에 대해 problem → A → B로 reduce하여 새로운 B도 NP-complete임을 알 수 있다
• 따라서 NP-Complete에 속하는 문제 하나를 다항 내에 풀면 다른 모든 NP 문제를 다항 내에 풀 수 있다 (불가능)