2-CNF가 NP 완전하지 않다는 것을 어떻게 증명할 수 있습니까?

2-CNF가 NP-hard 또는 NP가 아닌 것을 어떻게 보여줄 수 있는지 알고 싶습니다. 이 점에서 누구든지 나를 도울 수 있습니까? 나는 해결책을 급히 필요로한다.2-CNF가 NP 완전하지 않다는 것을 어떻게 증명할 수 있습니까?

2013-02-20 afrin mun

이 숙제가 있습니까? –

미리 결정된 수의 단계에서 수행 할 수 있으면 NP 하드 또는 NP 완료가 아닙니다. – Achrome

cstheory.stackexchange.com을 시도해보십시오. 그러나 먼저 약간의 노력을 보여주십시오. – geoffspear

2-CNF 만족도는 P에있는 것으로 알려져 있습니다. 따라서 NP 완전하지 않다는 것을 증명할 수 있다면 P ≠ NP입니다. 따라서 아무도 이것을 증명할 수있는 방법을 알지 못합니다.

2013-02-21 10:24:25

답변