Timeline for Finite objects for which isomorphism is NP-hard or harder?
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 15, 2020 at 12:52 | comment | added | joro | @EmilJeřábek I added answer about NP-hardness of CIRCUIT ISOMORPHISM and FORMULA ISOMORPHISM. | |
| Sep 15, 2020 at 12:27 | answer | added | joro | timeline score: 2 | |
| May 20, 2016 at 20:06 | answer | added | Joe Bebel | timeline score: 3 | |
| May 20, 2016 at 12:05 | comment | added | Emil Jeřábek | No, that's not what I said, at all. | |
| May 14, 2016 at 13:10 | comment | added | joro | @TimothyChow Emil's comment suggest your are looking for succinct representations of graphs. Consider "compressing" some graphs classes to BDDs as suggested in On the OBDD size for graphs of bounded tree- and clique-width. From there "– for graphs of bounded tree-width there is an OBDD of size O(log n) for f G that uses encodings of size O(log n) for the vertices;" | |
| May 14, 2016 at 12:11 | answer | added | Thomas Klimpel | timeline score: 7 | |
| May 14, 2016 at 12:09 | comment | added | joro | @EmilJeřábek ok, the edit might be pointless. According to your comments Chows's approach won't work unless unlikely collapse, right? | |
| May 14, 2016 at 9:54 | comment | added | Emil Jeřábek | What you've put in the question is just an elaborate version of UNSAT. There is no point in considering a weird model like indexed BDDs when it's already coNP-complete for CNFs. Meanwhile, this has nothing to do at all with Timothy Chow's suggestion, which was the usual graph isomorphism, but for graphs represented succinctly rather than by explicit enumeration of vertices and edges. | |
| May 14, 2016 at 6:54 | comment | added | joro | @TimothyChow Based on your comment, I edited with paper claiming that equivalence of Indexed BDDs is coNP-complete. Maybe someone will make isomorphism of this. | |
| May 14, 2016 at 6:52 | history | edited | joro | CC BY-SA 3.0 |
Partial result based on Chow's comment
|
| May 13, 2016 at 20:15 | comment | added | Timothy Chow | The following might be considered "cheating" but you can specify a graph by providing a circuit that, given the labels of two vertices, outputs 0 or 1 according to whether the vertices are adjacent or not. Deciding isomorphism for such "succinctly represented" graphs is surely NP-hard, although I'd have to think about how to prove that. | |
| May 13, 2016 at 12:08 | comment | added | Emil Jeřábek | I am of course talking about polynomial-time many-one reductions. Otherwise it wouldn't be relevant. | |
| May 13, 2016 at 11:55 | comment | added | joro | @EmilJeřábek Is it known that all reductions to GI take polynomial time and space in the size of the "object"? e.g. boolean propositional formula to a single clause in DNF will solve SAT. | |
| May 13, 2016 at 11:08 | comment | added | Emil Jeřábek | Actually more generally: isomorphism of finite "objects" is in coAM (hence not NP-hard unless PH = AM = coAM), as long as the standard IP protocol works (the Verifier chooses randomly one of the two given objects, randomly permutes it, and ask the Prover which object they've chosen). Basically, you only need that the objects consist of a "base set" plus whatever extra stuff, and any bijection of the base set of an object to another set lifts to an isomorphism of a uniquely determined object, poly-time computable from the given data. | |
| May 13, 2016 at 11:00 | comment | added | Emil Jeřábek | I can't parse that sentence. I am saying that isomorphism of arbitrary structures is reducible to graph isomorphism. | |
| May 13, 2016 at 10:49 | comment | added | joro | @EmilJeřábek Thanks. Do you mean that GI is isomorphism of finite objects complete? | |
| May 13, 2016 at 10:44 | comment | added | Emil Jeřábek | Well, it can't be any kind of algebraic or relational structures, as their isomorphism reduces to GI. Topology can't help either, as it collapses on finite sets to preorder, which is again just a relation. | |
| May 13, 2016 at 9:03 | history | asked | joro | CC BY-SA 3.0 |