{"provider_url":"https://hatena.blog","image_url":null,"type":"rich","published":"2005-04-23 15:35:33","author_url":"https://blog.hatena.ne.jp/smoking186/","author_name":"smoking186","title":" NP-hard based cryptosystem","categories":["crypt"],"html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2F186.hatenablog.com%2Fentry%2F20050423%2F1114238133\" title=\" NP-hard based cryptosystem - 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>","description":"\u3084\u3063\u3071\u308a\u5b9f\u7528\u7684\u306a\u30ec\u30d9\u30eb\u3067\u306f\u5143\u306b\u306a\u308b\u554f\u984c\u306fNP\u304b\u3064co-NP\u306e\u65b9\u304c\u3044\u3044\u3088\u306d\u3001\u3068\u3044\u3046\u8a71\u304c\u3042\u308b\u3002\u76f4\u611f\u7684\u306b\u8a00\u3063\u3066\u3057\u307e\u3046\u304c\u3001co-NP\u3060\u3063\u305f\u3089\u6b63\u3057\u3044\u6697\u53f7\u6587\u304b\u3069\u3046\u304b\u30c1\u30a7\u30c3\u30af\u3067\u304d\u308b\u3002 \u3067\u3001NP-hard\u3084NP-complete\u306a\u554f\u984c\u3092\u5143\u306b\u3057\u305f\u6697\u53f7\u69cb\u6210\u6cd5\u306f\u3042\u308b\u306e\u304b\u3001\u3068\u3044\u3046\u8a71\u306b\u306a\u308b\u304c\u3001\u306a\u306b\u305b\u5143\u304cNP-hard\u306a\u306e\u3067\u4f5c\u308a\u3065\u3089\u3044\u3088\u3046\u3060\u3002 \u683c\u5b50\u95a2\u4fc2\u304c\u5c40\u6240\u7684\u306b\u6d41\u884c\u3063\u3066\u308b\u306e\u306fWorst-case/Average-case\u306a\u95a2\u4fc2\u304c\u3042\u3063\u305f\u308a\u3057\u3066\u3001\u5143\u306e\u554f\u984c\u306e\u96e3\u3057\u3055\u3092\u3082\u3068\u306b\u5bfe\u8c61\u3068\u306a\u308b\u6697\u53f7\u3092\u89e3\u304f\u3053\u3068\u306e\u96e3\u3057\u3055\u3092\u3088\u308a\u3088\u304f\u4fdd\u8a3c\u3067\u304d\u308b\u304b\u3089\u3060\u3063\u305f\u308a\u3059\u308b\u3002 \u304c\u3001\u3044\u304b\u3093\u305b\u3093\u3001\u5b9f\u7528\u7684\u3058\u3083\u306a\u3044\u3002\u3053\u306e\u524d\u3001\u9375\u306e\u30b5\u30a4\u30ba\u3092\u8a08\u7b97\u3057\u3066\u3044\u3066\u3073\u3063\u304f\u308a\u3057\u305f\u3002Rege\u2026","height":"190","width":"100%","blog_title":"186 @ hatenablog","version":"1.0","url":"https://186.hatenablog.com/entry/20050423/1114238133","blog_url":"https://186.hatenablog.com/","provider_name":"Hatena Blog"}