Timeline for Finite objects for which isomorphism is NP-hard or harder?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 11, 2020 at 10:45 | comment | added | joro | Related cryptography question: mathoverflow.net/questions/371362/… | |
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| May 19, 2016 at 7:39 | history | edited | Thomas Klimpel | CC BY-SA 3.0 |
deleted 2 characters in body
|
| May 15, 2016 at 14:03 | comment | added | Thomas Klimpel | @joro Even if this is not a complete answer, the intention is certainly not to ask more questions. If your question is interpreted sufficiently strict, then the answer would be that there are no finite objects for which deciding isomorphism is NP-hard or harder, in the sense that the problem will always be in $AM\cap coAM$, which can only be NP-hard if the polynomial hierarchy collapses. Maybe it was a bad idea to describe the encoding by generators or by straight line programs as "compression". The issue is annoying (it is a source of disagreement), but not like "can something be compressed". | |
| May 15, 2016 at 12:55 | comment | added | joro | So this is partial answer, asking more questions, right? The issue of "compressing" appears complicated, I have seen problems of the form "can something be compressed". | |
| May 15, 2016 at 4:14 | comment | added | Thomas Klimpel | @joro I restructured the answer now into three distinct parts and an explanation about the role of those parts, to make it easier to parse. The answer to the question is that using input compression (for example generators of permutation groups) might be able to come up with hard examples of isomorphism testing problems, but even then Emil Jeřábek's comment about isomorphism being in coAM will often still apply and prevent the problem from being NP-hard. | |
| May 15, 2016 at 4:07 | history | edited | Thomas Klimpel | CC BY-SA 3.0 |
restructured the answer into three parts, and added an explanation how those parts address the question
|
| May 14, 2016 at 13:34 | comment | added | joro | Thanks, I am trying to parse this. Isn't something like mixing unitary and binary clear abuse, leading to a mess? And what is the answer to the question? | |
| May 14, 2016 at 12:11 | history | answered | Thomas Klimpel | CC BY-SA 3.0 |