Skip to main content
2 of 2
Partial result based on Chow's comment
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 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.

joro
  • 25.4k
  • 10
  • 66
  • 121