smoking186 https://blog.hatena.ne.jp/smoking186/ 186 @ hatenablog https://186.hatenablog.com/ CS とりあえず10個かー. 授業で証明読んだもの 停止問題とそのヴァリアント ビジービーバー ライスの定理 L(PDA)?={0,1}^*, L(PDA1)?=L(PDA2) PCP (Postの方) 証明知らないもの ヒルベルトの第10問題 ワンのタイル 読みたいもの DBLPから見繕う. 群同型 en.wikipediaにあった. 環同型は判定可能でNP∩coAM (Kayal and Saxena, CCC 2005). さらに, グラフ同型問題の困難性は環同型問題の困難性以下. コラッツ‐角谷予想の決定不能性 Eero Lehtonen “Two undecidable variants … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2F186.hatenablog.com%2Fentry%2F20090803%2F1249257987" title=" undecidable problems - 186 @ hatenablog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-08-03 09:06:27 rich https://186.hatenablog.com/entry/20090803/1249257987 1.0 100%