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 入門」 第一部 「機械と人間のインタラクション」