"A 문제가 NP 완료되면 A를 풀 수있는 비 결정적 다항식 시간 알고리즘이 있습니다"라는 서적에 쓰여 있습니다. 그러나 NP에 대한 '예'- 답을 알기까지는 완전한 문제가 다항식 시간에 "검증"될 수 있습니다. 나는 정말로 혼란 스럽다. 비 결정적 다항식 시간 알고리즘을 사용하여 NP 완전 문제를 "해결"할 수 있습니까?
문제 X가 NP-Complete임을 보여주는 방법을 알고 있습니다. X ∈ NP로 표시합니다. 표시 Y ≤ p X : NP 완료로 알려진 Y를 다항식 시간으로 X로 줄일 수 있습니다. 그러나 에 붙어 있는데, 왜이 절차는 X가 NP 완료임을 증명합니다. 누군가 비교적 간단한 방법으로 이것을 설명 할 수 있습니까?
시간 간격의 목록이 주어지면 최대 겹치지 않는 간격의 집합을 찾아야합니다. 예를 들어 , 우리는 다음 간격이있는 경우 : [0600, 0830], [0800, 0900], [0900, 1100], [0900, 1130],
[1030, 1400], [1230, 1400]
또 그것이 소정 시간 [0000, 2400] 범위에 있어야한다. 최대 겹치지 않는
NP가 완료된 파티션 문제의 변형 인 문제가 있습니다. 이것은 최적화 문제이며 의사 결정 문제는 아닙니다. 문제 : 합계의 차이가 최소가되도록 두 개의 하위 집합으로 숫자 목록을 분할하고 두 개의 하위 집합을 찾습니다. n이라도 맞으면 크기는 n/2이어야하며 이상한 경우 floor[n/2] 및 ceil[n/2]이어야합니다. 의사 다항식 시간 DP 알고리즘이
예를 들어, 세트 - 커버 결정 문제는 NP 완전 문제로 알려져 있습니다. 이 문제의 입력은 우주 U, U의 부분 집합의 가족 S 및 정수 k()입니다. 내가 혼란스러워하는 한 가지는 k = 1이라고하면, S의 각 요소를 간단히 검사하여 시간 | S |에서 문제를 풀 수 있다는 것입니다. 일반적으로 k가 상수 일 때 , 문제는 | S |의 다항식 시간으로
나는 P, NP, NP-Complete 및 NP-Hard를 직관적 인 방식으로 랩핑하려고 노력하고있어 그 정의를 기억할 필요가 없습니다. 다음 이미지 (왼쪽 시나리오, P! = NP)에는 NP-Complete와 NP-Hard 사이에 겹치는 영역이 있습니다. 일부 문제는 NP-Complete 및 NP-Hard라는 것을 의미합니까? 나는이 모순 된 대답을 발견
유명한 게임 흐름에서 문제를 해결할 방법을 찾으려고했습니다. http://moh97.us/flow/ Google 검색 결과 NP 완성 문제임을 알게되었습니다. 좋은 해결책은 경험적 방법과 상처를 사용하는 것입니다. 어떻게 NP 완전 문제를 쉽게 발견 할 수 있습니까? 때로는 차단할 때 명백한 해결책을 볼 수 없습니다. NP 완료와 함께 이런 일이 발생하면
wiki에 따르면 (N-1)! N 개의 도시와 함께 투어를 계산할 수 있습니다. 나는 더 나은 방법을 찾았지만 수학을 통해 내가 그것을 얼마나 향상 시켰는지 계산할 수는 없다. 나는 내 가정용 PC에서 1 시간 이내에 20 개 도시지도를 해결할 수 있다고 말할 수 있습니다. 20! = 2.43290200e + 18. 내가 한 일은 다음과 같습니다. 브로트