PSPACE-완전

PSPACE-complete

계산 복잡도 이론에서, 결정 문제는 입력 길이(다항식 공간)에서 다항식인 메모리를 사용하여 풀 수 있고 다항식 공간에서 풀 수 있는 다른 모든 문제가 다항식 시간 내에 PSPACE-완전이다.PSPACE-완전한 문제는 PSPACE에서 가장 어려운 문제, 다항식 공간에서 해결할 수 있는 결정 문제의 클래스로 생각할 수 있습니다. 왜냐하면 그러한 문제에 대한 해답은 PSPACE에서 다른 문제를 쉽게 해결할 수 있기 때문입니다.

PSPACE-complete로 알려진 문제에는 정규 표현과 상황에 맞는 문법의 특성 결정, 정량화된 부울 공식의 진실성 결정, 조합 최적화 문제의 해결책 간의 단계적 변화, 많은 퍼즐과 게임이 포함됩니다.

이론.

문제는 다항식 메모리량(PSPACE에 속함)을 사용하여 해결할 수 있고 PSPACE 내의 모든 문제가 다항식 시간에 주어진 문제의 [1]동등한 인스턴스로 변환될 수 있는 경우 PSPACE-완전이라고 정의됩니다.

PSPACE-완전 문제는 더 유명한 복잡도 클래스 P(다항식 시간)와 NP(비결정론적 다항식 시간)를 벗어나는 것으로 널리 의심되지만,[2] 이는 알려지지 않았다.입력크기의 로그에서 NC의 문제는 공간다항식의 양으로 풀 수 있고, 공간계층정리에 의해 공간다항식의 양으로 풀 수 있는 문제의 종류가 PSPACE에 엄밀하게 포함되어 있기 때문에 고효율 병렬 알고리즘의 문제 클래스인 클래스 NC 밖에 있는 것으로 알려져 있다..

PSPACE 완전성을 정의할 때 일반적으로 고려되는 변환은 다항식 시간 다원 감소이며, 한 유형의 문제의 단일 인스턴스를 다른 유형의 동등한 단일 인스턴스로 변환합니다.그러나 튜링 감소를 사용하여 완전성을 정의하는 것도 가능하며, 여기서 한 문제는 다른 문제에 대한 서브루틴에 대한 다항식 호출 수로 해결될 수 있다.이러한 두 가지 유형의 감소가 다른 클래스의 PSPACE-완전 [3]문제로 이어질지는 알려지지 않았습니다.변환된 입력의 길이를 항상 증가시키는 다원 감소와 같은 다른 유형의 감소도 [4]고려되었다.

PSPACE-완전 집합에 대한 Berman-Hartmanis 추측의 버전은 이러한 집합이 모두 다항식 시간 [5]분사에 의해 서로 변환될 수 있다는 점에서 비슷해 보인다고 말한다.

예

주요 기사:PSPACE-complete 문제 목록

형식 언어

R{\ R을 지정하면 알파벳 위에 모든 문자열을 생성할지 여부를 결정하는 것은 PSPACE-complete입니다.[6]

PSPACE-complete의 첫 번째 알려진 문제는 결정론적 문맥에 민감한 문법에 대한 단어 문제였다.문맥에 민감한 문법에 대한 단어 문제에서는 문장의 길이를 늘릴 수 있지만 줄일 수는 없는 일련의 문법적 변환이 주어지며, 주어진 문장이 이러한 변환에 의해 생성될 수 있는지 여부를 판단하고 싶어한다.결정론의 기술적 조건(각 변환이 사용되었음을 대강 암시함)은 이 과정이 다항식 공간에서 해결될 수 있음을 보장하며, 구로다(1964)는 선형 공간에서 계산 가능한 모든 (아마도 비결정론적) 프로그램이 상황에 민감한 문법의 해석으로 변환될 수 있음을 보여주었다.결정론을 [7]보존하는 방법.1970년에 Savitch의 정리는 PSPACE가 비결정론 하에서 닫혀 있다는 것을 보여주었고, 이것은 심지어 비결정론적 맥락에 민감한 문법도 PSPACE에 [1]있다는 것을 암시한다.

논리

다른 많은 PSPACE 완전성 결과에서 사용되는 표준 PSPACE 완전성 문제는 부울 만족도 문제의 일반화인 정량화된 부울 공식 문제입니다.정량화된 부울 공식 문제는 다음과 같이 모든 변수를 보편적 또는 존재적으로 수량화한 부울식을 입력으로 받아들입니다.

문제의 출력은 수량화된 식 값입니다.이 값은 PSPACE-complete입니다.[1]

재구성

재구성 문제는 솔루션 상태 공간의 조합 문제에 대한 연결성과 관련이 있습니다.예를 들어, 3가지 색채에 대한 동일한 문제를 다항식 [9]시간에 해결할 수 있지만, 각 단계에서 유효한 4가지 색채를 유지하면서 한 번에 하나의 정점의 색을 바꾸는 이동에 의해 그래프의 두 가지 4가지 색채가 서로 연결될 수 있는지 여부를 테스트하는 것은 PSPACE-완료이다.[8]이 영역에서 다른 많은 문제의 PSPACE 완전성 증명의 기초로서 정량화된 부울 공식과 유사하게 사용되는 재구성 문제의 또 다른 패밀리는 비결정론적 제약 논리를 포함하며, 여기서 상태는 얼마나 많은 가장자리가 안쪽으로 향해야 하는지에 대한 특정 제약 조건 그래프의 방향이다.각 정점 및 상태 간 이동이 단일 [10]가장자리의 방향을 반대로 하는 경우.

퍼즐과 게임

PSPACE 또는 기타 복잡도 클래스의 완성도별 게임 목록은 게임 복잡성을 참조하십시오.

정량화된 부울 공식 문제는 검증자와 위조자 두 명의 플레이어에 의한 게임으로 해석될 수 있다.플레이어는 기존 수량화된 변수와 보편적으로 수량화된 변수를 채우는 검증기로 계량화된 변수의 값을 중첩된 순서대로 채우는 동작을 한다. 채워진 공식이 참이 되면 검증자가 게임에서 승리하고 그렇지 않으면 위조자가 승리한다.정량화된 공식은 검증자가 승리 전략을 가지고 있는 경우에만 참입니다.마찬가지로, 다른 많은 조합 게임의 승패를 결정하는 문제는 PSPACE-완전인 것으로 판명되었습니다.Examples of games that are PSPACE-complete (when generalized so that they can be played on an board) are the games Hex and Reversi.체스, 체커(드래프트), 바둑과 같은 다른 일반화된 게임들은 EXPTIME-complete이다. 왜냐하면 두 완벽한 선수들 간의 게임은 매우 길 수 있기 때문이다. 그래서 그들은 PSPACE에 있을 것 같지 않다.그러나 이동 수에 대한 다항식 경계가 [11]적용되면 PSPACE-완전이 됩니다.

또한 한 명의 플레이어가 플레이하는 퍼즐은 PSPACE 완성이 가능하다.이는 종종 재구성 [10]문제로 해석될 수 있으며, 솔리테어 게임인 러시 아워, 마작, 아토믹스, 소코반, 기계 컴퓨터인 튜링 [11]텀블 등이 포함됩니다.

PSPACE-완전성은 입력 n{ n의 함수로서 복잡성에 기초하고 있으며 n{ n이 제한 없이 증가할 때 된다.의 8 88) 보드의 체스 등 포지션 수가 제한된 퍼즐이나 게임은 PSPACE-완성이 될 수 없습니다.이는 매우 큰 룩업 테이블을 사용하여 일정한 시공간에서 해결할 수 있기 때문입니다.PSPACE-complete 버전의 게임을 공식화하려면 포지션 수가 제한되지 않도록 수정해야 합니다(예: × \ n \ n ).체스와 같은 경우에 따라 이러한 확장자는 인위적입니다.

레퍼런스

  1. ^ a b c Garey, Michael R.; Johnson, David S. (1979), "Section 7.4: Polynomial Space Completeness", Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, pp. 170–177, ISBN 0-7167-1045-5
  2. ^ Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, p. 92, ISBN 978-1-139-47736-9
  3. ^ Watanabe, Osamu; Tang, Shou Wen (1992), "On polynomial-time Turing and many-one completeness in PSPACE", Theoretical Computer Science, 97 (2): 199–215, doi:10.1016/0304-3975(92)90074-P, MR 1163815
  4. ^ Hitchcock, John M.; Pavan, Aduri (2013), "Length-increasing reductions for PSPACE-completeness", in Chatterjee, Krishnendu; Sgall, Jirí (eds.), Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013, Proceedings, Lecture Notes in Computer Science, vol. 8087, Springer, pp. 540–550, doi:10.1007/978-3-642-40313-2_48, MR 3126236
  5. ^ Berman, L.; Hartmanis, J. (1977), "On isomorphisms and density of NP and other complete sets", SIAM Journal on Computing, 6 (2): 305–322, doi:10.1137/0206023, hdl:1813/7101, MR 0455536
  6. ^ Hunt, Harry B. III (1973), "On the time and tape complexity of languages, I", in Aho, Alfred V.; Borodin, Allan; Constable, Robert L.; Floyd, Robert W.; Harrison, Michael A.; Karp, Richard M.; Strong, H. Raymond (eds.), Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1973, Austin, Texas, USA, Association for Computing Machinery, pp. 10–19, doi:10.1145/800125.804030, hdl:1813/6007
  7. ^ Kuroda, S.-Y. (1964), "Classes of languages and linear-bounded automata", Information and Computation, 7: 207–223, doi:10.1016/s0019-9958(64)90120-2, MR 0169724
  8. ^ Bonsma, Paul; Cereceda, Luis (2009), "Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances", Theoretical Computer Science, 410 (50): 5215–5226, doi:10.1016/j.tcs.2009.08.023, MR 2573973
  9. ^ Johnson, Matthew; Kratsch, Dieter; Kratsch, Stefan; Patel, Viresh; Paulusma, Daniël (2016), "Finding shortest paths between graph colourings", Algorithmica, 75 (2): 295–321, doi:10.1007/s00453-015-0009-7, MR 3506195
  10. ^ a b Hearn, Robert A.; Demaine, Erik D. (2009), Games, Puzzles, and Computation, A K Peters
  11. ^ a b Eppstein, David, Computational Complexity of Games and Puzzles

추가 정보