정의 SAT2016 = {\ phi | \ phi는 최대 2016 개의 절이있는 CNF 공식}입니다. P \ neq NP라고 가정하면 SAT2016 NP가 완성 되었습니까?계산 가능성 : 제한된 수의 절이있는 SAT 수식
각 절의 리터럴 수는 한정되어 있지 않으므로 절 수에 상수가있는 수식의 적합성을 검사하는 다항 시간 알고리즘이 있는지 여부가 즉시 명확하지 않습니다.
귀하의 아이디어를 환영합니다.
SAT2016는 모든 조항의 문자 하나 이상에 1을 할당 할 수있는 식을 만족하기 위해 그 사항을 준수 P.
에입니다. 각 절에는 최대 2n 개의 리터럴이 포함됩니다. 따라서 모든 절에서 하나의 리터럴을 선택하는 방법의 수는 많아야 (2n)^2016입니다. 수식이 만족 스러운지 알아 내려면 (2n)^2016 개의 가능성 (모든 절에서 하나의 리터럴을 선택)을 반복하고 합법적 인 경우 각 가능성을 확인해야합니다. 즉, 2016 리터럴 (각 절에서 하나씩)의 각 선택 항목에 대해 2016 리터럴 중 2 개가 특정 변수 및 부정이 발생했는지 확인해야합니다. 이 경우 다음 2016 리터럴로 이동합니다. (2n)^2016 가능성을 모두 살펴본 결과 모두 충돌이있는 것으로 밝혀지면 수식이 만족스럽지 않다고 결론 내릴 수 있습니다.
최대 (2n)^2016 개의 가능성이 있으므로 주어진 가능성을 검사하는 데 일정한 시간이 걸리므로 알고리즘의 실행 시간은 다항식 인 입니다.