MAX 3 SAT는 NP 완결인가 아니면 NP 완수인가?

Question

이 문제에 대해 많은 상충되는 정보가 있습니다. 일부 말하기 사이트에서는 NP 완성형이며 다른 사람들은 그것이 공동 NP 완료 형이라고 말합니다. 내가 찾을 수있는 진정한 일관성있는 정보는 확실히 NP 하드입니다. 무엇 이니? 그리고 왜?

Answer 1

MAX-3SAT 정의 방법에 따라 다릅니다.

함수 문제로 "3CNF 공식을 사용하여 만족 절점을 최대화하는 변수 할당을 생성"으로 MAX-3SAT를 정의하면 NP 완료 또는 공동 NP 완료가 아닙니다. NP와 공동 NP는 의사 결정 문제의 부류이므로 어떤 기능 문제도 그들에게 속할 수 없다. 따라서 MAX-3SAT는 NP 또는 co-NP에 속할 수 없기 때문에 두 클래스 모두에서 완전한 문제가 될 수 없습니다. 이 함수 문제는 바닐라 3SAT로부터의 감소를 통해 NP 하드입니다. 최대 만족스러운 할당을 찾을 수 있다면 모든 절이 만족되었는지를 확인하여 원래 수식이 만족 스러운지 확인할 수 있습니다.

또한 "3CNF 공식 및 숫자 n이 주어지면 적어도 n 개의 절을 참으로 만드는 수식에 대한 변수 할당이 있는지 여부를 결정할 때 결정 문제로 MAX-3SAT를 정의 할 수 있습니다." 이것은 분명히 NP에 있고 NP 완성은 3SAT로부터의 감소를 통해 이루어진다.

반면에 "3CNF 공식과 해당 수식에 대한 변수 할당이 주어지면 MAX-3SAT는 만족 된 조항의 수를 최대화하는 과제입니까?"라는 결정 문제로 정의하면? co-NP에 속한다 (대답이 '아니오'인 경우, 더 만족스러운 과제를 제시함으로써이를 확인할 수있다). 나는 NP-hard인지 확실치 않지만, NP-hard 인지도 확신 할 수 없다.

희망이 도움이됩니다.