PSPACE-complete 문제 목록

List of PSPACE-complete problems
이것은 동적인 리스트이며, 완전성에 관한 특정의 기준을 만족시키지 못할 가능성이 있습니다.신뢰할 수 있는 소스로 누락된 항목을 추가하면 도움이 됩니다.

다음은 의사 결정 문제로 표현될 때 PSPACE-complete로 나타나는 일반적인 문제의 몇 가지입니다.이 목록은 결코 포괄적이지 않다.

게임과 퍼즐

일반 버전:

논리

  • 2D 민코프스키 시공간의 시간 논리.

람다 미적분

단순 유형 람다 미적분의 유형 거주 문제

오토마타와 언어 이론

회로 이론

정수 회로 평가[23]

오토마타 이론

형식 언어

그래프 이론

  • 그래프 컬러링 게임[42]
  • 노드 카일스 게임과 패거리 형성 게임:[43] 두 플레이어가 번갈아 정점을 선택하고 유도 서브그래프는 독립된 세트여야 합니다(resp. clique).꼴찌가 이긴다.
  • 많은 그래프 문제의 간결한 버전, 부울 회로,[44] 순서 있는 바이너리 결정[45] 다이어그램 또는 기타 관련 표현으로 표현된 그래프:
    • 간결한 그래프에 대한 s-t 도달 가능성 문제.이는 기본적으로 자동화된 계획 및 스케줄링에서 가장 단순한 계획 존재 문제와 동일합니다.
    • 간결한 그래프의 평면성
    • 간결한 그래프의 비순환성
    • 간결한 그래프의 연결성
    • 간결한 그래프에서의 오일러 경로의 존재
  • 캐나다 여행자 [46]문제
  • Border Gateway Protocol에 의해 선택된 경로가 특정 경로[47] 설정 세트에 대해 최종적으로 안정된 상태로 수렴될지 여부 결정
  • 동적 그래프 [21]신뢰성
  • 결정론적 제약 논리(무제한)[48]
  • 비결정적 제약 로직([11]무제한)
  • 2인 한정 구속[11] 논리

다른이들

  • 유한 지평선 POMDP(부분적으로 관측 가능한 마르코프 의사결정 프로세스).[49]
  • Hidden Model MDP(hmMDP)[50]
  • 동적 마르코프 과정.[21]
  • 관계형[51] 데이터베이스에서 포함 종속성 탐지
  • 렘케를 통해 얻을 수 있는 2인용 정상 형태 게임의 내쉬 균형 계산.하우슨 [52]알고리즘
  • 코리더 타일링 문제: Wang 타일 세트, 선택한 displaystyle 및 단항 표기로 지정된 폭(\ n의 경우 타일이 0(\ n\m)이 m(\ m이 있습니까?[53][54]

「 」를 참조해 주세요.

메모들

  1. ^ R. A. Hearn (2005-02-02). "Amazons is PSPACE-complete". arXiv:cs.CC/0502013.
  2. ^ Markus Holzer and Stefan Schwoon (February 2004). "Assembling molecules in ATOMIX is hard". Theoretical Computer Science. 313 (3): 447–462. doi:10.1016/j.tcs.2002.11.002.
  3. ^ 다항식 횟수 이동 후 추첨을 가정합니다.Aviezri S. Fraenkel (1978). "The complexity of checkers on an N x N board - preliminary report". Proceedings of the 19th Annual Symposium on Computer Science: 55–64. {{cite journal}}: 저널 요구 사항 인용(도움말)
  4. ^ Erik D. Demaine (2009). The complexity of the Dyson Telescope Puzzle. Vol. Games of No Chance 3.
  5. ^ a b Robert A. Hearn (2008). "Amazons, Konane, and Cross Purposes are PSPACE-complete". Games of No Chance 3. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  6. ^ Lichtenstein; Sipser (1980). "Go is polynomial-space hard". Journal of the Association for Computing Machinery. 27 (2): 393–401. doi:10.1145/322186.322201. S2CID 29498352.
  7. ^ Go 래더는 PSPACE-complete Archived 2007-09-30으로 Wayback Machine에 보관되어 있습니다.
  8. ^ Stefan Reisch (1980). "Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete)". Acta Informatica. 13: 59–66. doi:10.1007/bf00288536. S2CID 21455572.
  9. ^ Stefan Reisch (1981). "Hex ist PSPACE-vollständig (Hex is PSPACE-complete)". Acta Inform. (15): 167–191.
  10. ^ Viglietta, Giovanni (2015). "Lemmings Is PSPACE-Complete" (PDF). Theoretical Computer Science. 586: 120–134. doi:10.1016/j.tcs.2015.01.055.
  11. ^ a b c d Erik D. Demaine; Robert A. Hearn (2009). Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. Vol. Games of No Chance 3.
  12. ^ Grier, Daniel (2012). "Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-Complete". Automata, Languages, and Programming. Lecture Notes in Computer Science. Vol. 7965. pp. 497–503. arXiv:1209.1750. doi:10.1007/978-3-642-39206-1_42. ISBN 978-3-642-39205-4. S2CID 13129445.
  13. ^ Shigeki Iwata and Takumi Kasai (1994). "The Othello game on an n*n board is PSPACE-complete". Theoretical Computer Science. 123 (2): 329–340. doi:10.1016/0304-3975(94)90131-7.
  14. ^ a b c Hearn; Demaine (2002). "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation". arXiv:cs.CC/0205005.
  15. ^ A. Condon, J. Feigenbaum, C.룬드, P. 쇼어, 랜덤 토론자 및 확률 함수의 근사 경도, SIAM Journal on Computing 26:2 (1997) 369-400.
  16. ^ Demaine; Viglietta; Williams (2016). "Super Mario Bros. Is Harder/Easier than We Thought". {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  17. ^ 길버트, 렝가워, R.E. 타잔:다항식 공간에서 페블링 문제가 완료되었습니다.SIAM Journal on Computing, 제9권, 제3호, 1980년, 513-524페이지.
  18. ^ Philipp Hertel 및 Toniann Pitassi:흑백 Pebbling은 PSPACE-Complete Archived 2011-06-08 웨이백 머신에서 실행
  19. ^ a b 카사이 타쿠미, 아다치 아케오, 이와타 시게키: 페블 게임과 완전한 문제의 클래스, SIAM Journal on Computing, 1979년 제8권, 574-586쪽.
  20. ^ a b c d e f g h i j k K. 와그너와 G.웨취성.계산의 복잡성D. 레이델 출판사, 1986.ISBN 90-277-2146-7
  21. ^ a b c Christos Papadimitriou (1985). "Games against Nature". Journal of Computer and System Sciences. 31 (2): 288–301. doi:10.1016/0022-0000(85)90045-5.
  22. ^ A.P.Sistla and Edmund M. Clarke (1985). "The complexity of propositional linear temporal logics". Journal of the ACM. 32 (3): 733–749. doi:10.1145/3828.3837. S2CID 47217193.
  23. ^ 정수 회로 평가
  24. ^ 게리-존슨: AL3
  25. ^ 게리-존슨: AL4
  26. ^ 갈릴, Z완전한 문제의 계층.Acta Informatica 6(1976), 77-88.
  27. ^ 게리-존슨: AL2
  28. ^ L. J. Stockmeyer와 A. R. Meyer.기하급수적인 시간이 필요한 단어 문제.제5회 컴퓨팅 이론 심포지엄의 속행, 1973년 1~9페이지.
  29. ^ 게리-존슨: AL1
  30. ^ J. E. 홉크로프트와 J. D.울만오토마타 이론, 언어, 계산 소개, 1979년 초판.
  31. ^ a b D. 코젠자연 증명 시스템의 하한입니다.컴퓨터 과학 재단 18권, 254~266쪽, 1977년.
  32. ^ Langton's Ant problem 2007-09-27 Wayback Machine에서 아카이브된 Langton's Ant problem is PSPACE-complete IEIC Technical Report (Institute of Electronics, Information and Communications Engineer)의 야마구치 EII와 TATSUGIE에 의해 작성되었습니다.
  33. ^ T. Jiang과 B.라비쿠마.최소한의 NFA 문제는 어렵다.SIAM Journal on Computing, 22(6): 1117~1141, 1993년 12월.
  34. ^ S.-Y. Kuroda, "언어 및 선형 경계 오토마타", 정보 및 제어, 7(2): 207-223, 1964년 6월.
  35. ^ Bernátsky, László. "Regular Expression star-freeness is PSPACE-Complete" (PDF). Retrieved 13 January 2021.
  36. ^ 게리-존슨: AL12
  37. ^ 게리-존슨: AL13
  38. ^ 게리-존슨: AL14
  39. ^ 게리-존슨: AL16
  40. ^ 게리-존슨: AL19
  41. ^ 게리-존슨: AL21
  42. ^ Costa, Eurinardo; Pessoa, Victor Lage; Soares, Ronan; Sampaio, Rudini (2020). "PSPACE-completeness of two graph coloring games". Theoretical Computer Science. 824–825: 36–45. doi:10.1016/j.tcs.2020.03.022. S2CID 218777459.
  43. ^ Schaefer, Thomas J. (1978). "On the complexity of some two-person perfect-information games". Journal of Computer and System Sciences. 16 (2): 185–225. doi:10.1016/0022-0000(78)90045-4.{{cite journal}}: CS1 maint: ref 복제 기본값(링크)
  44. ^ 안토니오 로자노와 호세 L. 발카자르.간결하게 표현된 그래프에 대한 그래프 문제의 복잡성.Manfred Nagl 편집자, 컴퓨터 과학 그래프 이론 개념, 제15회 국제 워크숍, WG'89, 컴퓨터 과학 강의 노트 번호 411, 277-286페이지.Springer-Verlag, 1990년.
  45. ^ J. Feigenbaum, S. Kannan, M. Y. Vardi, M.Viswanathan, OBDD로 표현된 그래프의 복잡성, 시카고 이론 컴퓨터 과학 저널, vol 5, No 5, 1999.
  46. ^ C.H. Papadimitriou; M. Yannakakis (1989). "Shortest paths without a map". Lecture Notes in Computer Science. Proc. 16th ICALP. Vol. 372. Springer-Verlag. pp. 610–620.
  47. ^ 알렉스 파브리칸트와 크리스토스 파파디미트리우입니다게임 다이내믹스의 복잡성: BGP 진동, 싱크 equlibria 및 Wayback Machine의 아카이브 2008-09-05 이후.SODA 2008에서.
  48. ^ Erik D. Demaine and Robert A. Hearn (June 23–26, 2008). Constraint Logic: A Uniform Framework for Modeling Computation as Games. Vol. Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (Complexity 2008). College Park, Maryland. pp. 149–162.
  49. ^ C.H. Papadimitriou; J.N. Tsitsiklis (1987). "The complexity of Markov Decision Processes" (PDF). Mathematics of Operations Research. 12 (3): 441–450. doi:10.1287/moor.12.3.441. hdl:1721.1/2893.
  50. ^ I. Chades; J. Carwardine; T.G. Martin; S. Nicol; R. Sabbadin; O. Buffet (2012). MOMDPs: A Solution for Modelling Adaptive Management Problems. AAAI'12.
  51. ^ Casanova Marco A.; et al. (1984). "Inclusion Dependencies and Their Interaction with Functional Dependencies". Journal of Computer and System Sciences. 28: 29–59. doi:10.1016/0022-0000(84)90075-8.
  52. ^ P.W. Goldberg and C.H. Papadimitriou and R. Savani (2011). The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke–Howson Solutions. Proc. 52nd FOCS. IEEE. pp. 67–76.
  53. ^ Maarten Marx (2007). "Complexity of Modal Logic". In Patrick Blackburn; Johan F.A.K. van Benthem; Frank Wolter (eds.). Handbook of Modal Logic. Elsevier. p. 170.
  54. ^ Lewis, Harry R. (1978). Complexity of solvable cases of the decision problem for the predicate calculus. 19th Annual Symposium on Foundations of Computer Science. IEEE. pp. 35–47.

레퍼런스