NP는 무엇을 의미합니까?

NP는 비결정론적 다항 시간(nondeterministic polynomial time)을 의미합니다. 동등하게, 제안된 해결책을 찾는 것이 어려워 보일지라도 다항 시간 내에 확인할 수 있다면 그 문제는 NP에 속합니다. 주어진 길이보다 짧은 외판원 경로는 일단 주어지면 확인하기는 쉽지만, 발견하기는 어려운 것으로 보입니다.

새로운 문제가 NP-완전임을 어떻게 증명합니까?

두 가지를 보여주어야 합니다. 첫째, 그 문제가 NP에 속하여 후보 해결책을 빠르게 확인할 수 있다는 것, 둘째, 알려진 NP-완전 문제 중 일부가 다항 시간 내에 그 문제로 환원된다는 것입니다. 이 환원은 알려진 난해함(hardness)을 전달하여 새로운 문제를 NP에서 가장 어려운 문제들 중 하나로 만듭니다.

NP-완전성 및 환원

NP-완전 문제는 NP 클래스 내에서 가장 어려운 문제 중 하나이며, 모든 NP 문제가 효율적으로 이 문제로 환원될 수 있다는 점에서, 단 하나의 NP-완전 문제를 빠르게 해결하면 모든 NP 문제를 해결할 수 있게 됩니다.

PaperMind(으)로 주제 찾기곧 제공Find papers & topics

Tools & resources

슬라이드 다운로드

Learn & explore

동영상곧 제공

Definition

어떤 문제가 NP에 속하고 NP에 있는 모든 문제가 다항 시간 환원(polynomial-time reduction)에 의해 그 문제로 환원될 수 있다면 그 문제는 NP-완전입니다. 이러한 문제들은 NP의 최대 난이도 구성원이며, 효율적인 변환에 있어서 서로 동등합니다.

Scope

이 주제는 다항 시간 내에 검증 가능한 문제들의 클래스인 NP, 다항 시간 다대일 환원(polynomial-time many-one reductions), 만족성(satisfiability)을 NP-완전으로 확립한 쿡-레빈 정리(Cook–Levin theorem), 카프(Karp)의 NP-완전 조합 문제 목록, 그리고 알려진 문제들로부터 환원을 통해 새로운 문제를 NP-완전으로 증명하는 방법론을 다룹니다.

Core questions

어떤 문제가 NP에서 가장 어려운 문제 중 하나라는 것은 무엇을 의미합니까?
쿡-레빈 정리(Cook–Levin theorem)는 어떻게 첫 번째 NP-완전 문제를 식별합니까?
새로운 문제가 NP-완전임을 증명하기 위해 환원(reductions)은 어떻게 사용됩니까?
하나의 문제의 NP-완전성이 수천 개의 다른 문제에 왜 영향을 미 미칩니까?

Key theories

쿡-레빈 정리(Cook–Levin theorem): 부울 만족성(Boolean satisfiability)은 NP-완전인데, 이는 모든 다항 시간 검증자(polynomial-time verifier)의 계산이 만족성 인스턴스로 인코딩될 수 있기 때문이며, 이는 다른 문제들이 파생되는 근본적인 완전 문제(complete problem)를 제공합니다.
카프 환원(Karp reductions)과 NP-완전 문제들의 웹: 카프(Karp)는 그래프 색칠(graph coloring)부터 외판원 결정 문제(traveling salesman decision problem)에 이르기까지 21개의 자연스러운 문제들이 다항 시간 환원(polynomial-time reductions)에 의해 NP-완전임을 보여주었으며, 이는 환원의 확장되는 네트워크를 통해 난해함(hardness)을 확립하는 관행을 시작했습니다.

Clinical relevance

NP-완전성은 난해함(intractability)에 대한 실질적인 진단 도구입니다. 스케줄링, 물류, 설계 또는 검증 분야의 문제가 NP-완전으로 밝혀지면, 엔지니어들은 보장된 빠른 정확한 알고리즘을 찾는 것을 멈추고 근사 알고리즘, 휴리스틱, 정수 계획법 해결사 또는 문제를 다루기 쉽게 만드는 제약 조건으로 전환하게 됩니다.

History

쿡(Cook)은 1971년에 만족성이 NP-완전임을 증명했으며, 레빈(Levin)은 소련에서 독립적으로 동등한 결과를 얻었습니다. 1972년에 카프(Karp)는 21개의 추가적인 NP-완전 문제를 시연하여 이 현상의 보편성을 드러냈고, NP-완전성을 계산 복잡도(computational hardness)를 진단하는 핵심 도구로 만들었습니다.

Key figures

Stephen Cook
Leonid Levin
Richard Karp

Seminal works

cook1971
karp1972

Frequently asked questions

NP는 무엇을 의미합니까?: NP는 비결정론적 다항 시간(nondeterministic polynomial time)을 의미합니다. 동등하게, 제안된 해결책을 찾는 것이 어려워 보일지라도 다항 시간 내에 확인할 수 있다면 그 문제는 NP에 속합니다. 주어진 길이보다 짧은 외판원 경로는 일단 주어지면 확인하기는 쉽지만, 발견하기는 어려운 것으로 보입니다.
새로운 문제가 NP-완전임을 어떻게 증명합니까?: 두 가지를 보여주어야 합니다. 첫째, 그 문제가 NP에 속하여 후보 해결책을 빠르게 확인할 수 있다는 것, 둘째, 알려진 NP-완전 문제 중 일부가 다항 시간 내에 그 문제로 환원된다는 것입니다. 이 환원은 알려진 난해함(hardness)을 전달하여 새로운 문제를 NP에서 가장 어려운 문제들 중 하나로 만듭니다.