문제가 NP 완료된 경우 NP 클래스에 속해야하며 NP 완료 문제로 줄이려면 다항식 시간 알고리즘이 있어야합니다.NP 완성을 위해 '다항식 시간에 문제를 줄여야한다'는 것이 강제적입니까?
이제 지수 감소 알고리즘 만 사용하면 어떻게 될까요? 이 문제는 여전히 NP 완성이라고 할 수 있습니까? 아니면 기존의 문제가 있습니까?
편집 : 또한 이러한 문제가 있는지 여부를 알려주고 어떤 클래스에 속하는지 여부를 알려주십시오.
Are such problems NP-complete?
번호 증명 :
하자
는 (적어도) 지수 시간 = B. "최소"로 감소 NP 완전 문제를 보자 문제 = A. 당신 때문에 기하 급수적 인 시간에 도달하거나 사소한 접근법을 따르는 사소한 일을 할 수있다. (더 효율적인 감축 전략이 존재하지 않는다는 것을 증명하기 위해 아마도 N! = NP, 현재까지는 해결되지 않았다).
B는 NP 완성이므로 "every problem in NP is reducible to B in polynomial time"입니다.
A가 NP에 있으면 다항식 시간이 B가되어야합니다. 그러나 NP가 아니기 때문에 NP가 아닙니다.
따라서 NP 완성이 될 수 없습니다.
간단히 말하면 NP의 모든 문제는 A만큼 어렵지 않아도되고 분명히 그렇지 않습니다. 세트 감안할 때
(가 스마트 사람이 있는가에 대해 나는 상관 없어 코멘트 나 2 개) (재귀 knapsack) :
Are there such problems?
나는이 이 같은 문제가있을 수 있습니다 생각 해요 최대 가중치 A를 갖는 부분 집합을 찾고, 또한이 부분 집합 내에서 일부 총 최대 가중치 C를 갖는 부분 집합을 찾고, 두 집합의 값의 합을 최대화하는 것을 목표로합니다.
To which class does it belong?
은 내가 특별히 이들의 이름이없는 확신 해요,하지만 난 많은 생각 (또는 전부를?) 그들 NP-hard이다의. 증명 : (적어도 위의 문제에 대해서는 그것이 그러한 문제라고 가정 할 때)
위의 예제가 이와 같은 문제이고 it = H라고 가정합시다. 우리는 상수 시간에 위를 해결할 수있는 오라클이 있다고 가정합니다. 그러나 배낭 문제는 단순히 위의 특수한 경우 (C = 0)이므로 오라클을 사용하여 일정 시간 (다항식 시간)에 배낭 문제를 풀 수 있습니다.
일반적으로이를 증명하는 것에 대해 확실하지 않습니다. 그러나 주어진 문제는 주어진 문제를 위의 문제로 줄이거 나 주어진 문제를 배낭 문제로 줄임으로써 해결 될 수 있습니다.
편집 : 실제로 이름이 2-EXPTIME 인 것 같습니다.
한 점 여기 나는 여기에 대해 확신 할 수 없다는 것은 지수 적 시간 문제가 폴리 시간 알고리즘으로 축소 될 수 없음을 증명하는 것이 어렵다는 것입니다. 사실 이것을 정확히 이해한다면 지수 시간 완전 문제는 다항식 시간으로 줄일 수없고 알려진 지수 시간 완전 문제 (http://en.wikipedia.org/wiki/EXPTIME)가있는 것으로 알려져 있습니다. –
@ user802500'for (i = 1 : n) {(n^n 시간 동안 원을 그리며); arr1 [i] = arr2 [i]; }'. 그게 내가 말하는거야. 당신이 ** ** 기하 급수적으로 어떤 일을 할 수 있다고해서 다항식 시간에 그것을 할 수있는 방법이 존재하지 않는다는 것을 의미하지는 않습니다. 그것은 본질적으로 전체 P = NP 질문이 내려지는 이유입니다. – Dukeling
다른 NP 문제를 다항식 시간으로 줄일 수있는 경우에만 NP 완전성을 고려할 수 있습니다. 이것이 유용한 정의 인 이유는 하나의 다항식 시간 알고리즘을 찾으면 자동으로 모든 NP 문제에 대해 하나의 알고리즘을 제공한다는 것입니다. 우리가 기하 급수적 인 시간 감축을 허용했지만, 감소 된 문제에 대한 다항식 시간 해결책을 찾았다면, 우리가 감축 한 문제를 해결하는 데 실제로 도움이되지 않을 것입니다.
희망이 도움이됩니다.
N? = NP와 그 질문이 함축하는 의미에 대해 언급하는 것이 좋을 것이다. – Dukeling
아마도 - 나는 그 지점에 빨리 도착한 짧은 대답을하려고했습니다. OP가 얻고 싶어하는 교육을받은 사람에 따라 다소 긴 답변이 더 나을 수도 있습니다. –
복잡성 이론의 완전성은 특정 종류의 감소 (항상 문맥에서 알 수 있으므로 명시 적으로 언급되지 않음)에 대해 항상 정의됩니다. NP- 완전 문제의 유명한 클래스는 Richard Rast의 답에 주어진 이유로 다항식 시간 단축에 대해 완전하다고 정의됩니다.
EXPTIME 감소에 대해 NP 완전 문제 클래스를 정의 할 수 있지만이 클래스는별로 흥미롭지 않습니다. 감소가 기하 급수적으로 허용되는 경우 원래 문제를 완전히 해결하고 대상 문제의 사소한 인스턴스를 생성 할 수 있습니다. 이것은 NP의 모든 문제가 그러한 유형의 감소에 의해 모든 다른 문제로 축소 될 수 있음을 의미하므로 NP의 모든 문제는 기하 급수적 인 시간 단축을 위해 NP 완전합니다.
짧은 버전 : 줄이기는 문제가 감소되는 클래스보다 약한 경우에만 흥미 롭습니다.
많은 이전에 언급했듯이 질문의 방향이 잘못되었습니다. 문제 A는 NP의 모든 문제 B가 문제 A에 대한 다항식 시간에서 감소 될 수 있다면 정의에 의해 NP 완성입니다. 따라서 귀하의 질문은 그 감소가 다항식이어야하며 기하 급수적 시간이 아닌지 여부입니다.
지수 시간 감축을 허용 한 경우 다음 결정 문제 X를 수행하십시오. "입력이 예"입니까? 그것은 거의 가능한 가장 단순한 의사 결정 문제입니다. 입력이 YES이면 대답은 YES이고, 입력이 예가 아니면 대답은 NO입니다. 그러나 NP의 모든 문제는 기하 급수적으로 문제 X로 줄일 수 있습니다. 분명히 우리는 문제 X를 "NP-complete"라고 부르고 싶지 않습니다. 그러므로 지수 적 시간 감소는 허용되지 않기 때문에 "NP-complete"라는 용어는 완전히 의미가 없기 때문에 허용되지 않습니다.
이것은 http://cstheory.stackexchange.com/에 속합니다. – raven
사실, cstheory는 연구 수준의 질문입니다 (나는 이것이 불행하다고 생각하지만, 그것이 그렇습니다). 따라서이 질문은 거기에서 적절하지 않을 것입니다. –
축소 방향이 잘못되었습니다. 그것은 NP에 있어야하며 알려진 NP 완전한 문제는 *로 줄여야합니다. –