{"description":"\u3068\u308a\u3042\u3048\u305a10\u500b\u304b\u30fc. \u6388\u696d\u3067\u8a3c\u660e\u8aad\u3093\u3060\u3082\u306e \u505c\u6b62\u554f\u984c\u3068\u305d\u306e\u30f4\u30a1\u30ea\u30a2\u30f3\u30c8 \u30d3\u30b8\u30fc\u30d3\u30fc\u30d0\u30fc \u30e9\u30a4\u30b9\u306e\u5b9a\u7406 L(PDA)?={0,1}^*, L(PDA1)?=L(PDA2) PCP (Post\u306e\u65b9) \u8a3c\u660e\u77e5\u3089\u306a\u3044\u3082\u306e \u30d2\u30eb\u30d9\u30eb\u30c8\u306e\u7b2c10\u554f\u984c \u30ef\u30f3\u306e\u30bf\u30a4\u30eb \u8aad\u307f\u305f\u3044\u3082\u306e DBLP\u304b\u3089\u898b\u7e55\u3046. \u7fa4\u540c\u578b en.wikipedia\u306b\u3042\u3063\u305f. \u74b0\u540c\u578b\u306f\u5224\u5b9a\u53ef\u80fd\u3067NP\u2229coAM (Kayal and Saxena, CCC 2005). \u3055\u3089\u306b, \u30b0\u30e9\u30d5\u540c\u578b\u554f\u984c\u306e\u56f0\u96e3\u6027\u306f\u74b0\u540c\u578b\u554f\u984c\u306e\u56f0\u96e3\u6027\u4ee5\u4e0b. \u30b3\u30e9\u30c3\u30c4\u2010\u89d2\u8c37\u4e88\u60f3\u306e\u6c7a\u5b9a\u4e0d\u80fd\u6027 Eero Lehtonen \u201cTwo undecidable variants \u2026","html":"<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>","title":" undecidable problems","provider_url":"https://hatena.blog","image_url":null,"blog_title":"186 @ hatenablog","author_name":"smoking186","width":"100%","blog_url":"https://186.hatenablog.com/","provider_name":"Hatena Blog","url":"https://186.hatenablog.com/entry/20090803/1249257987","height":"190","categories":["CS"],"author_url":"https://blog.hatena.ne.jp/smoking186/","published":"2009-08-03 09:06:27","type":"rich","version":"1.0"}