Timeline for Decision problems for which it is unknown whether they are decidable
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27, 2023 at 12:26 | comment | added | Ville Salo | Ah, I missed this word. If the last sentence really means that both the polygon and cuts are orthogonal, I don't see why it would be trivially decidable, but this is highly surprising. With this interpretation, I can finally upvote this answer :P | |
| Sep 27, 2023 at 12:02 | comment | added | Timothy Chow | @VilleSalo They said, "orthogonal with all edges having integer length." I think that "orthogonal" means that every edge is either parallel to the $x$-axis or parallel to the $y$-axis. | |
| Sep 27, 2023 at 6:32 | comment | added | Ville Salo | Concretely (and I apologize for this triviality): Suppose the polygons are given by Turing machines telling you better and better precision on the angles and positions of edges (I mean, how else, when no specific type of algebraicity is specified?) Consider two unit cubes that have been slightly distorted (still with unit sides) by pushing two corners together. You can never know if two such polygons are the same (and it's easy to arrange that they have no common $k$-dissection for any $k$ when distinct). | |
| Sep 27, 2023 at 6:25 | comment | added | Ville Salo | Ok, but "integer length edges" still allows uncountably many polygons. | |
| Sep 26, 2023 at 23:03 | comment | added | Timothy Chow | @VilleSalo I noticed today that in Section 9 of the paper, the authors write, "Our proofs remain valid when the input polygons are restricted to be simple (hole-free) and orthogonal with all edges having integer length." They also write, "Is k-Piece Dissection in NP, or even decidable? We do not know the answer to this question even when only orthogonal cuts are allowed and rotations and reflections are forbidden." | |
| Dec 3, 2019 at 15:51 | comment | added | Timothy Chow | @VilleSalo : I had the same question. I have not asked the authors, but I assume that that is what they meant. | |
| Dec 3, 2019 at 11:29 | history | made wiki | Post Made Community Wiki by Todd Trimble | ||
| Dec 3, 2019 at 8:50 | comment | added | Ville Salo | It is not clear to me what the problem they ask is. Do I interpret correctly that it is open whether, given two rational polygons of equal area in $\mathbb{R}^2$, it is decidable whether there is a common dissection? | |
| Nov 6, 2019 at 17:00 | history | answered | Timothy Chow | CC BY-SA 4.0 |