0
$\begingroup$

I am not a mathematician. I am trying to understand if the paper "The complexity of solitaire" that shows this game is NP-complete also has a implicit assumption that a given hand can only be played once (i.e. is a single-shot rule). In other words a given hand cannot be replayed using information gathered from previous failed attempts to find a solution.

Here is the full information on the paper:

Luc Longpré and Pierre McKenzie, The complexity of solitaire, Theor. Comput. Sci. 410, No. 50, 5252-5260 (2009), MR2573977, Zbl 1194.68123.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ I don't know about this specific case, but usually proofs of NP-completeness do not rely on any assumptions about missing information since problems in NP by definition provide all relevant information to the problem-solver. Is there a specific reason that you think this one might? $\endgroup$
    – Will Sawin
    Commented Oct 7 at 14:44
  • $\begingroup$ Yes - I find that using information from previously played hands I can find a solution to more than 60% of hands within 2 or 3 plays. There are some instance that take more plays and other instances that are very difficult are likely NP. There seems to be an unstated assumption in the original rules from a couple of centuries ago when played with cards that the search for a solution was done in only one try. With the advent of the digital form of the game hands can be replayed using information gleaned from failed hands $\endgroup$
    – Syl
    Commented Oct 7 at 14:57
  • 2
    $\begingroup$ NP-completeness just means that some cases of the problem are hard - it's fine if these cases are very rare, so rare that they would never occur in practice with random hands. So this isn't really any evidence on the question. $\endgroup$
    – Will Sawin
    Commented Oct 7 at 15:02
  • $\begingroup$ That is what I was looking for "some cases of the problem are hard" are hard and NP-complete while other are simple and P or intermediate NP cases using information from previous plays of a given hand Given any hand there are two possible decisions (1) is there a solution (yes/no) (2) is the solution optimal i.e. done in the fews number of moves (yes/no) I can see that #2 is NP but from what you said it seems #2 can range from P to NP Does this sound correct? $\endgroup$
    – Syl
    Commented Oct 7 at 15:07
  • 1
    $\begingroup$ That just isn't how NP is defined. One can't say an individual problem like a hand of solitaire is or isn't NP-complete. Rather NP-completeness is a property of an infinite sequence of problems like all possible hands of solitaire (after generalizing solitaire to larger decks of cards so that there are infinitely many possible hands). If a sequence (called for historical reasons a language) is NP-complete then every member is contained in a NP-complete subsequence and every member is contained in a subsequence in P. $\endgroup$
    – Will Sawin
    Commented Oct 7 at 15:10

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .