Jump to content

Talk:List of PSPACE-complete problems

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Untitled

[edit]

The generalized piano mover's problem is PSPACE-complete (John Canny - Some Algebraic and Geometric Computations in PSPACE, John H. Reif - Complexity of the Mover's Problem and Generalizations). I will add it when i find some time.

There are quite a few PSPACE-complete games and puzzles not listed in this article. I cannot add them because I have a COI as an author of several of these results. The ones I am aware of that are not listed are:

Sliding-block puzzles
Sliding-coin puzzles
Plank Puzzles
Block-pushing puzzles Push-2-F, PushPush-k, and Push-*-F (all related to Sokoban)
Rolling block mazes
Konane
Cross Purposes
A large family of token games on DAGs (e.g. Annihilation, Hit, Capture, Node Blocking, Edge Blocking, Pursuit)
Node Kayles (and Partizan Node Kayles)
Snort
Shannon Switching Game on directed graph edges

All of these are described in the paper Playing Games with Algorithms: Algorithmic Combinatorial Game Theory and Appendix A of the book Games, Puzzles, and Computation

PSPACE-complete problems in graph theory that are not listed on the page include Deterministic Constraint Logic, Nondeterministic Constraint Logic, and Bounded Two-Player Constraint Logic. Bobhearn (talk) 21:03, 2 April 2010 (UTC)[reply]


The article lists the emptiness problem for regular expressions as PSPACE-complete. This is incorrect, as for regular expressions it is solvable in DTIME(n). It is only PSPACE-complete for regular expressions with intersection. I removed it from the article, as I think it should only be in there if this issue is clarified. Jooohnas (talk) 11:52, 1 July 2011 (UTC)[reply]

DFA intersection emptyness

[edit]

The intersection of two DFA can be calculated and has maximal size of n*m. Emptyness is a linear problem, thus it is bilinear regarding the two input automata. Thus it should be not PSPACE-complete. — Preceding unsigned comment added by 138.246.2.173 (talk) 19:23, 6 December 2012 (UTC)[reply]

PSPACE-completeness comes in here for an unbound number of automata. For two automata it is indeed in P. 82.135.69.43 (talk) 07:23, 1 September 2014 (UTC)[reply]

Snake Pspace complete

[edit]

The video game Snake is Pspace complete. See this link: Snake is pspace complete

— Preceding unsigned comment added by 79.109.5.165 (talk) 19:13, 2 December 2016 (UTC)[reply]

[edit]

Hello fellow Wikipedians,

I have just modified 4 external links on List of PSPACE-complete problems. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 20:30, 26 December 2017 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:List_of_PSPACE-complete_problems&oldid=1212681223"