이 언어가 NP입니까?

Question

L={[G, K] | G is a simple undirected graph with no simple path longer than k} 

(또한 Co-NP인가)?

나는 이것이 NP라고 생각합니다. E는 그래프에 대한 에지리스트이고, K는 제공된 경로 (G, E, K) G 그래프이다 검증기는이다

V : I는 다음했던 검증을 제공 할 수있다 .

먼저 경로가 유효한지 확인하십시오. 둘째, 지정된 경로보다 긴 경로에 대해 검색을 시작하십시오. 있는 경우 을 다항식 시간으로 찾을 수 있습니다. 그러나이 경우 이 무향 그래프이기 때문에 아무 것도없는 경우 시간이 무한대인지 확인할 수 있으므로이 문제는 NP-Hard가됩니다.

내 생각 프로세스의 결함은 어디에 있습니까?

Answer 1

문제 L의 보수, L ', 호출하면 G 간단한 경로를 포함 않는다 그래프 G = (V, E) 및 정수 K 주어`이다 길이가 적어도 k + 1 ''이며 이는 잘 알려진 LONGEST-PATH 문제입니다. 문제가 L '에 분명히 있습니다 NP : 그냥 하나 있다고 가정하고 경로를 추측하십시오. (등가 경로 주어진 그냥 길이 실제로 적어도 K + 1인지 확인.) 문제가 보완 에서 NP 경우에만, 에 CONP 유의,가되어 L 의미 coNP.

는 LONGEST-PATH 때문에 - 완전한 NP, L은 에 않는 CONP = NP NP하지 않다. (우리가 CONP를! = 믿기 때문에 NP이 더 NP - 완전한 문제가 CONP에 속할 수없는 의미와 더 CONP - 완전한 문제는 NP에 속할 수 있습니다. 자세한 내용은 Arora-Barak book를 참조하십시오.)