有限に提示されたカテゴリの等価問題の計算上の複雑さの特徴を見つけようとしています。
2 つの圏 C と D が与えられると、同値は 2 つの関手 F : C -> D と G : D -> C と 2 つの自然同型 FG -> I_D と I_C -> GF であり、ここで I_C : C -> C と I_D : D -> D は C と D の恒等関手です。
等価問題は、有限に提示された 2 つのカテゴリの等価性の存在を判断することです。この問題は決定的ではありませんが、再帰的に列挙可能または再帰的に列挙可能であることを願っています。どんな助けでも大歓迎です。