나는 그것이 # P-Space라고 불릴 것 같지만 그것을 모호하게 언급 한 기사를 하나만 발견했다. EXP-SPACE-Complete 문제뿐만 아니라 EXP-TIME-Complete, NEXP-Complete의 계산 버전은 어떻습니까? Toda의 정리와 같은 포함 또는 제외 유형과 관련하여 인용 할 수있는 이전 연구가 있습니까?
답변
부울 수식에 만족할만한 할당 수는 수식의 유효한 수량화 수와 같습니다. 귀납적 증거는 매우 우아합니다. 따라서 #P = #PSpace.