Zonitoides excavatus and Talk:Eternity II puzzle: Difference between pages
tweak prose |
m Signing comment by Randommuser - "→Number of Distinct Colors: new section" |
||
| Line 1: | Line 1: | ||
==NP-complete== |
|||
{{Taxobox |
|||
While Demaine demonstrates that edge-matching puzzles ''in general'' are NP-complete, it does not mean that all specific edge-matching puzzles are necessarily NP-complete. (Consider as a counterexample trivial edge-matching puzzles with all pieces the same, which can be solved rapidly by trivial backtracking search, or the puzzle with all sides the same, which will be solved immediately by ''any'' search algorithm.) Is there any evidence that ''this particular'' puzzle has been deliberately constructed to be NP-complete? |
|||
| name = ''Zonitoides excavatus'' |
|||
| image = |
|||
| image_caption = |
|||
| image_width = 225px |
|||
| status = |
|||
| regnum = [[Animal]]ia |
|||
| phylum = [[Mollusca]] |
|||
| classis = [[Gastropoda]] |
|||
| subclassis = [[Orthogastropoda]] |
|||
| superordo = [[Heterobranchia]] |
|||
| ordo = [[Pulmonata]] |
|||
| familia = [[Gastrodontidae]] |
|||
| genus = ''[[Zonitoides]]'' |
|||
| species = ''Z. excavatus'' |
|||
| binomial = '''''Zonitoides excavatus''''' |
|||
| binomial_authority = (Alder, 1830]) |
|||
}} |
|||
Bonus question: is it possible to estimate the probability that a puzzle constructed by randomly coloring edgepairs of the puzzle in its assembled state before disassembling the tiles will be NP-complete, without solving an NP-complete problem to generate the probability itself? -- [[User:Karada|Karada]] 16:03, 28 August 2007 (UTC) |
|||
'''''Zonitoides excavatus''''' is a European [[species]] of small, air-breathing land [[snail]], a [[terrestrial]] [[pulmonate]] [[gastropod]] [[mollusk]] in the family [[Gastrodontidae]]. |
|||
My understanding is NP-completeness cannot be determined for any one instance of the problem. For example, Chess can be solved with O(1) time, using the big-oh notation. Just have a table about the size of googol with all the positions in there, and look it up. NP-completeness only applies to certain class of problems when the problem solving time is measured in relation to the problem size in some measure. Eternity II has its rules printed out and the fixed set of pieces, so it does not have variable problem size, even tho it can placed into different classes of problems which indeed have variable problem size. [[User:62.220.237.74|62.220.237.74]] 19:13, 15 September 2007 (UTC) |
|||
==Distribution== |
|||
This species is found in the [[British Isles]] and from [[Denmark]] to [[Belgium]] and northern [[France]]. |
|||
I was astonished by both comments. Both have a point and the first raise an important question. My summary is this. NP-complete refers to '''complexity class'''. This means that if a problem lies in this class, this is for every 'word' in the language of the input. For example, prime factorization may be outside of P, but finding the prime factors of 26=2*13 is trivial. Complexity is therefore used as a measure of how the difficulty scales to the size of the input, but does not refer to the difficulty of '''instances of the problem''' |
|||
==References== |
|||
{{reflist}} |
|||
==External links== |
|||
* Excellent info at: [http://www.animalbase.uni-goettingen.de/zooweb/servlet/AnimalBase/home/species?id=2560] |
|||
* Taxonomy at: [http://zipcodezoo.com/Animals/Z/Zonitoides_excavatus/] |
|||
* One shell image at: [http://www.mollusken-nrw.de/forschung/bilder/ZonarbVO.500x500.jpg] |
|||
About Eternity II, we are interested if it is tractable or not. It may well be, but there is strong evidence it may be not. Karada poses a very interesting question. To paraphrase it a liitle: "Was Eternity II constructed to be difficult?". And I might also be interested in designing an approach on how to decide on that. |
|||
[[Category:Zonitoides]] |
|||
== Number of Distinct Colors == |
|||
Currently the article says there are 22 distinct colors, however, according to one of the references below: |
|||
{{Pulmonata-stub}} |
|||
http://grok-code.com/10/e2-the-np-complete-kids-game-with-the-2-million-prize/ |
|||
there are only 17, and possibly one of them is the gray color. Can anyone confirm this? <small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Randommuser|Randommuser]] ([[User talk:Randommuser|talk]] • [[Special:Contributions/Randommuser|contribs]]) 00:38, 13 October 2008 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot--> |
|||
Revision as of 00:39, 13 October 2008
NP-complete
While Demaine demonstrates that edge-matching puzzles in general are NP-complete, it does not mean that all specific edge-matching puzzles are necessarily NP-complete. (Consider as a counterexample trivial edge-matching puzzles with all pieces the same, which can be solved rapidly by trivial backtracking search, or the puzzle with all sides the same, which will be solved immediately by any search algorithm.) Is there any evidence that this particular puzzle has been deliberately constructed to be NP-complete?
Bonus question: is it possible to estimate the probability that a puzzle constructed by randomly coloring edgepairs of the puzzle in its assembled state before disassembling the tiles will be NP-complete, without solving an NP-complete problem to generate the probability itself? -- Karada 16:03, 28 August 2007 (UTC)
My understanding is NP-completeness cannot be determined for any one instance of the problem. For example, Chess can be solved with O(1) time, using the big-oh notation. Just have a table about the size of googol with all the positions in there, and look it up. NP-completeness only applies to certain class of problems when the problem solving time is measured in relation to the problem size in some measure. Eternity II has its rules printed out and the fixed set of pieces, so it does not have variable problem size, even tho it can placed into different classes of problems which indeed have variable problem size. 62.220.237.74 19:13, 15 September 2007 (UTC)
I was astonished by both comments. Both have a point and the first raise an important question. My summary is this. NP-complete refers to complexity class. This means that if a problem lies in this class, this is for every 'word' in the language of the input. For example, prime factorization may be outside of P, but finding the prime factors of 26=2*13 is trivial. Complexity is therefore used as a measure of how the difficulty scales to the size of the input, but does not refer to the difficulty of instances of the problem
About Eternity II, we are interested if it is tractable or not. It may well be, but there is strong evidence it may be not. Karada poses a very interesting question. To paraphrase it a liitle: "Was Eternity II constructed to be difficult?". And I might also be interested in designing an approach on how to decide on that.
Number of Distinct Colors
Currently the article says there are 22 distinct colors, however, according to one of the references below: http://grok-code.com/10/e2-the-np-complete-kids-game-with-the-2-million-prize/ there are only 17, and possibly one of them is the gray color. Can anyone confirm this? —Preceding unsigned comment added by Randommuser (talk • contribs) 00:38, 13 October 2008 (UTC)