[전산학특강] 전산학특강 - 7
TQBF 문제 – 완전히 양자화된 부울 수식 f가 주어졌을 때, 어떻게 f가 TQBF의 멤버인지 (즉, f가 참인지) 판별할 수 있을까? 주어진 QBF에 대하여 TQBF (즉, 참)인지 여부를 결정하기 위한 간단한 재귀 알고리즘이 있습니다. \[ Q_1x_1Q_2x_2...Q_nx_n\phi(x_1, x_2,..., x_n) \] 수식에 양자자가 없으면 수식을 그대로 반환할 수 있습니다. 그렇지 않으면 첫 번째 양자자를 제거하고 첫 번째 변수에 대한 두 가능한 값을 모두 확인합니다: \[ A = Q_2x_2...Q_nx_n\phi(0, x_2,..., x_n) \] \[ B = Q_2x_2...Q_nx_n\phi(1, x_2,..., x_n) \] \[ Q_1 \]이 \[ \exists \] (있다면)이..
