[algorithm] 컴퓨터 과학에서 NP-complete 란 무엇입니까?
NP- 완전 문제는 무엇입니까? 컴퓨터 과학에서 왜 그렇게 중요한 주제입니까?
답변
NP 는 비 결정적 다항식 시간을 나타냅니다 .
이는 비 결정적 튜링 기계 (일반적인 튜링 기계와 마찬가지로 비 결정적 “선택”기능 포함)를 사용하여 다항식 시간에 문제를 해결할 수 있음을 의미합니다. 기본적으로 솔루션은 폴리 타임 으로 테스트 할 수 있어야 합니다. 이 경우 수정 된 입력으로 주어진 문제를 사용하여 알려진 NP 문제를 해결할 수있는 경우 (NP 문제는 주어진 문제 로 축소 될 수 있음 ) 문제는 NP 완료입니다.
NP- 완전 문제에서 벗어나는 가장 중요한 것은 알려진 방법으로 다항식 시간으로 해결할 수 없다는 것입니다. NP-Hard / NP-Complete는 특정 클래스의 문제를 현실적으로 해결할 수 없다는 것을 보여주는 방법입니다.
편집 : 다른 사람들이 지적했듯이 NP-Complete 문제에 대한 대략적인 해결책이 종종 있습니다. 이 경우 근사 솔루션은 일반적으로 근사값이 얼마나 가까운지를 알려주는 특수 표기법을 사용하여 근사값을 제공합니다.
답변
NP 란 무엇입니까 ?
순이익은 모두의 집합입니다 의사 결정 문제 ‘yes’-답변이 될 수있는 (예스 또는 노 대답과 질문) 검증 다항식 시간 (O (n이 K ) 여기서 n은 문제의 크기이며, k는 A는 결정적 튜링 머신에 의해) . 다항식 시간이 때로는 정의로 사용되는 고속 또는 빠르게 .
P 란 무엇입니까 ?
P가 될 수있는 모든 결정 문제의 집합 인 해결 의 다항식 시간 a로 결정 튜링 기계 . 다항식 시간으로 풀 수 있으므로 다항식 시간으로도 확인할 수 있습니다. 따라서 P는 NP의 하위 집합입니다.
NP-Complete 란 무엇입니까 ?
NP에있는 모든 문제 x가 NP로 신속하게 (즉, 다항식 시간으로) 변환 될 수있는 경우에만 NP에있는 문제 x도 NP- 완료에 있습니다.
다시 말해:
- x는 NP에 있고
- NP의 모든 문제는 x 로 환원 가능
따라서 NP-Complete을 매우 흥미롭게 만드는 것은 NP-Complete 문제 중 하나를 신속하게 해결하면 모든 NP 문제를 신속하게 해결할 수 있다는 것입니다.
“P = NP 란 무엇입니까?” 게시물을 참조하십시오. 왜 그렇게 유명한 질문입니까?
NP-Hard 란 무엇입니까 ?
NP-Hard는 최소한 NP에서 가장 어려운 문제만큼 어려운 문제입니다. NP-Complete 문제도 NP-hard입니다. 그러나 NP접두사로 사용 하더라도 모든 NP-hard 문제가 NP (또는 의사 결정 문제) 인 것은 아닙니다 . 즉 NP-hard의 NP는 비 결정적 다항식 시간을 의미하지 않습니다 . 그렇습니다. 혼란 스럽지만 사용법이 변경되어 변경 될 가능성이 없습니다.
답변
NP-Complete은 매우 구체적인 것을 의미하므로주의해야합니다. 그렇지 않으면 정의가 잘못 될 것입니다. 첫째, NP 문제는 다음과 같은 예 / 아니오 문제입니다.
- 답이 “예”라는 “예”대답 또는 (동등한) 문제의 모든 인스턴스에 대해 다항식 시간 증명이 있습니다.
- 문제의 인스턴스에 대한 답변이 “예”인 경우 “예”라고 대답 할 확률이 0이 아닌 다항식 시간 알고리즘 (임의의 변수를 사용하는)이 있으며 100 %의 경우 “아니오”라고 표시합니다 대답은 ‘아니오.” 다시 말해, 알고리즘은 100 % 미만의 오 음율이어야하고 오 탐지가 없어야합니다.
문제 X는 NP- 완료
- X는 NP에 있고
- NP의 모든 문제 Y에 대해 Y에서 X 로의 “감소”가 있습니다. 다항식 시간 알고리즘은 Y의 인스턴스를 X의 인스턴스로 변환하여 Y 인스턴스에 대한 응답이 “예”인 경우에만 X- 인스턴스가 “예”인 경우
X가 NP- 완전하고 X의 모든 인스턴스를 올바르게 해결할 수있는 결정 론적 다항식 시간 알고리즘이 존재하면 (0 % 오탐, 0 % 오음) 결정 론적 다항식에서 NP의 모든 문제를 해결할 수 있습니다. 시간 (X로 감소).
지금까지 아무도 그러한 결정 론적 다항식 시간 알고리즘을 생각해 냈지만 아무도 존재하지 않는다는 것을 입증 한 사람은 없습니다 ( P = NP 문제입니다 ). 그렇다고 NP-Complete (또는 NP-Hard) 문제의 특정 인스턴스를 해결할 수 없다는 의미는 아닙니다. 정수 목록을 안정적으로 정렬하는 것과 같은 방식으로 문제의 모든 인스턴스에서 안정적으로 작동하는 것을 가질 수 없다는 것을 의미합니다. NP-Hard 문제의 모든 실제 사례에서 매우 잘 작동하는 알고리즘을 만들 수있을 것입니다.
답변
기본적으로이 세계의 문제는 다음과 같이 분류 될 수 있습니다.
1) 해결할 수없는 문제 2) 다루기 어려운 문제 3) NP 문제 4) P 문제
1) 첫 번째는 문제에 대한 해결책이 아닙니다. 2) 두 번째는 필요한 지수 시간입니다 (즉, 위의 O (2 ^ n)). 3) 세 번째는 NP라고합니다. 4) 네 번째는 쉬운 문제입니다.
P : 다항식 시간 문제의 해를 나타냅니다.
NP : 아직 다항식 시간을 참조하여 솔루션을 찾습니다. 다항식 시간 솔루션이 있는지 확실하지 않지만 일단 솔루션을 제공하면이 솔루션을 다항식 시간으로 확인할 수 있습니다.
NP Complete : 아직 다항식 시간으로 솔루션을 찾지 못했지만 다항식 시간으로 확인할 수 있습니다. NP의 NPC 문제는 더 어려운 문제이므로 NPC 문제에 대한 P 솔루션이 있음을 증명할 수 있으면 P 솔루션에서 찾을 수있는 NP 문제가 있습니다.
NP Hard : 다항식 시간이 아직 솔루션을 찾지 못했지만 다항식 시간으로 검증 할 수 없음을 나타냅니다. NP 하드 문제는 NPC 난이도를 능가합니다.
답변
NP-Complete은 일련의 문제입니다.
이 클래스 P는 다항식 시간에 해결할 수있는 문제로 구성됩니다 . 예를 들어, 상수 k에 대해 O (n k ) 로 풀 수 있습니다 . 여기서 n 은 입력 크기입니다. 간단히 말해 합리적인 시간에 실행되는 프로그램을 작성할 수 있습니다 .
이 클래스 NP는 다항식 시간 으로 확인할 수 있는 문제로 구성됩니다 . 즉, 우리가 잠재적 솔루션을 제공하면 주어진 솔루션이 다항식 시간에 올바른지 확인할 수 있습니다.
일부 예는 부울 만족도 (또는 SAT ) 문제 또는 해밀턴 사이클 문제입니다. NP 클래스에있는 것으로 알려진 많은 문제가 있습니다.
NP-Complete문제 수단 적어도 NP에 문제로 열심히.
NP의 문제가 NP-complete의 다른 문제 로 변환 될 수 있다는 것이 입증되었으므로 컴퓨터 과학에 중요합니다 . 즉, 하나의 NP- 완전 문제에 대한 해결책은 모든 NP 문제에 대한 해결 책임을 의미합니다.
보안의 많은 알고리즘은 NP 하드 문제에 대한 알려진 솔루션이 없다는 사실에 달려 있습니다. 솔루션이 발견되면 컴퓨팅에 큰 영향을 줄 것입니다.
답변
최적의 솔루션을 확보하기 위해 모든 가능성을 시뮬레이션해야하는 일련의 문제입니다.
일부 NP-Complete 문제에 대해 좋은 휴리스틱이 많이 있지만, 그들은 단지 교육받은 추측 일뿐입니다.
답변
NP- 완전 문제의 예를 찾고 있다면 3-SAT를 살펴보십시오 .
기본 전제는 결합 정규 형식 의 표현식을 사용 하는 것입니다. 이는 OR에 의해 결합 된 일련의 표현식이 모두 참이어야한다는 것을 의미합니다.
(a or b) and (b or !c) and (d or !e or f) ...
3-SAT 문제는 각 OR- 표현식이 정확히 3 개의 부울 값을 갖는 표현식을 만족시키는 솔루션을 찾는 것입니다.
(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...
이것에 대한 해결책은 (a = T, b = T, c = F, d = F) 일 수 있습니다. 그러나 일반적인 경우 다항식 시간에서이 문제를 해결하는 알고리즘이 발견되지 않았습니다. 이것이 의미하는 바는이 문제를 해결하는 가장 좋은 방법은 기본적으로 무차별 대입 추측 및 검사를 수행하고 작동하는 조합을 찾을 때까지 다른 조합을 시도하는 것입니다.
3-SAT 문제의 특별한 점은 모든 NP- 완전 문제를 3-SAT 문제로 줄일 수 있다는 것입니다. 즉,이 문제를 해결하기 위해 다항식 시간 알고리즘을 찾을 수 있다면 전 세계 컴퓨터 과학자와 수학자의 존경과 감탄은 말할 것도없이 $ 1,000,000 를 얻게 됩니다.
