NP 및 P로 문제를 생성해야하는 이유는 무엇입니까?

Question

NP 및 P로 문제를 분할하는 주된 의도 또는 주요 용도는 무엇입니까? 역사적인 이유가 있습니까? 아니면 우리가이 개념을 만들었습니까? 그렇다면 어디에서 도움이 될까요?

Answer 1

이것은 여기에 철저한 대답을 기대하기에는 너무 복잡합니다. 그러나 간단히 말해서 실용적인 관점에서 볼 때 P의 문제는 합리적인 시간과 해결책으로 NP에서 문제를 발견 할 수있는 문제입니다 (P! = NP라고 가정하고) 계산에 너무 많은 시간이 걸리는 솔루션입니다.

P와 NP 사이의 경계는 비공식적으로 계산을 사용하여 효율적으로 해결할 수 있고 해결할 수없는 문제 사이의 경계로 생각할 수 있습니다.

위키 백과 http://en.wikipedia.org/wiki/P_versus_NP_problem을 먼저 읽어야 이러한 복잡성 등급의 동기와 목적에 대해 자세히 알 수 있습니다.

Answer 2

P와 NP에 문제를 나누는 "실제적인"의도는 하한이라고 생각합니다. 문제가 NP 하드 (그리고 P! = NP라는 일반적인 믿음에 동의 함)하면 합리적인 시간 내에 실행되는 문제에 대한 알고리즘을 찾을 수 없다는 것을 증명했습니다.

좀 더 비공식적으로 보스가 5 분 안에 실행되는 알고리즘을 작성하라고합니다. 네가 찾을 수 없다고 말하면, 그는 너가 가만히 있다고 생각할거야. 그가 당신에게 NP 하드라고 질문 한 것을 보여 주면, 당신은 그것을 할 수 없다고 확신해야합니다. 형식주의로 돌아 가면 근사 알고리즘을 사용하여 정당화 할 수 있습니다.

업계에서 현재 NP 완료 (예 : SAT-solvers) 또는 PSPACE 완료 (예 : 공식 확인, PSPACE 완료) 문제를 구현하기 때문에이 모든 것은 이전 대화입니다. 수식의 크기). 반면에, 예를 들어 그래픽에서는 가끔 n^2에서 실행되는 알고리즘을 구현할 수 없습니다. 심지어 nlogn 때로는 날카로운 수 있습니다.

Answer 3

주요 개념은 난이도에 따라 문제를 구분하는 것입니다.

여기서 은 모든 쉬운 문제 (합리적인 시간 내에 해결 가능)를 나타냅니다. 그리고 NP 어려운 것들. (합리적인 시간 솔루션이 존재하지 않지만 솔루션을 추측 할 수 있다면 빨리 검증 할 수 있습니다.)

일단이 두 세트로 문제를 분류하면 해결에 대해 걱정할 수 있습니다.

예를 들어, NP 문제가 발생하는 경우 솔루션에 머리를 부수는 대신 적절한 시간 내에 해결할 수 없다는 것을 알게되거나 좋은 추측 작업을 사용하면 솔루션을 확인하십시오).

한편, P 문제인 경우 더 효율적인 솔루션을 찾는 등의 작업을 할 수 있습니다.