만족성을 확인하기위한 알고리즘

Question

SAT가 NP에 있음을 증명하기 위해 다항식 시간 (알고리즘)을 일으켜야합니다.요리사 Levin 정리는 비 결정적 튜링 기계를 사용하지만 그것이 내가 찾고있는 것이 아닙니다.

알고리즘의 아이디어는 값을 넣고 대답을 계산하는 것일 수 있습니다.그런 다음 답변이 1인지 여부를 확인합니다.그러나 '값을 넣는 것'부분에 psuedocode를 쓸 수있는 방법을 이해할 수 없으며 확실히 다항식이라는 것을 보여줍니다.

if x = 1:
 accept
else:
 reject

.

이것은 O (1) 일 수 있습니다.그러나 나머지 부분은 무엇입니까?

Answer 1

여기서 내가 어떻게 할 것인가 :

algo : DNF-SAT 문제의 검증자가 폐쇄 배열 및 리터럴의 부울에 대한 가능한 매핑 가능 입력 :
클로저 배열 : [ $ C_1 $ , $ C_2 $ , ..., $ C_M $ ] 여기서 $ C_J \ SUBETEQ \ {X_1, ..., x_n, \nneg x_1, ... \nneg x_n \} $
(인증서) 배열 $ m $ 여기서 $ m_i $ 은 리터럴 $ x_i $
출력 : true 또는 false

for $i = 1$ to $m$:
  value = true
  for literal in $C_i$:
    if literal == $x_i$:
      value = value or $M[i]$:
    else if literal == $\neg x_i$:
      value = value or (not $M[i]$)
  if not value:
    return false
return true 

.

참고 : 수학 표기법이 들여 쓰기되고 흔히 의사 코드 슬프게도 SADLY CS StaCkexchange는 그것을 지원하지 않습니다