0
$\begingroup$

Generalized chess is EXPTIME complete[1]. Generalized chess is also PSPACE complete[2]. Therefore $EXPTIME = PSPACE$. This implies that $P \neq PSPACE$

This proof is probably wrong. I want to know what I did wrong. They are probably referring to different problems regarding chess. But here are my sources. I can't say if they are. Reading the first bit of the papers it sounds like they are describing problems that are similar if not the exact same, But they probably are not. Hopefully someone proves me wrong and I learn something.

If i'm not wrong then how did actual scientists miss this?

EDIT 1: The EXP-TIME paper says that it is determining a perfect strategy, the P SPACE paper is determining if a player has wining moves. IF you look at the start position of NXN chess, determining if a player has a series of winning moves is the same as a perfect strategy I think. Forgive any trivial errors here. I'm, very new to this. But want to learn.

references

[1]

Aviezri S. Fraenkel, David Lichtenstein

Computing a perfect strategy for n×n chess requires time exponential in n

https://link.springer.com/chapter/10.1007/3-540-10843-2_23

[2]

http://rohitsharma.net/wp-content/uploads/2019/09/1-s2.0-0022000083900302-main.pdf

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Your links seem broken. Can you fix them? Also, we expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$
    – D.W. ♦
    Jan 3, 2022 at 3:01
  • $\begingroup$ Thanks for fixing the links. When posting references to papers, we prefer that you also include the title, authors, and where it was published. This serves two purposes; it helps others with a question about these papers find this page (by searching for the paper title), and it ensures the question continues to make sense even if the link stops working. See the link I gave above for details about this expectation. Thank you for your understanding. $\endgroup$
    – D.W. ♦
    Jan 3, 2022 at 4:33

1 Answer 1

Reset to default
2
$\begingroup$

The first step is to read and understand the papers. It's not always enough to read just the introduction -- you often need to read the full paper, particularly the precise statement of results and their discussion. Reading the papers will help you discover what they each actually prove, and then you will discover why the two papers are actually consistent with each other. The researchers didn't miss anything; they already explained the answer to your question in their paper. Each paper considers a problem that is related to or can be considered as a generalization of chess; but they don't both consider the same problem.

In particular, the Storer paper specifically mentions Fraenkel's work and explains the difference between their two results. To quote:

Although we have taken the view that exponentially long generalized chess games are not in the spirit of the 50-move draw rule, recently, Fraenkel and Lichtenstein [4] have shown that when exponentially long games are allowed, generalized chess is exponential-time complete.

See also the surrounding sentences for more explanation.

In short, it's not entirely clear what is the right way to generalize the 50-move rule, and what choice you make affects the complexity of the problem.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. So if i could somehow prove that, regardless of how the 50 move rule is generalized, the complexity is the same, that PSPACE = EXP? Albeit there is a proof that hasn't really been validated yet that $PSPACE \neq EXP$ it is located here. arxiv.org/abs/2104.14316 But this has at-least kinda seems to reduce the problem of PSPACE vs EXP to something easier???(maybe) $\endgroup$
    – Colonizor48
    Jan 3, 2022 at 18:53
  • 1
    $\begingroup$ @Colonizor48, Could you fix the paper references in your question, as indicated above? Thank you. Probably, but I'm guessing it's unlikely you'll be able to prove that. I don't see how that is easier. $\endgroup$
    – D.W. ♦
    Jan 3, 2022 at 20:57
  • $\begingroup$ @Colonizor48, thank you for citing my paper. There are some bugs, so I have written a similar paper ( $ L\not= P$ ) arxiv.org/abs/2201.08501. $\endgroup$
    – Reiner Czerwinski
    Jan 24, 2022 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.