NP, NP- 완성 및 NP-HARD의 차이점은 무엇입니까?
https://stackoverflow.com/questions/1857244
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
차이점은 무엇입니까? NP, NP- 완성 그리고 NP-HARD?
나는 웹 전체의 많은 리소스를 알고 있습니다. 나는 당신의 설명을 읽고 싶습니다. 그 이유는 그것들이 거기에있는 것과 다를 수도 있고, 내가 알지 못하는 것이 있기 때문입니다.
해결책
기술적 인 정의는 이해하는 데 꽤 많은 시간이 필요하기 때문에 직관적 인 정의를 찾고 있다고 가정합니다. 우선, 그러한 정의를 이해하기위한 예비 필요한 개념을 기억합시다.
- 결정 문제: a의 문제 예 또는 아니요 대답.
이제 우리는 그것들을 정의합시다 복잡성 수업.
피
P는 다항식 시간에 해결할 수있는 모든 결정 문제의 세트를 나타내는 복잡성 클래스입니다..
즉, 문제의 사례가 주어지면, 대답은 다항식 시간에 결정될 수 있습니다.
예시
연결된 그래프가 주어졌습니다 G, 가장자리가 단색이 아닌 두 가지 색상을 사용하여 정점을 채색 할 수 있습니까?
알고리즘 : 임의의 정점으로 시작하여 빨간색을 색칠하고 모든 이웃을 파란색으로 채우고 계속하십시오. 정점이 부족하거나 가장자리가 두 가지 모두 같은 색상을 갖도록 강요받을 때 중지하십시오.
NP
NP는 대답이 "예"인 사례가 다항식 시간에 확인할 수있는 증거를 갖는 모든 결정 문제의 세트를 나타내는 복잡성 클래스입니다.
이것은 누군가가 우리에게 문제의 사례와 인증서 (때로는 증인이라고 함)를 응답이라고 생각한다면, 우리는 그것이 다항식 시간에 맞는지 확인할 수 있음을 의미합니다.
예시
정수 인수 화 NP에 있습니다. 이것은 정수가 주어진 문제입니다 n 그리고 m, 정수가 있습니까? f ~와 함께 1 < f < m, 그렇게 f 분열 n (f 작은 요인입니다 n)?
답이 예 또는 아니오이기 때문에 결정 문제입니다. 누군가가 우리에게 문제의 사례를 건네 주면 (그래서 그들은 우리에게 정수를 건네줍니다 n 그리고 m) 그리고 정수 f ~와 함께 1 < f < m, 그리고 그것을 주장합니다 f 요인입니다 n (인증서), 우리는 답을 확인할 수 있습니다. 다항식 시간 부서를 수행함으로써 n / f.
NP- 완성
NP-Complete는 모든 문제의 세트를 나타내는 복잡성 클래스입니다. X 다른 NP 문제를 줄일 수있는 NP에서 Y 에게 X 다항식 시간에.
직관적으로 이것은 우리가 해결할 수 있음을 의미합니다 Y 해결 방법을 알고 있다면 빨리 X 빠르게. 정확히, Y 환원 가능합니다 X, 다항식 시간 알고리즘이있는 경우 f 인스턴스를 변환합니다 y 의 Y 경우에 x = f(y) 의 X 다항식 시간에 y 예, 대답이있는 경우에만 f(y) 예입니다.
예시
3-SAT. 이것은 우리가 3- 클라스 분할 (OR)의 결합 (및), 양식의 진술을 제공하는 문제입니다.
(x_v11 OR x_v21 OR x_v31) AND
(x_v12 OR x_v22 OR x_v32) AND
... AND
(x_v1n OR x_v2n OR x_v3n)
각각 x_vij 부울 변수 또는 유한 사전 정의 된 목록에서 변수의 부정입니다. (x_1, x_2, ... x_n).
그것은 그것을 보여줄 수 있습니다 모든 NP 문제는 3-SAT로 줄일 수 있습니다. 이것의 증거는 기술적이며 NP의 기술적 정의를 사용해야합니다.비 결정적 튜링 머신을 기반으로합니다). 이것은 다음과 같습니다 쿡의 정리.
NP- 완성 문제를 중요하게 만드는 것은 결정 론적 다항식 시간 알고리즘이 그 중 하나를 해결하는 데 발견 될 수 있다면 모든 NP 문제가 다항식 시간에 해결할 수 있다는 것입니다 (모두를 배제하는 데 하나의 문제).
NP-HARD
직관적으로, 이것들은 문제입니다 적어도 NP- 완료 문제만큼 어렵습니다. NP-HARD 문제가 있습니다 NP에있을 필요는 없습니다, 그리고 그들은 의사 결정 문제 일 필요가 없습니다.
여기서 정확한 정의는 그 것입니다 문제 X NP- 완료 문제가있는 경우 NP-HARD입니다 Y, 그렇게 Y 환원 가능합니다 X 다항식 시간에.
그러나 다항식 시간에 NP- 완료 문제가 다른 NP- 완료 문제로 줄일 수 있기 때문에 모든 NP- 완성 문제는 다항식 시간에 NP-HARD 문제로 줄일 수 있습니다. 그런 다음 다항식 시간에 하나의 NP-HARD 문제에 대한 해결책이 있다면 다항식 시간에 모든 NP 문제에 대한 해결책이 있습니다.
예시
그만큼 중단 문제 NP- 하드 문제입니다. 이것은 프로그램이 주어진 문제입니다 P 그리고 입력 I, 멈출까요? 이것은 결정 문제이지만 NP에 있지 않습니다. NP- 완료 문제가 이것으로 감소 될 수 있음이 분명합니다. 또 다른 예로서, 모든 NP- 완료 문제는 NP-HARD입니다.
내가 가장 좋아하는 NP- 완성 문제는 다음과 같습니다 광산 문제.
p = np
이것은 컴퓨터 과학에서 가장 유명한 문제이며 수학 과학에서 가장 중요한 질문 중 하나입니다. 사실, 클레이 연구소 문제에 대한 해결책을 위해 백만 달러를 제공하고 있습니다 (Stephen Cook 's 쓰기 점토 웹 사이트에서는 꽤 좋습니다).
P는 NP의 서브 세트라는 것이 분명합니다. 열린 질문은 NP 문제에 결정적 다항식 시간 솔루션이 있는지 여부입니다. 그들이 그렇지 않다고 믿는다. 다음은 P = NP 문제의 최신 (및 중요성)에 대한 최근 기사입니다. P 대 NP 문제의 상태.
주제에 관한 최고의 책은입니다 컴퓨터 및 다루기 쉬운 Garey와 Johnson에 의해.
다른 팁
나는 주위를 둘러보고 많은 긴 설명을보고 있습니다. 다음은 요약하는 데 유용 할 수있는 작은 차트입니다.
어려움이 어떻게 위로 올라가는 지 주목하십시오 NP는 NP- 완성으로 줄일 수 있습니다, 그리고 어떤 것도 NP- 완성은 NP-HARD로 줄일 수 있습니다, 모두 p (다항식) 시간.
P Time에서 더 어려운 클래스의 문제를 해결할 수 있다면 P 시간으로 모든 쉬운 문제를 해결하는 방법을 찾았습니다 (예 : NP- 완료 문제를 해결하는 방법을 알아 내면 p = np를 증명하는 것과 같습니다. p 시간).
____________________________________________________________ | Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty ___________________________________________________________| | | P | Yes | Yes | | | NP | Yes | Yes or No * | | | NP-Complete | Yes | Unknown | | | NP-Hard | Yes or No ** | Unknown *** | | ____________________________________________________________ V
메모 Yes 또는 No 항목 :
- * P 시간에도 p 인 NP 문제는 p 시간으로 해결 될 수 있습니다.
- ** NP- 완료 인 NP-HARD 문제는 P 시간으로 검증 가능합니다.
- *** NP- 완료 문제 (모두 NP-HARD의 서브 세트를 형성 함). 나머지 NP 하드는 아닙니다.
나는 또한 발견했다 이 다이어그램 이러한 모든 유형이 서로 어떻게 대응하는지 보는 데 매우 유용합니다 (다이어그램의 왼쪽 절반에 더 많은주의를 기울이십시오).
이것은 질문에 대한 매우 비공식적 인 답변입니다.
3233은 1보다 큰 두 개의 다른 숫자의 제품으로 작성할 수 있습니까? 모든 주위의 길을 걸을 수있는 방법이 있습니까? Königsberg의 7 개의 다리 다리를 두 번 복용하지 않고? 이것들은 일반적인 특성을 공유하는 질문의 예입니다. 답을 효율적으로 결정하는 방법은 분명하지 않을 수 있지만 답이 '예'인 경우 증거가 짧고 빠르게 확인됩니다. 첫 번째 경우에 51의 사소한 인수 화; 두 번째로, 다리를 걷는 경로 (제약 조건).
ㅏ 결정 문제 하나의 매개 변수에만 다른 예 또는 아니오 답변이있는 질문 모음입니다. 문제 합성 = { "IS를 말하십시오 n 합성물": n 정수} 또는 eulerpath = { "그래프를 수행합니다. G 오일러 경로가 있습니까? ": G 유한 그래프}입니다.
이제 일부 결정 문제는 명백한 알고리즘이 아닌 경우 효율적으로 적용됩니다. Euler는 250 년 전에 "Königsberg의 Seven Bridges"와 같은 문제에 대한 효율적인 알고리즘을 발견했습니다.
반면에, 많은 결정 문제의 경우, 답을 얻는 방법은 분명하지 않습니다. 그러나 추가 정보를 알고 있다면 답을 올바르게 얻는 것을 증명하는 방법은 분명합니다. 복합재는 다음과 같습니다. 시험 부서는 명백한 알고리즘이며 느린다. 10 자리 숫자를 고려하려면 100,000 개의 가능한 디바이저와 같은 것을 시도해야합니다. 그러나 예를 들어 누군가가 61이 3233의 제수라고 말하면 Simple Long Division은 그들이 정확하다는 것을 효율적으로 알 수있는 방법입니다.
복잡성 클래스 NP '예'답변이 상태가 부족하여 증거를 빠르게 확인하는 결정 문제의 클래스입니다. 합성물처럼. 중요한 요점 중 하나는이 정의가 문제가 얼마나 어려운지에 대해 아무 말도하지 않는다는 것입니다. 의사 결정 문제를 해결할 수있는 정확하고 효율적인 방법이 있다면 솔루션의 단계를 작성하는 것만으로는 충분합니다.
알고리즘 연구는 계속되고 새로운 영리한 알고리즘이 항상 생성됩니다. 오늘날 효율적으로 해결하는 방법을 모르는 문제는 내일 효율적인 (명백하지 않은 경우) 솔루션을 가질 수 있습니다. 사실, 그것은 연구원들을 데려 갔다 2002 합성에 대한 효율적인 솔루션을 찾으려면! 이 모든 발전으로 인해 정말로 궁금해해야합니다. 짧은 증거가 환상에 관한 것입니까? 아마도 모든 효율적인 증거에 적합한 의사 결정 문제 효율적인 솔루션이 있습니까? 아무도 모릅니다.
아마도이 분야에 가장 큰 기여는 독특한 클래스의 NP 문제를 발견했습니다. Stephen Cook은 계산을위한 회로 모델을 사용하여 NP 품종의 결정 문제를 발견했습니다. 모든 다른 NP 문제. 효율적인 솔루션 부울 만족도 문제 효율적인 솔루션을 만드는 데 사용될 수 있습니다 다른 것 NP의 문제. 얼마 지나지 않아 Richard Karp는 다른 많은 결정 문제가 같은 목적을 달성 할 수 있음을 보여주었습니다. NP에서 "가장 어려운"문제는 어떤 의미에서 이러한 문제가 NP- 완성 문제.
물론 NP는 결정 문제의 클래스 일뿐입니다. "n의 요소 찾기", "모든 정점을 방문하는 그래프 G에서 가장 짧은 경로를 찾으십시오", "다음 부울 표현을 사실로 만드는 변수 할당 세트를 제공하십시오." 비공식적으로 그러한 문제가 "NP에있는"문제에 대해 비공식적으로 이야기 할 수도 있지만 기술적으로는 의미가 없지만 의사 결정 문제가 아닙니다. 이러한 문제 중 일부는 NP- 완성 문제와 동일한 종류의 힘을 가질 수 있습니다. 이러한 (결정되지 않은) 문제에 대한 효율적인 솔루션은 NP 문제에 대한 효율적인 솔루션으로 직접 이어질 것입니다. 이와 같은 문제를 호출합니다 NP-HARD.
다른 위대한 대답 외에도 여기에 일반적인 스키마 사람들은 NP, NP-Complete 및 NP-HARD의 차이를 보여주는 데 사용합니다.
P (다항식 시간) : 이름 자체가 알 수 있듯이, 이것은 다항식 시간에 해결할 수있는 문제입니다.
NP (비 결정적 폴리 곡물 시간) : 이들은 다항식 시간에 확인할 수있는 결정 문제입니다. 즉, 특정 문제에 대한 다항식 시간 솔루션이 있다고 주장한다면, 당신은 그것을 증명하도록 요청합니다. 그런 다음 다항식 시간에 쉽게 확인할 수있는 증거를 알려 드리겠습니다. 이러한 종류의 문제를 NP 문제라고합니다. 여기서는이 문제에 대한 다항식 시간 솔루션이 있는지 여부에 대해 이야기하지 않습니다. 그러나 우리는 다항식 시간에 주어진 문제에 대한 해결책을 확인하는 것에 대해 이야기하고 있습니다.
NP-HARD : NP에서 가장 어려운 문제만큼 어렵습니다. 다항식 시간에 이러한 문제를 해결할 수 있다면 존재할 수있는 NP 문제를 해결할 수 있습니다. 이러한 문제는 반드시 NP 문제 일 필요는 없습니다. 즉, 우리는 다항식 시간에 이러한 문제에 대한 해결책을 확인할 수 없습니다.
NP- 완성 : NP와 NP-HARD의 문제입니다. 즉, 이러한 문제를 해결할 수 있다면 다른 NP 문제를 해결할 수 있으며 이러한 문제에 대한 해결책은 다항식 시간에 확인할 수 있습니다.
기술에 들어 가지 않고 P v. NP를 설명하는 가장 쉬운 방법은 "단어 문제"와 "객관식 문제"를 비교하는 것입니다.
"단어 문제"를 해결하려고 할 때는 솔루션을 처음부터 찾아야합니다. "객관식 문제"를 해결하려고 할 때 선택할 수 있습니다. 선택이 있습니다. "단어 문제"처럼 해결하거나 귀하에게 주어진 각 답변을 연결하고 적합한 후보 답변을 선택하십시오.
"객관적인 문제"가 해당 "단어 문제"보다 훨씬 쉬운 경우가 종종 발생합니다. 후보 답변을 대체하고 적합한 지 확인하면 정답을 처음부터 찾는 것보다 훨씬 적은 노력이 필요할 수 있습니다.
이제 우리가 다항식 시간이 "쉬운"시간에 동의한다면 클래스 P는 "쉬운 단어 문제"로 구성되며 클래스 NP는 "쉬운 객관식 문제"로 구성됩니다.
P v. NP의 본질은 다음과 같습니다. "단어 문제로 쉽지 않은 객관식 문제가 있습니까?" 즉, 주어진 답변의 유효성을 쉽게 확인할 수있는 문제가 있지만 그 대답을 처음부터 찾는 것이 어렵습니까?
이제 우리는 NP가 무엇인지 직관적으로 이해하므로 직관에 도전해야합니다. 어떤 의미에서 가장 어려운 "객관적인 문제"가 있다는 것이 밝혀졌습니다. "가장 어려운 모든"문제 중 하나에 대한 해결책을 찾을 수 있다면 모든 사람에게 해결책을 찾을 수 있습니다. NP 문제! 쿡이 40 년 전에이 사실을 발견했을 때 그것은 완전히 놀라운 일이되었습니다. 이 "가장 어려운 모든"문제는 NP-Hard로 알려져 있습니다. 그들 중 하나에 "단어 문제 해결책"을 찾으면 각 "쉬운 객관식 문제"에 대한 "단어 문제 해결책"을 자동으로 찾을 수 있습니다!
마지막으로, NP- 완료 문제는 동시에 NP 및 NP-HARD 인 문제입니다. 우리의 비유에 따라, 그들은 동시에 "객관식 문제로 쉽게", "가장 어려운 것은 단어 문제로 가장 어려운 것"입니다.
나는 우리가 훨씬 더 간결하게 대답 할 수 있다고 생각합니다. 나는 대답했다 관련 질문, 그리고 거기에서 내 대답을 복사합니다
그러나 첫째, NP-HARD 문제는 다항식 시간 솔루션이 존재한다는 것을 증명할 수없는 문제입니다. 일부 "문제 -P"의 NP-HARDNESS는 일반적으로 이미 입증 된 NP-HARD 문제를 다항식 시간에 "문제 -P"로 변환함으로써 입증됩니다.
나머지 질문에 답하려면 먼저 어떤 NP-HARD 문제가 NP- 완성인지 이해해야합니다. NP-HARD 문제가 설정 NP에 속하는 경우 NP- 완성됩니다. SET NP에 속해 있으려면 문제가 필요합니다.
(i) 결정 문제,
(ii) 문제에 대한 해결책의 수는 유한해야하며 각 솔루션은 다항식 길이 여야하며
(iii) 다항식 길이 솔루션이 주어지면 문제에 대한 답이 예/아니오인지 여부를 말할 수 있어야합니다.이제 NP에 속하지 않고 해결하기가 더 어려울 수있는 많은 NP-HARD 문제가있을 수 있음을 쉽게 알 수 있습니다. 직관적 인 예로서, 실제 일정을 찾아야하는 여행 세일즈맨의 최적화는 길이 <= k의 일정이 존재하는지 아닌지를 결정 해야하는 여행 판매원의 의사 결정 버전보다 어렵습니다.
NP- 완료 문제는 NP-HARD 및 복잡성 클래스 NP의 문제입니다. 따라서 주어진 문제가 NP- 완료임을 보여주기 위해서는 문제가 NP에 있고 NP-Hard임을 보여 주어야합니다.
NP 복잡성 클래스에있는 문제는 다항식 시간에 비 결정적으로 해결 될 수 있으며 NP의 문제에 대한 가능한 솔루션 (즉, 증명서)은 다항식 시간의 정확성을 확인할 수 있습니다.
K-Clique 문제에 대한 비 결정적 솔루션의 예는 다음과 같습니다.
1) 그래프에서 K 노드를 무작위로 선택합니다
2)이 k 노드가 파벌을 형성하는지 확인하십시오.
위의 전략은 입력 그래프 크기의 다항식이므로 K- 클릭 문제는 NP에 있습니다.
다항식 시간에 결정적으로 해결할 수있는 모든 문제는 또한 NP에 있습니다.
문제는 NP-HARD임을 보여주는 것은 일반적으로 다항식 시간 매핑을 사용하여 다른 NP-HARD 문제에서 문제로 감소하는 것을 포함합니다. http://en.wikipedia.org/wiki/reduction_(complexity)
이 특정 질문에 대한 좋은 답변이 정말 있으므로 내 자신의 설명을 쓸만한점이 없습니다. 그래서 나는 다양한 종류의 계산 복잡성에 대한 훌륭한 자원에 기여하려고 노력할 것입니다.
계산 복잡성이 P와 NP에 관한 것이라고 생각하는 사람에게는 다음은 가장 철저한 자원입니다 다른 계산 복잡성 문제에 대해. OP가 요청한 문제와는 별도로, 좋은 설명과 함께 약 500 개의 다른 클래스의 계산 문제와 클래스를 설명하는 기본 연구 논문 목록을 나열했습니다.
내가 이해하면서, an NP-HARD 문제는 AN보다 "어려운"것이 아닙니다 NP- 완성 문제. 실제로, 정의상, 모든 NP- 완료 문제는 다음과 같습니다.
- NP에서
- NP-HARD
- 소개. Cormen, Leiserson, Rivest 및 Stein의 알고리즘 (3ed), pg 1069
흥미로운 정의를 찾으십시오.
