Skip to main content
Partial result based on Chow's comment
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

Are there finite objects for which deciding isomorphism is NP-hard or harder?

Graphs and groupgroups are not solutions.

Searching the web didn't return answer for me.


Partial result based on Chow's comment.

From a paper p.16

for IBDDs (Indexed BDDs) ... the equivalence test is coNP-complete even if there are only two layers.

Indexed BDD are rooted digraphs, representing boolean function.

"Equivalence" appears very close to isomorphism and means representing the same boolean function.

Are there finite objects for which deciding isomorphism is NP-hard or harder?

Graphs and group are not solutions.

Searching the web didn't return answer for me.

Are there finite objects for which deciding isomorphism is NP-hard or harder?

Graphs and groups are not solutions.

Searching the web didn't return answer for me.


Partial result based on Chow's comment.

From a paper p.16

for IBDDs (Indexed BDDs) ... the equivalence test is coNP-complete even if there are only two layers.

Indexed BDD are rooted digraphs, representing boolean function.

"Equivalence" appears very close to isomorphism and means representing the same boolean function.

Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

Finite objects for which isomorphism is NP-hard or harder?

Are there finite objects for which deciding isomorphism is NP-hard or harder?

Graphs and group are not solutions.

Searching the web didn't return answer for me.