컴퓨터 과학의 NP- 완성은 무엇입니까?

Question

NP- 완료 문제는 무엇입니까? 컴퓨터 과학에서 왜 그렇게 중요한 주제입니까?

Answer 1

NP 의지합니다 비 결정적 다항식 시각.

이는 문제가 비 결정적 튜링 머신 (일반 튜링 기계와 같은 비 결정적 "선택"기능을 포함하여 다항식 시간에 해결 될 수 있음을 의미합니다. 기본적으로 솔루션이 있어야합니다 테스트 가능 폴리 시간에. 이 경우, 알려진 NP 문제는 수정 된 입력으로 주어진 문제를 사용하여 해결할 수 있습니다 (NP 문제는 줄인 주어진 문제에) 문제는 NP가 완료됩니다.

NP- 완료 문제에서 벗어나야 할 가장 중요한 것은 알려진 방식으로 다항식 시간에 해결할 수 없다는 것입니다. NP-HARD/NP-Complete는 특정 클래스의 문제가 현실적인 시간에 해결할 수 없음을 보여주는 방법입니다.

편집 : 다른 사람들이 지적했듯이, 종종 NP- 완료 문제에 대한 근사 솔루션이 있습니다. 이 경우 근사 솔루션은 일반적으로 근사치가 얼마나 가까운 지 알려주는 특수 표기법을 사용하여 근사 경계를 제공합니다.

Answer 2

무엇인가요 NP?

NP는 모든 것입니다 의사 결정 문제 '예'-답변이 확인 다항식 시간 (O (n^케이) 어디 N 문제 크기입니다 케이 a 결정 론적 튜링 머신. 다항식 시간은 때때로 정의로 사용됩니다 빠른 또는 빠르게.

무엇인가요 피?

P는 모든 결정 문제의 세트입니다. 해결되었습니다 안에 다항식 시간 a 결정 론적 튜링 머신. 다항식 시간에 해결 될 수 있기 때문에 다항식 시간에도 검증 될 수도 있습니다. 따라서 P는 NP의 서브 세트입니다.

무엇인가요 NP- 완성?

NP에있는 문제 X도 NP- 완성되어 있습니다. 경우에만 NP의 다른 모든 문제는 빠르게 (즉, 다항식 시간에) x로 변환 될 수 있습니다.

다시 말해:

1. X는 NP에 있습니다
2. NP의 모든 문제입니다 환원 가능 x

그래서, 무엇을 만드는 것 NP- 완성 흥미로운 것은 NP- 완료 문제 중 하나가 빠르게 해결 되었다면 NP 문제는 빠르게 해결 될 수 있습니다.

게시물도 참조하십시오 "P = NP?"란 무엇이며 왜 그렇게 유명한 질문입니까?

무엇인가요 NP-HARD?

NP-HARD는 NP에서 가장 어려운 문제만큼 어려운 문제입니다. NP- 완료 문제도 NP-HARD입니다. 그러나 모든 NP- 하드 문제가 NP (또는 결정 문제)가 아닙니다. NP 접두사로. 이것이 NP-Hard의 NP입니다 비 결정적 다항식 시간. 그렇습니다. 이것은 혼란 스럽지만 사용법은 확고하고 변경되지 않을 것입니다.

Answer 3

NP- 완성은 매우 구체적인 것을 의미하며 조심해야합니다. 그렇지 않으면 정의가 잘못됩니다. 첫째, NP 문제는 예/아니오 문제입니다.

1. "예"대답의 모든 인스턴스에 대한 다항식 시간 증거가 있습니다. 답은 "예"또는 (동등하게)
2. 문제의 인스턴스에 대한 답변이 "예"인 경우 "예"에 대한 대답 할 확률이 0이되지 않는 다항식 시간 알고리즘 (임의 변수를 사용하여 가능성)이 존재하며 "아니오"라고 말할 것입니다. 내 대답은 아니오 야." 다시 말해, 알고리즘은 100% 미만의 거짓 음성 속도를 가져야하며 오 탐지가 없어야합니다.

문제 X는 np-complete if입니다

1. X는 NP에 있습니다
2. NP의 모든 문제의 경우 y에서 x 로의 "감소"가 있습니다. 답변 x- 인스턴스가 "예"인 경우.

X가 NP- 완성되고 결정 론적, 다항식 시간 알고리즘이 존재하는 경우 X의 모든 인스턴스를 올바르게 해결할 수있는 다항식 시간 알고리즘이 존재한다면 (0% False-Positives, 0% False-Negatives) NP의 모든 문제는 결정 론적으로 결정적으로 해결할 수 있습니다. 시간 (x로 축소).

지금까지 아무도 그런 결정 론적 다항식 시간 알고리즘을 생각해 본 사람이 없지만 아무도 존재하지 않는다는 것을 증명 한 사람은 아무도 없습니다 (누구나 할 수있는 사람에게는 백만 달러가 있습니다. P = NP 문제). 그렇다고해서 NP- 완성 (또는 NP-HARD) 문제의 특정 인스턴스를 해결할 수 없다는 의미는 아닙니다. 그것은 단지 당신이 정수 목록을 안정적으로 정렬 할 수있는 것과 같은 방식으로 문제의 모든 사례에서 안정적으로 작동 할 무언가를 가질 수 없다는 것을 의미합니다. NP- 하드 문제의 모든 실질적인 사례에서 잘 작동하는 알고리즘을 만들 수 있습니다.

Answer 4

NP- 완성은 일련의 문제입니다.

클래스 P 해결할 수있는 문제로 구성됩니다 다항식 시간. 예를 들어, 그들은 O (n^케이) 일부 상수 K의 경우, 어디에 N 입력의 크기입니다. 간단히 말해서, 당신은 실행되는 프로그램을 쓸 수 있습니다. 합리적인 시각.

클래스 NP 그 문제로 구성됩니다 증명할 수 있는 다항식 시간에. 즉, 잠재적 인 솔루션이 주어지면 주어진 솔루션이 다항식 시간에 올바른지 확인할 수 있습니다.

일부 예는 부울 만족도 (또는 수능) 문제 또는 해밀턴주기 문제. 클래스 NP에있는 것으로 알려진 많은 문제가 있습니다.

NP-Complete 문제는 있다는 것을 의미합니다 적어도 NP의 문제만큼 어려운 것입니다.

NP의 모든 문제가 될 수 있기 때문에 컴퓨터 과학에 중요합니다. 변형 NP- 완성의 또 다른 문제로. 즉, 하나의 NP- 완료 문제에 대한 해결책은 모든 NP 문제에 대한 해결책이라는 것을 의미합니다.

보안의 많은 알고리즘은 NP 어려운 문제에 대해 알려진 솔루션이 존재하지 않는다는 사실에 달려 있습니다. 솔루션이 발견되면 컴퓨팅에 큰 영향을 미칩니다.

Answer 5

기본적 으로이 세계의 문제는 다음과 같이 분류 할 수 있습니다

1) 해결할 수없는 문제 2) 다루기 어려운 문제 3) NP-PROBLEM 4) P-PROBLEM

---

1) 첫 번째는 문제에 대한 해결책이 아닙니다. 2) 두 번째는 지수 시간이 필요하다 (즉, 위의 O (2 ^ n)). 3) 세 번째는 NP라고합니다. 4) 네 번째는 쉬운 문제입니다.

---

P : 다항식 시간의 문제에 대한 해결책을 말합니다.

NP : 해결책을 찾지 못한 다항식 시간을 말합니다. 다항식 시간 솔루션이 없음을 확신하지 못하지만 일단 솔루션을 제공하면이 솔루션은 다항식 시간에 검증 될 수 있습니다.

NP 완료 : 다항식 시간을 말하면 아직 해결책을 찾지 못했지만 다항식 시간에 확인할 수 있습니다. NP의 NPC 문제는 더 어려운 문제이므로 NPC 문제에 대한 P 솔루션이 있음을 증명할 수 있다면 P 솔루션에서 찾을 수있는 NP 문제가 있습니다.

NP Hard : 다항식 시간은 아직 해결책을 찾지 못했지만 다항식 시간에 확인할 수는 없습니다. NP 하드 문제는 NPC 난이도를 능가합니다.

Answer 6

그것은 우리가 최적의 솔루션을 가지고 있는지 확인하기 위해 모든 가능성을 시뮬레이션 해야하는 일련의 문제입니다.

일부 NP- 완성 문제에 대한 좋은 휴리스틱이 많이 있지만, 교육받은 추측 일뿐입니다.

Answer 7

NP- 완료 문제의 예를 찾고 있다면 살펴 보는 것이 좋습니다. 3-SAT.

기본 전제는 표현이 있다는 것입니다 결합 정상 형태, 이는 ORS가 결합 한 일련의 표현이 모두 사실이어야한다고 말하는 방법입니다.

(a or b) and (b or !c) and (d or !e or f) ...

3-SAT 문제는 각각의 표현이 정확히 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, 전 세계의 컴퓨터 과학자와 수학자들의 존중과 존경은 말할 것도 없습니다.

Answer 8

솔직히, 위키 백과 이것에 대한 답을 찾기에 가장 좋은 곳일 수 있습니다.

NP = P라면, 우리는 이전에 생각했던 것보다 훨씬 더 어려운 문제를 훨씬 빨리 해결할 수 있습니다. P (다항식) 시간에 하나의 NP- 완료 문제 만 해결하면 NP- 완료 범주의 다른 모든 문제에 적용될 수 있습니다.

Answer 9

알고리즘과 문제를 분리해야합니다. 우리는 문제를 해결하기 위해 알고리즘을 작성하고 특정 방식으로 확장합니다. 이것은 단순화이지만 스케일링이 충분하다면 'P'가있는 알고리즘에 레이블을 지정하고 그렇지 않은 경우 'NP'라벨을 붙이십시오.

우리가 해결하려는 문제에 대해 우리가 해결하기 위해 사용하는 알고리즘보다는 우리가 해결하려는 문제에 대해 아는 것이 도움이됩니다. 따라서 잘 스케일링 알고리즘이있는 모든 문제는 "P"라고 말할 것입니다. 그리고 스케일링 알고리즘이 열악한 것은 "NP"입니다.

즉, 간단한 문제를 해결하기 위해 나쁜 알고리즘을 작성할 수 있기 때문에 많은 간단한 문제가 "NP"라는 것을 의미합니다. NP의 어떤 문제가 정말 까다로운 문제인지 아는 것이 좋을 것입니다. 그러나 우리는 단지 "우리가 좋은 알고리즘을 찾지 못한 것"이라고 말하고 싶지 않습니다. 결국, 나는 슈퍼 amazing 알고리즘이 필요하다고 생각하는 문제 (x라고 함)를 생각해 낼 수 있습니다. 나는 세상에 X 스케일을 잘못 해결하기 위해 내가 생각해 낼 수있는 최고의 알고리즘을 세상에 말하면 X가 정말 힘든 문제라고 생각합니다. 그러나 내일, 나보다 영리한 누군가가 X를 해결하고 P에있는 알고리즘을 발명 할 수도 있습니다. 따라서 이것은 어려운 문제에 대한 좋은 정의가 아닙니다.

동일하게 NP에는 아무도 좋은 알고리즘을 모르는 많은 문제가 있습니다. 그래서 내가 할 수 있다면 입증하다 그 X는 특정 종류의 문제입니다. X를 해결하기위한 좋은 알고리즘이 또한 로터리 방식으로 사용하여 좋은 알고리즘을 제공합니다. 모든 NP의 다른 문제. 이제 사람들은 X가 진정으로 까다로운 문제라고 조금 더 확신 할 수 있습니다. 그리고이 경우 우리는 x np-complete를 호출합니다.

Answer 10

위의 NP 완전한 문제에 대한 정의는 정확하지만 아직 아무도 그 문제를 해결하지 못했기 때문에 철학적 중요성에 대해 서정적 일 수 있다고 생각했습니다.

당신이 나올 거의 모든 복잡한 문제는 NP가 완료됩니다. 이 수업에는 매우 근본적인 것이 있으며, 이는 쉽게 해결할 수있는 문제와 계산적으로 다른 것 같습니다. 그들은 자신의 맛을 가지고 있으며, 그들을 인식하기는 어렵지 않습니다. 이것은 기본적으로 적당히 복잡한 알고리즘이 정확하게 일정, 최적화, 포장, 덮개 등을 해결하는 것이 불가능하다는 것을 의미합니다.

그러나 발생하는 문제가 NP가 완료되면 모든 것이 손실되지는 않습니다. 사람들이 근사 알고리즘을 연구하는 광대하고 매우 기술적 인 분야가있어 NP 완전한 문제의 솔루션에 가깝게 보장 할 수 있습니다. 이들 중 일부는 엄청나게 강력한 보증입니다. 예를 들어 3SAT의 경우 정말 명백한 알고리즘을 통해 7/8 보증을받을 수 있습니다. 더 나은 것은 실제로 매우 강력한 휴리스틱이 있으며,이 문제에 대한 훌륭한 답변을 제공하는 데 탁월합니다 (그러나 보증은 없습니다!).

그래프 등 동형 및 인수는 P 또는 NP 인 것으로 알려져 있지 않습니다.

Answer 11

"NP- 완전성은 아마도 알고리즘 연구에서 더 수수께끼의 아이디어 중 하나 일 것입니다."NP "는"비 결정적 다항식 시간 "을 의미하며 복잡성 클래스가 불리는 이름입니다. 어떤 문제에 속할 수 있는지. NP 복잡성 클래스는 해당 클래스의 문제가 될 수 있다는 것입니다. 확인 다항식 시간 알고리즘으로. 예를 들어, 물건을 세는 문제를 고려하십시오. 테이블에 사과가 많이 있다고 가정하십시오. 문제는 "얼마나 많은 사과가 있습니까?"입니다. 가능한 답변이 제공됩니다. 사과를 세는 것은 각 사과를 계산하는 데 한 단계가 걸리기 때문에 O (n) (큰 표기법)에서 발생합니다. N 사과의 경우 N 단계가 필요합니다. 이 문제는 NP 복잡성 클래스에 있습니다.

문제는 다음과 같이 분류됩니다 NP- 완성 그것이 둘 다를 보여줄 수 있다면 NP-HARD 그리고 증명할 수 있는 다항식 시간에. NP-HARD에 대한 논의에 너무 깊이 들어 가지 않고, 다항식 시간 솔루션이 발견되지 않은 특정 문제가 있다고 말하면 충분합니다. 즉, N과 같은 것이 필요합니다! (n 요인) 그들을 해결하기위한 단계. 그러나 NP- 완료 문제에 대한 해결책이 주어지면 다항식 시간에 확인할 수 있습니다.

NP- 완료 문제의 전형적인 예는 여행 세일즈맨 문제입니다. "

저자 : ApoxyButt From : http://www.everything2.com/title/np-complete

Answer 12

NP 문제 :-

1. NP 문제는 비 결정적 다항식 시간에 해결할 수있는 문제입니다.
2. 비 결정적 알고리즘은 2 단계에서 작동합니다.
3. 비 결정적 추측 단계 && 비 결정적 검증 단계.

NP 문제의 유형

1. NP 완료
2. NP 하드

NP 완전한 문제 :-

1 결정 문제 a는 두 가지 속성을 따르는 경우 NP를 완료합니다.

1. 클래스 NP에 속합니다.
2. NP의 다른 모든 문제는 다항식 시간에 p로 변환 될 수 있습니다.

일부 예 :-

• 배낭 문제
• 서브 세트 합계 문제
• 정점을 덮는 문제

Answer 13

NP- 완료 문제는 각각의 다른 NP- 프로 블렘이 다항식 시간에 감소 될 수 있으며, 그 용액이 다항식 시간에 여전히 검증 될 수있는 일련의 문제입니다. 즉, 모든 NP 문제는 NP- 완성 문제로 변환 될 수 있습니다. -비공식적으로, NP- 완료 문제는 NP의 다른 문제와 마찬가지로 적어도 "힘든"NP 문제입니다.

Answer 14

NP 문제는 솔루션을 검증하는 컴퓨터 알고리즘이 다항식 시간에 생성 될 수있는 문제입니다.

NP- 완료 문제는 NP이지만 다항식 시간 (p라고 함)에 해결할 수 있다면 모든 NP 문제는 P입니다.

그러니 갈라지기.