What makes a problem be NP complete is allowing some parameter (maximum rank of the cards in this case) to increase without bounds. Each step increase requires exponentially more computations. Yes, setting a limit at any level keeps the problem from being NP complete. I don’t see how the proof that the first paradigm is NP complete bears on the second paradigm of a limit on the minimal number of moves. It is the case that a search for the minimal number of moves takes an increasing amount of computations. It seems to me that once one solution is found, each step down from that clearly requires a finite number of computations and since we always begin with a finite number of steps toward a minimum, we always have a finite number of computations (although perhaps quite large).
From: Shlomi Fish
Sent: Tuesday, October 02, 2012 6:46 AM
To: fc-solve-discuss_at_yahoogroups.com
Cc: gary_at_numin8r.us
Subject: Re: Status of 8x4 FreeCell Deals
Hi Gary,
On Tue, 2 Oct 2012 06:21:57 -0700
"Gary Campbell" <mailto:gary%40numin8r.us> wrote:
> Just to address one minor point of Shlomi’s last posting (I’ll cut
> out the rest).
>
> I don’t know of anybody (or any FreeCell solver) that has addressed
> more than the 13 ranks of the natural deck of cards, so the NP
> complete version “generalised Freecell” hasn’t caught anyone’s
> attention (as a problem to be solved) as far as I know. Given more
> than 4 free cells, the game becomes rapidly less interesting. Given
> the 13 ranks (a standard 52-card deck), 8 columns, and and 0 to 4
> free cells, you pretty much have what we have, and it is clearly not
> an NP complete problem. I’m not sure why this issue keeps cropping
> up.
>
Well, I may argue that a Freecell problem with 100 levels of ranks is not
NP-complete either, because the number is still limited. However, it would
be significantly harder than the 13 ranks of the French deck, which in
turn is harder than that of decks with a smaller number of cards.
My complete quote was:
[QUOTE]
OK. There has been some research which showed that generalised Freecell
is NP-complete (as a function of the number of ranks), see:
http://en.wikipedia.org/wiki/FreeCell#Complexity
This may set a hard limit to the number of minimal moves.
[/QUOTE]
What I meant by that is that there may be some implications on the depth of
the moves graph until reaching the shortest solution, which would be implied
by the fact that generalised Freecell was found to be NP-complete. I'm not much
of a computer scientist, so I it's just a speculation, but it prove to
be insightful.
Regards,
Shlomi Fish
> -Gary Campbell
>
> From: Shlomi Fish
> Sent: Tuesday, October 02, 2012 1:53 AM
> To: mailto:fc-solve-discuss%40yahoogroups.com
> Cc: mailto:dannyjones183%40yahoo.com
> Subject: Re: Status of 8x4 FreeCell Deals
>
> OK. There has been some research which showed that generalised
> Freecell is NP-complete (as a function of the number of ranks), see:
>
> http://en.wikipedia.org/wiki/FreeCell#Complexity
>
>
>
> Switch to: Text-Only, Daily Digest • Unsubscribe • Terms of Use •
> Send us Feedback .
--
----------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
Free (Creative Commons) Music Downloads, Reviews and more - http://jamendo.com/
Real men don’t listen to sentences that start with “Real men don’t”.
— http://whatsup.org.il/article/6023
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Tue Oct 02 2012 - 07:07:36 IST