{"title":"2SAT","provider_url":"https://hatena.blog","type":"rich","blog_url":"https://yasu0207.hatenadiary.org/","height":"190","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyasu0207.hatenadiary.org%2Fentry%2F20091206%2F1260111871\" title=\"2SAT - yasu0207\u306e\u65e5\u8a18\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","provider_name":"Hatena Blog","blog_title":"yasu0207\u306e\u65e5\u8a18","description":"\u5f37\u9023\u7d50\u6210\u5206\u5206\u89e3\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u30bc\u30df\u3067\u3084\u3063\u305f\u306e\u3067\u30e1\u30e2\u3002 2SAT\u306f\u5f37\u9023\u7d50\u6210\u5206\u5206\u89e3\u3092\u5229\u7528\u3057\u3066\u89e3\u3051\u308b\u30022SAT\u306f\u591a\u9805\u5f0f\u6642\u9593\u3067\u89e3\u3051\u308b\u3002\u3061\u306a\u307f\u306b3SAT\u306fNP\u5b8c\u5168\u3002\u89e3\u304d\u65b9\u306f\uff12\u3064\u3042\u308b\u3002 (1)\u3042\u308b\u5909\u6570x\u306e\u5272\u308a\u5f53\u3066\u30920\u3067\u56fa\u5b9a\u3059\u308b\u3068\u30012SAT\u306a\u306e\u3067\u3001x\u3092\u542b\u3080\u7bc0\u306ex\u3068\u306f\u7570\u306a\u308b\u5909\u6570\u306e\u5272\u308a\u5f53\u3066\u304c\u6c7a\u307e\u308b\u3002 \u3053\u306e\u3088\u3046\u306b\u3057\u3066\u77db\u76fe\u304c\u8d77\u3053\u308b\u3068\u3001x\u3078\u306e\u5272\u308a\u5f53\u3066\u304c\u6c7a\u5b9a\u3057\u3001x\u3092\u542b\u3080\u7bc0\u3092\u6d88\u53bb\u3057\u3066\u518d\u5e30\u3002 (2)2SAT\u306a\u306e\u3067\u7bc0\u306f(x\u2228\u00acy)\u306e\u3088\u3046\u306a\u5f62\u3092\u3057\u3066\u3044\u308b\u3002\u3053\u308c\u306fy\u21d2x\u3068\u540c\u3058\u3067\u3042\u308b \u5404\u8ad6\u7406\u5909\u6570\u3001\u8ad6\u7406\u5426\u5b9a\u305d\u308c\u305e\u308c\u306b\u9802\u70b9\u3092\u7528\u610f\u3057\u3066\u3001y\u21d2x\u3092\u5f0f\u304c\u542b\u3093\u3067\u3044\u308c\u3070\u6709\u52b9\u8fba(y,x)\u3092\u30b0\u30e9\u30d5\u306b\u52a0\u3048\u308b\u3002 \u3053\u306e\u3088\u3046\u306b\u3057\u3066\u3067\u304d\u305f\u30b0\u30e9\u30d5\u306b\u5f37\u9023\u7d50\u6210\u5206\u5206\u89e3\u30a2\u2026","version":"1.0","published":"2009-12-06 00:04:31","author_url":"https://blog.hatena.ne.jp/yasu0207/","categories":["algorithm"],"author_name":"yasu0207","image_url":null,"url":"https://yasu0207.hatenadiary.org/entry/20091206/1260111871","width":"100%"}