Interactive Proofと複雑性

2021/01/10* マルゼミ「Interactive Proofと複雑性」

「Interactive Proofと複雑性」　YouTube版

Interactive Proof = nonlocalゲーム — Interactive Proofと確率的証明 —

グラフの同型性

頂点の置換とグラフの同型性

Interactive Proofから見るグラフの非同型性

MaruLabo関連資料

• 「MIP*=RE References」
• マルレク 「MIP*=RE 入門– Interactive Proofとnonlocal ゲーム –」
• マルレク 「コンピュータ・サイエンスの現在 — MIP*=RE定理とは何か？–
• マルレク 「人工知能と計算科学」
• 「Interactive Proof 入門」 第三部 「確率と証明」
• 「Interactive Proof 入門」 第二部 「nonlocal game とInteractive Proof」
• 「Interactive Proof 入門」 第一部 「機械と人間のインタラクション」