에서 이 질문에 , 그것은 쌀의 정리의 설명 복잡성 버전이 있다는 것을 언급했다. 나는 다음 정리의 증거를 발견했다.

복잡성 수준을 감안할 때 C 에서 언어의 사소 특성 C가 계산 될 수없는 C

나는 이전에 내가 찾은 증거를 게시했지만, 너무 길었고이 논문이 이미 그 정리에 대한 증거를 포함하고 있다는 의견에서 지적 되었기 때문에 제거했다. (어떤 이유로 든 내 증거를보고 싶어하는 경우이 질문의 이전 개정판을 참조하십시오.)

이 정리가 AC0과 PSPACE를 분리하는 데 사용될 수 있는지에 관심이 있습니다. 다음과 같은 주장이 있습니다.

다음과 같이 정의 된 복잡성 클래스 AC0 의 특성 P 를 고려하십시오 .

P : 특정 고정 구조, 즉 하나의 요소, 함수, 상수 및 관계가없는 구조를 허용하는 FO 쿼리의 속성

분명히, 상기 정리에 의해, P 는 AC0에서 결정될 수 없으며; FO 쿼리의 사소한 속성입니다.

그러나, FO 질의가 그러한 간단한 구조를 수용하는지 아닌지를 계산하는 것이 TQBF만큼 쉽게 결정될 수 있음을 약간의 조사가 보여 주어야한다. 따라서 P 는 PSPACE에서 결정할 수 있습니다.

이 점을 명확하게하기 위해 ( P 는 PSPACE에서 계산 가능함) : 우리가 관심있는 특성은 구조가 FO 여야한다는 점에 유의하십시오. 따라서 관계없이 단일 요소 구조에서 실행되는 FO 쿼리가 허용되는지 확인하려고합니다. 처리 할 관계가 없기 때문에 이러한 FO 쿼리를 결정하는 작업은 TQBF 인스턴스를 결정하는 것과 동일합니다. 관계가 없기 때문에 남아있는 유일한 과제는 정량화 된 부울 공식이 참인지 여부를 평가하는 것입니다. 이것은 기본적으로 단지 TQBF이므로 PSPACE에서 P 는 계산 가능합니다.

때문에 P는 AC0 PSPACE에 있지만 계산할 수있다, 우리는 AC0! = PSPACE을 체결 할 수 있어야한다. 이 추론이 맞습니까? 아니면 어딘가에서 실수를 했습니까? 특히 이전 단락에 대해 우려하고 있습니다. 나는 박람회에 대해 조금 더 생각할 기회를 얻은 후에 내일 논쟁을 명확히하고 업데이트하려고 노력할 것이다.

필자가 설명한 단일 요소의 관계없는 구조를 계산할 때 TQBF의 인스턴스로 분명히 이해되지 않는 FO 쿼리의 예를 대답으로 받아 들일 것입니다. (나는 존재하지 않는다는 것을 제안하고 있으므로, 존재하는 것을 보여줄 수 있다면 반대의 예가 될 것입니다.)

감사.

답변