{"id":34904,"date":"2020-01-16T00:45:19","date_gmt":"2020-01-15T16:45:19","guid":{"rendered":"https:\/\/case.ntu.edu.tw\/blog\/?p=34904"},"modified":"2020-04-13T12:10:06","modified_gmt":"2020-04-13T04:10:06","slug":"%e5%8f%af%e7%ae%97%ef%bc%9f%e4%b8%8d%e5%8f%af%e7%ae%97%ef%bc%9f%e9%80%99%e6%98%af%e5%80%8b%e9%9b%bb%e8%85%a6%e5%95%8f%e9%a1%8c","status":"publish","type":"post","link":"https:\/\/case.ntu.edu.tw\/blog\/?p=34904","title":{"rendered":"\u3010\u63a2\u7d2222-8\u3011\u53ef\u7b97\uff1f\u4e0d\u53ef\u7b97\uff1f\u9019\u662f\u500b\u96fb\u8166\u554f\u984c"},"content":{"rendered":"<p><span style=\"color: #333399;\"><strong>\u6211\u5011\u5728\u65e5\u5e38\u751f\u6d3b\u4e2d\u4eab\u53d7\u8457\u5404\u7a2e\u667a\u6167\u7522\u54c1\u6240\u5e36\u4f86\u7684\u65b9\u4fbf\uff0c\u7531\u65bc\u96fb\u8166\u5f37\u5927\u904b\u7b97\u80fd\u529b\u5e36\u4f86\u7684\u4f4e\u5ef6\u9072\uff0c\u5f88\u5bb9\u6613\u5c31\u8b93\u4eba\u5fd8\u8a18\u9019\u4e9b\u65b9\u4fbf\u5176\u5be6\u4f86\u81ea\u65bc\u96fb\u8166\u5728\u80cc\u5f8c\u9032\u884c\u7684\u5de8\u91cf\u904b\u7b97\uff0c\u4e5f\u5bb9\u6613\u5ffd\u7565\u96fb\u8166\u80fd\u89e3\u6c7a\u7684\u554f\u984c\u5176\u5be6\u6709\u5176\u9650\u5236\u3002\u8463\u4e16\u5e73\u6559\u6388\u5c07\u5f9e\u7c21\u55ae\u7684\u6578\u5b78\u554f\u984c\u51fa\u767c\uff0c\u4ecb\u7d39\u96fb\u8166\u7684\u53ef\u7b97\u6027\u3001\u53ef\u884c\u6027\uff0c\u63a2\u8a0e\u7576\u4eca\u96fb\u8166\u79d1\u5b78\u754c\u6578\u4e00\u6578\u4e8c\u91cd\u8981\u7684\u554f\u984c\uff0c\u5e36\u6211\u5011\u8a8d\u8b58\u73fe\u5728\u8a08\u7b97\u79d1\u5b78\u7684\u6a23\u8c8c\u3002<\/strong><\/span><\/p>\n<p><strong><img fetchpriority=\"high\" decoding=\"async\" class=\"alignleft wp-image-34907\" src=\"http:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2280.jpg\" alt=\"\" width=\"450\" height=\"299\" srcset=\"https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2280.jpg 1920w, https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2280-300x199.jpg 300w, https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2280-768x510.jpg 768w, https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2280-1024x679.jpg 1024w\" sizes=\"(max-width: 450px) 100vw, 450px\" \/>\u8b1b\u8005\uff5c\u4e2d\u539f\u5927\u5b78\u61c9\u7528\u6578\u5b78\u7cfb\u6559\u6388 \u8463\u4e16\u5e73<br \/>\n<\/strong><strong>\u5f59\u6574\u64b0\u6587\uff5c\u8607\u5efa\u7ff0<\/strong><\/p>\n<p><span style=\"color: #008080;\"><strong>\u25cf\u7c21\u55ae\u554f\u984c\u4e0d\u7c21\u55ae<\/strong><\/span><\/p>\n<p>\u5982\u4f55\u627e\u51fa\u300c x<sup>2<\/sup>-2x-15=0\u300d\u7684\u6574\u6578\u89e3\uff0c\u5728\u8ab2\u672c\u88e1\u5c31\u80fd\u5728\u4e00\u5143\u4e8c\u6b21\u65b9\u7a0b\u5f0f\u7ae0\u7bc0\u770b\u904e\u985e\u4f3c\u7684\u984c\u76ee\uff0c\u5c0d\u65bc\u67d0\u4e9b\u719f\u6089\u7684\u4eba\u4f86\u8aaa\u6216\u8a31\u53ea\u8981\u900f\u904e\u5fc3\u7b97\u5373\u53ef\u89e3\u6c7a\uff0c\u7136\u800c\u9019\u9053\u770b\u4f3c\u521d\u968e\u7684\u984c\u76ee\u771f\u7684\u6709\u90a3\u9ebc\u7c21\u55ae\u55ce\uff1f\u6211\u5011\u90fd\u77e5\u9053\u7c21\u55ae\u8207\u5426\u662f\u56e0\u4eba\u800c\u7570\u7684\uff0c\u90a3\u9ebc\u5c0d\u65bc\u96fb\u8166\u4f86\u8aaa\uff0c\u8981\u89e3\u9019\u9053\u984c\u76ee\u4e5f\u662f\u7c21\u55ae\u7684\u55ce\uff1f<\/p>\n<p>\u6b78\u529f\u65bc\u96fb\u8166\u5f37\u5927\u7684\u8a08\u7b97\u80fd\u529b\uff0c\u6709\u4e9b\u8f03\u55ae\u7d14\u7684\u6578\u5b78\u554f\u984c\u900f\u904ewolfram alpha\u7b49\u904b\u7b97\u5e73\u53f0\u53ea\u6d88\u7247\u523b\u5c31\u80fd\u7372\u5f97\u7b54\u6848\u3002\u5728\u9019\u770b\u4f3c\u4e0d\u8cbb\u5439\u7070\u4e4b\u529b\u7684\u904e\u7a0b\u80cc\u5f8c\uff0c\u7531\u65bc\u7121\u6cd5\u548c\u4eba\u985e\u4e00\u6a23\u9032\u884c\u62bd\u8c61\u601d\u8003\u4ee5\u53ca\u7d19\u7b46\u904b\u7b97\uff0c\u96fb\u8166\u5176\u5be6\u4ef0\u8cf4\u8a31\u591a\u6f14\u7b97\u6cd5\u4f86\u61c9\u5c0d\u4e0d\u540c\u7684\u6578\u5b78\u554f\u984c\u3002\u7121\u8ad6\u662f\u63a1\u53d6\u54ea\u7a2e\u65b9\u6cd5\uff0c\u9078\u64c7\u6bcf\u4e00\u500b\u65b9\u6cd5\u7684\u80cc\u5f8c\u90fd\u6709\u5176\u6578\u5b78\u7684\u7406\u7531\uff0c\u8b6c\u5982\u8981\u89e3\u958b\u524d\u8ff0\u4e00\u5143\u4e8c\u6b21\u65b9\u7a0b\u5f0f\u7684\u984c\u76ee\uff0c\u53ef\u4ee5\u900f\u904e\u66b4\u529b\u6cd5\u9032\u884c\u641c\u7d22\uff0c\u4e5f\u53ef\u4ee5\u900f\u904e\u56e0\u6578\u6cd5\u6e2c\u8a66\u56e0\u6578\u5206\u89e3\u5f8c\u5f97\u5230\u53ef\u80fd\u7684\u5019\u9078\u503c\u518d\u9032\u884c\u5224\u65b7\uff0c\u53c8\u6216\u8005\u53ef\u4ee5\u5229\u7528\u56e0\u5f0f\u6cd5\u76f4\u63a5\u9032\u884c\u56e0\u5f0f\u5206\u89e3\u5f97\u5230\u7b54\u6848\uff0c\u9019\u4e9b\u4e0d\u540c\u7684\u65b9\u6cd5\u80cc\u5f8c\u90fd\u6709\u5176\u6578\u5b78\u5b9a\u7406\u652f\u6490\u3002<\/p>\n<p><span style=\"color: #008080;\"><strong>\u25cf\u5e0c\u723e\u4f2f\u7279\u7b2c\u5341\u554f\u984c\u7684\u7b54\u6848<\/strong><\/span><\/p>\n<p>\u8b93\u6211\u5011\u66f4\u9032\u968e\u4e00\u9ede\uff0c\u601d\u8003\u5982\u4f55\u627e\u51fa\u300cx<sup>2<\/sup>-631y<sup>2<\/sup>-1=0\u300d\u7684\u6240\u6709\u6574\u6578\u89e3\uff0c\u6216\u8a31\u6709\u4eba\u4e00\u773c\u5c31\u80fd\u770b\u51fa\u4f86\uff0c(x,y)=( \u00b11,0)\u5373\u70ba\u5169\u7d44\u89e3\uff0c\u4e0d\u904e\u4e0b\u4e00\u7d44\u6574\u6578\u89e3\u7684\u6578\u91cf\u7d1a\u5df2\u7d93\u66b4\u6f32\u81f3x=48,961,575,312,998,650,035,560\u3001y=1,949,129,537,575,151,036,427\u3002\u7531\u6b64\u53ef\u4ee5\u770b\u51fa\uff0c\u5373\u4f7f\u53ea\u662f\u4e00\u500b\u7c21\u55ae\u4fc2\u6578\u7684\u4e8c\u5143\u4e8c\u6b21\u65b9\u7a0b\u5f0f\uff0c\u89e3\u7b54\u5f88\u5bb9\u6613\u5c31\u843d\u5728\u591a\u6578\u4eba\u8a08\u7b97\u7bc4\u570d\u4e4b\u5916\uff0c\u9762\u5c0d\u9019\u985e\u554f\u984c\uff0c\u6211\u5011\u53ef\u4ee5\u5bc4\u5e0c\u671b\u65bc\u96fb\u8166\u55ce\uff1f\u9019\u500b\u554f\u984c\u7684\u7b54\u6848\u4ee4\u4eba\u9a5a\u8a1d\uff0c\u81f3\u4eca\u70ba\u6b62\u300c\u6c92\u6709\u65b9\u6cd5\u300d\u53ef\u89e3\u6240\u6709\u7684\u4e8c\u5143\u6574\u6578\u65b9\u7a0b\u5f0f\u3002<\/p>\n<p>\u5341\u4e5d\u4e16\u7d00\u672b\uff0c\u5fb7\u570b\u6578\u5b78\u5bb6\u5e0c\u723e\u4f2f\u7279(David Hilbert, 1862-1943)\u63d0\u51fa\u4e86\u4e8c\u5341\u4e09\u9053\u6578\u5b78\u554f\u984c\uff0c\u671f\u671b\u80fd\u5728\u63a5\u4e0b\u4f86\u7684\u4e8c\u5341\u4e16\u7d00\u4e2d\u7372\u5f97\u56de\u61c9\u3002\u5176\u4e2d\uff0c\u7b2c\u5341\u9053\u554f\u984c\u5373\u662f\u8a62\u554f\u300c\u662f\u5426\u80fd\u627e\u5230\u4e00\u500b\u65b9\u6cd5\uff0c\u53ef\u4ee5\u5728\u6709\u9650\u7684\u6b65\u9a5f\u5167\uff0c\u6c7a\u5b9a\u4efb\u4e00\u500b\u6574\u6578\u65b9\u7a0b\u5f0f\u662f\u5426\u6709\u6574\u6578\u89e3\uff1f\u300d\uff0c\u9019\u500b\u554f\u984c\u5728\u6578\u5b78\u5bb6\u7684\u52aa\u529b\u4e0b\uff0c\u5f97\u5230\u7684\u7b54\u6848\u662f\u300c\u6c92\u6709\u65b9\u6cd5\u300d(MRDP\u5b9a\u7406)\uff0c\u9019\u500b\u7b54\u6848\u5f88\u6709\u8da3\uff0c\u8aaa\u4e0d\u5b9a\u4e5f\u51fa\u65bc\u7576\u5e74\u5e0c\u723e\u4f2f\u7279\u7684\u610f\u6599\u4e4b\u5916\uff0c\u800c\u9019\u500b\u300c\u6c92\u6709\u65b9\u6cd5\u300d\u7a76\u7adf\u662f\u4ec0\u9ebc\u610f\u601d\uff1f\u9019\u500b\u65b9\u6cd5\u7a76\u7adf\u5b58\u4e0d\u5b58\u5728\uff1f\u73fe\u5728\u4e0d\u77e5\u9053\u96e3\u9053\u4ee5\u5f8c\u4e5f\u4e0d\u77e5\u9053\u55ce\uff1f<\/p>\n<p>\u4efb\u4f55\u96fb\u8166\u80fd\u5920\u57f7\u884c\u7684\u5de5\u4f5c\u90fd\u662f\u675c\u6797\u6a5f\u53ef\u7b97\u7684\u554f\u984c\uff0c\u6839\u64da\u90b1\u6c60\u2014\u675c\u6797\u8ad6\u984c(Church\u2014Turing thesis)\uff0c\u4efb\u4f55\u53ef\u8a08\u7b97\u7684\u554f\u984c\uff0c\u90fd\u662f\u675c\u6797\u6a5f\u53ef\u7b97\u7684\uff0c\u76f8\u5c0d\u7684\u90a3\u4e9b\u675c\u6797\u6a5f\u4e0d\u53ef\u7b97\u7684\u554f\u984c\uff0c\u5c31\u662f\u88ab\u8a8d\u70ba\u300c\u6c92\u6709\u65b9\u6cd5\u300d\u53ef\u4ee5\u89e3\u6c7a\u7684\u554f\u984c\u3002\u6240\u8b02\u7684\u300c\u6c92\u6709\u65b9\u6cd5\u300d\u4e26\u4e0d\u7b49\u540c\u300c\u65b9\u6cd5\u5b58\u5728\u53ea\u662f\u9084\u6c92\u627e\u5230\u300d\uff0c\u66f4\u7cbe\u78ba\u4e00\u9ede\u7684\u8aaa\uff0c\u5176\u5be6\u5c31\u662f\u300c\u9019\u500b\u65b9\u6cd5\u4e0d\u5b58\u5728\u300d\uff0c\u5982\u679c\u5f9e\u8a08\u7b97\u7684\u89d2\u5ea6\u4f86\u8aaa\uff0c\u300c\u6c92\u6709\u65b9\u6cd5\u300d\u6307\u5f97\u5c31\u662f\u7121\u8ad6\u672a\u4f86\u96fb\u8166\u5982\u4f55\u767c\u5c55\uff0c\u7d66\u4e88\u4e0d\u53d7\u9650\u5236\u7684\u6642\u9593\u8207\u8cc7\u6e90\u4ecd\u7121\u6cd5\u900f\u904e\u96fb\u8166\u89e3\u6c7a\u3002\u9019\u4e00\u985e\u548c\u65b9\u7a0b\u5f0f\u6574\u6578\u89e3\u4e00\u6a23\u300c\u6c92\u6709\u65b9\u6cd5\u300d\u3001\u96fb\u8166\u7121\u6cd5\u89e3\u6c7a\u7684\u554f\u984c\uff0c\u6211\u5011\u5c31\u7a31\u4f5c\u662f\u300c\u4e0d\u53ef\u7b97\u554f\u984c\u300d\u3002<\/p>\n<p><span style=\"color: #008080;\"><strong> \u25cfP = NP?<\/strong><\/span><\/p>\n<p>\u524d\u8ff0\u91dd\u5c0d\u53ef\u8a08\u7b97\u6027\u7684\u8a0e\u8ad6\uff0c\u901a\u5e38\u662f\u4e0d\u9650\u6642\u9593\u8207\u7a7a\u9593\u7684\uff0c\u4e0d\u904e\u73fe\u5be6\u4e2d\u6240\u6703\u78b0\u5230\u7684\u554f\u984c\u5e38\u5e38\u6703\u9700\u8981\u5728\u53d7\u9650\u7684\u6642\u9593\u4ee5\u53ca\u8a18\u61b6\u9ad4\u7a7a\u9593\u4e0b\u89e3\u6c7a\uff0c\u5728\u6b64\u7a2e\u72c0\u6cc1\u4e0b\uff0c\u9700\u8981\u8003\u616e\u8a08\u7b97\u7e41\u5ea6\uff0c\u63db\u53e5\u8a71\u8aaa\uff0c\u6211\u5011\u9664\u4e86\u601d\u8003\u6709\u6c92\u6709\u65b9\u6cd5\uff0c\u4e5f\u60f3\u63a2\u7a76\u6709\u6c92\u6709\u8db3\u5920\u597d\u7684\u65b9\u6cd5\u3002\u8981\u6bd4\u8f03\u4e0d\u540c\u65b9\u6cd5\u7684\u597d\u58de\uff0c\u4f5c\u70ba\u8861\u91cf\u57fa\u6e96\u7684\uff0c\u901a\u5e38\u662f\u7576\u554f\u984c\u8b8a\u5f97\u975e\u5e38\u8907\u96dc\u6642\uff0c\u89e3\u6c7a\u554f\u984c\u6240\u9700\u8981\u82b1\u8cbb\u7684\u6642\u9593\u3002<\/p>\n<figure id=\"attachment_34905\" aria-describedby=\"caption-attachment-34905\" style=\"width: 946px\" class=\"wp-caption aligncenter\"><img decoding=\"async\" class=\"size-full wp-image-34905\" src=\"http:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2281.jpg\" alt=\"\" width=\"946\" height=\"541\" srcset=\"https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2281.jpg 946w, https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2281-300x172.jpg 300w, https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2281-768x439.jpg 768w\" sizes=\"(max-width: 946px) 100vw, 946px\" \/><figcaption id=\"caption-attachment-34905\" class=\"wp-caption-text\">\u5716\u4e00\u3001\u76ee\u524d\u5c0d\u8a08\u7b97\u7e41\u5ea6\u7684\u4e00\u7a2e\u731c\u6e2c(\u4f86\u6e90\uff1a\u81ea\u7e6a\uff0c\u53c3\u8003\u81ea\u8463\u4e16\u5e73\u6559\u6388\u6f14\u8b1b)<\/figcaption><\/figure>\n<p>&nbsp;<\/p>\n<p>\u675c\u6797\u6a5f\u53ef\u4ee5\u88ab\u5206\u6210\u78ba\u5b9a\u578b(deterministic)\u548c\u4e0d\u78ba\u5b9a\u578b(non-deterministic)\u5169\u985e\uff0c\u524d\u8005\u5373\u662f\u4e00\u822c\u901a\u7a31\u7684\u675c\u6797\u6a5f\uff0c\u5728\u904b\u4f5c\u4e2d\u7531\u7576\u524d\u7684\u503c\u548c\u72c0\u614b\u6c7a\u5b9a\u4e0b\u4e00\u6b65\uff0c\u56e0\u6b64\u4e0b\u4e00\u6b65\u53ea\u6709\u4e00\u7a2e\u53ef\u80fd\uff0c\u9019\u4e5f\u662f\u76ee\u524d\u96fb\u8166\u666e\u904d\u904b\u4f5c\u7684\u65b9\u5f0f\uff1b\u5f8c\u8005\u5247\u662f\u5728\u9078\u64c7\u4e0b\u4e00\u6b65\u6642\uff0c\u540c\u6642\u6709\u591a\u7a2e\u53ef\u80fd\u7684\u8def\u5f91\u53ef\u4ee5\u9078\u64c7\u3002\u8981\u6ce8\u610f\u7684\u662f\uff0c\u9019\u5169\u7a2e\u675c\u6797\u6a5f\u53ef\u4ee5\u89e3\u6c7a\u7684\u554f\u984c\u662f\u4e00\u6a23\u591a\u7684\uff0c\u5dee\u5225\u5728\u65bc\u5169\u8005\u4e4b\u9593\u6240\u9700\u8981\u7684\u6642\u9593\u4e0d\u4e00\u6a23\u3002\u5982\u679c\u4e00\u500b\u554f\u984c\uff0c\u53ef\u4ee5\u88ab\u78ba\u5b9a\u578b\u675c\u6797\u6a5f\u5728\u591a\u9805\u5f0f\u6642\u9593\u88ab\u89e3\u6c7a\u7684\u8a71\uff0c\u9019\u4e00\u985e\u554f\u984c\u6211\u5011\u5c31\u7a31\u70ba\u300c\u53ef\u884c(feasible)\u554f\u984c\u300d\uff0c\u4e00\u822c\u4ee5P\u4f86\u8868\u793a\uff1b\u76f8\u5c0d\u7684\uff0c\u4e0d\u5728P\u4e2d\u7684\u9019\u985e\u554f\u984c\u5c31\u662f\u300c\u975e\u53ef\u884c(Infeasible)\u554f\u984c\u300d\uff0c\u53ef\u4ee5\u88ab\u975e\u78ba\u5b9a\u578b\u675c\u6797\u6a5f\u5728\u591a\u9805\u5f0f\u6642\u9593\u88ab\u89e3\u6c7a\u7684\u8a71\uff0c\u9019\u4e00\u985e\u554f\u984c\u6211\u5011\u5c31\u7a31\u70baNP\u554f\u984c\uff0c\u53e6\u5916\uff0cNP\u5426\u5b9a\u554f\u984c\u7a31\u70baCO-NP\u554f\u984c\u3002\u5728NP\u554f\u984c\u4e2d\uff0c\u6700\u96e3\u7684\u4e00\u985e\u554f\u984c\u88ab\u7a31\u70baNP\u5b8c\u5099(NP-Complete, NPC)\uff0c\u5176\u5426\u5b9a\u554f\u984c\u5247\u7a31\u4f5cCO-NPC\u3002<\/p>\n<p>\u7576\u4eca\u5c0d\u8a08\u7b97\u7e41\u5ea6\u7684\u5206\u985e\u6709\u591a\u7a2e\u731c\u6e2c\uff0c\u800c\u5176\u4e2d\u88ab\u8a8d\u70ba\u662f\u96fb\u8166\u79d1\u5b78\u53ca\u6578\u5b78\u6700\u91cd\u8981\u7684\u554f\u984c\u4e4b\u4e00\u7684\uff0c\u5373\u662fP\u662f\u5426\u7b49\u540c\u65bcNP (P=NP?)\uff0c\u88ab\u5217\u5165\u514b\u96f7\u6578\u5b78\u7814\u7a76\u6240(Clay Mathematics Institute\uff0cCMI)\u61f8\u8cde\u4e00\u767e\u842c\u7f8e\u91d1\u7684\u4e03\u9053\u5343\u79a7\u5e74\u5927\u734e\u96e3\u984c\u4e4b\u4e2d\u3002P\u662f\u5426\u7b49\u65bcNP\u548c\u6578\u4f4d\u6642\u4ee3\u7684\u751f\u6d3b\u606f\u606f\u76f8\u95dc\uff0c\u73fe\u5728\u5e38\u7528\u7684RSA\u52a0\u5bc6\u6f14\u7b97\u6cd5\u5176\u6838\u5fc3\u662f\u7531\u8cea\u6578\u4e58\u7a4d\u4f86\u52a0\u5bc6\uff0c\u8cea\u6578\u4e58\u7a4d\u4e00\u822c\u88ab\u8a8d\u70ba\u662f\u4e00\u500b\u9677\u9631\u51fd\u6578\uff0c\u4e5f\u5c31\u662f\u8a08\u7b97\u5bb9\u6613\u4f46\u9006\u8f49\u8a08\u7b97\u76f8\u7576\u56f0\u96e3\u7684\u51fd\u6578\uff0c\u7834\u89e3\u5bc6\u78bc\u9700\u8981\u8cea\u56e0\u6578\u5206\u89e3\u9019\u662f\u500bNP\u554f\u984c\uff0c\u4e00\u65e6\u6211\u5011\u53ef\u4ee5\u8b49\u660eNP\u7b49\u65bcP\uff0c\u5c31\u53ef\u4ee5\u5c07NP\u8f49\u63db\u6210P\u554f\u984c\u4f86\u8655\u7406\uff0c\u7834\u89e3\u5bc6\u78bc\u5c07\u6703\u6210\u70ba\u53ef\u884c\u554f\u984c\uff0c\u5c0d\u73fe\u884c\u7684\u8cc7\u8a0a\u5b89\u5168\u5c07\u6703\u9020\u6210\u6975\u5927\u7684\u5a01\u8105\u3002<\/p>\n<p>\u5728\u7576\u524d\u7684\u96fb\u8166\u67b6\u69cb\u4e0b\uff0c\u5927\u90e8\u5206\u96fb\u8166\u79d1\u5b78\u5bb6\u7684\u770b\u6cd5\u70ba \uff0c\u56e0\u6b64\uff0c\u82e5\u4e00\u500b\u554f\u984c\u5df2\u7d93\u88ab\u8b49\u660e\u70baNP\u5b8c\u5099\uff0c\u5176\u6c42\u6700\u4f73\u89e3\u5247\u88ab\u8a8d\u70ba\u975e\u53ef\u884c\uff0c\u9047\u5230\u9019\u4e00\u985e\u975e\u53ef\u884c\u554f\u984c\uff0c\u96a8\u8457\u554f\u984c\u7684\u8907\u96dc\u5ea6\u589e\u52a0\uff0c\u5373\u4f7f\u76ee\u524d\u96fb\u8166\u904b\u7b97\u901f\u5ea6\u6210\u9577\u65e5\u65b0\u6708\u7570\uff0c\u8a08\u7b97\u80fd\u529b\u63d0\u5347\u6240\u5e36\u4f86\u7684\u89e3\u984c\u6548\u7387\u4e5f\u7121\u6cd5\u986f\u8457\u63d0\u5347\u3002<\/p>\n<p><strong><span style=\"color: #008080;\">\u25cf\u91cf\u5b50\u8a08\u7b97\u589e\u6dfb\u8a08\u7b97\u79d1\u5b78\u7684\u6a23\u8c8c<\/span><\/strong><\/p>\n<p>\u91cf\u5b50\u8a08\u7b97\u8fd1\u5e74\u4f86\u6210\u70ba\u71b1\u9580\u7684\u9818\u57df\uff0c\u5728\u78ba\u5b9a\u578b\u675c\u6797\u6a5f\u4ee5\u5916\u958b\u5275\u4e00\u689d\u4e0d\u540c\u7684\u8a08\u7b97\u5f62\u5f0f\u3002\u96d6\u7136\u91cf\u5b50\u8a08\u7b97\u7684\u53ef\u7b97\u6027\u8207\u78ba\u5b9a\u578b\u675c\u6797\u6a5f\u76f8\u540c\uff0c\u4e0d\u904e\u91cf\u5b50\u8a08\u7b97\u7684\u53ef\u884c\u6027\u8207\u78ba\u5b9a\u578b\u675c\u6797\u6a5f\u53ef\u80fd\u6709\u6240\u4e0d\u540c\uff0c\u6240\u4ee5\u4e5f\u591a\u4e86\u4e00\u7a2e\u8861\u91cf\u8a08\u7b97\u7e41\u5ea6\u7684\u6307\u6a19\uff0c\u7a31\u70baBQP(Bounded-error Quantum Polynomial Time)\u3002\u8b6c\u5982\uff0c\u5c0d\u65bc\u50b3\u7d71\u675c\u6797\u6a5f\u4f86\u8aaa\u662fNP\u7684\u56e0\u6578\u5206\u89e3\u554f\u984c\uff0c\u5c31\u6709\u591a\u9805\u5f0f\u6642\u9593\u7684BQP\u91cf\u5b50\u6f14\u7b97\u6cd5\uff0c\u56e0\u6b64\u6709\u4eba\u731c\u6e2c\u56e0\u6578\u5206\u89e3\u53ef\u4ee5\u6210\u70ba\u53ef\u884c\u554f\u984c\uff0c\u5982\u679c\u9019\u500b\u731c\u6e2c\u5728\u672a\u4f86\u88ab\u8b49\u5be6\u4e86\uff0c\u5c31\u5982\u4e0a\u8ff0\uff0c\u50b3\u7d71\u4e0a\u4f7f\u7528RSA\u52a0\u5bc6\u7684\u8cc7\u8a0a\u5c31\u9700\u8981\u53e6\u5c0b\u4ed6\u8def\u4f86\u4fdd\u8b77\u8cc7\u6599\u5b89\u5168\u3002<\/p>\n<p>\u96fb\u8166\u7684\u904b\u7b97\u80fd\u529b\u9032\u5165\u4e8c\u5341\u4e00\u4e16\u7d00\u4ee5\u4f86\u986f\u8457\u6210\u9577\uff0c\u53d7\u60e0\u65bc\u6b64\u8a31\u591a\u7814\u7a76\u3001\u5de5\u7a0b\u9818\u57df\u7522\u751f\u4e0d\u5c11\u61c9\u7528\uff0c\u8b93\u6211\u5011\u7684\u751f\u6d3b\u66f4\u4fbf\u5229\u3002\u5728\u61c9\u7528\u7aef\uff0c\u4e00\u5982\u524d\u9762\u63d0\u904e\u7684\u5c0b\u627e\u6574\u6578\u89e3\u3001\u8cea\u56e0\u6578\u5206\u89e3\u7b49\u554f\u984c\uff0c\u56de\u5230\u6700\u6e90\u982d\u7684\u6578\u8ad6\u3001\u8a08\u7b97\u79d1\u5b78\u4ecd\u6709\u8a31\u591a\u6709\u8da3\u7684\u3001\u91cd\u8981\u7684\u554f\u984c\u7b49\u5f85\u63a2\u7d22\uff0c\u9019\u4e9b\u554f\u984c\u80fd\u5426\u88ab\u89e3\u6c7a\u3001\u6709\u6c92\u6709\u7b54\u6848\uff0c\u5c07\u6703\u6c7a\u5b9a\u4e0b\u500b\u4e16\u4ee3\u8a08\u7b97\u7684\u9762\u8c8c\u3002<\/p>\n<figure id=\"attachment_34906\" aria-describedby=\"caption-attachment-34906\" style=\"width: 290px\" class=\"wp-caption aligncenter\"><img decoding=\"async\" class=\"size-full wp-image-34906\" src=\"http:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2282.jpg\" alt=\"\" width=\"290\" height=\"360\" srcset=\"https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2282.jpg 290w, https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2282-242x300.jpg 242w\" sizes=\"(max-width: 290px) 100vw, 290px\" \/><figcaption id=\"caption-attachment-34906\" class=\"wp-caption-text\">\u5716\u4e8c\u3001\u5c0d\u91cf\u5b50\u8a08\u7b97\u7684\u8a08\u7b97\u7e41\u5ea6\u731c\u6e2c\uff0c\u56e0\u6578\u5206\u89e3\u70ba\u5716\u4e0a\u7d05\u9ede(\u4f86\u6e90\uff1a\u81ea\u7e6a\uff0c\u53c3\u8003\u81ea\u8463\u4e16\u5e73\u6559\u6388\u6f14\u8b1b)<\/figcaption><\/figure>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><strong>--<\/strong><br \/>\n<strong>\u672c\u6587\u6574\u7406\u81ea\uff1a108\/12\/7\u7531\u8463\u4e16\u5e73\u8001\u5e2b\u5728\u81fa\u5927\u601d\u4eae\u9928\u570b\u969b\u6703\u8b70\u5ef3\u6240\u4e3b\u8b1b\u4e4b\u300c\u53ef\u7b97\uff1f\u4e0d\u53ef\u7b97\uff1f\u9019\u662f\u500b\u96fb\u8166\u554f\u984c\u300d\u6f14\u8b1b\u5167\u5bb9\u3002<\/strong><br \/>\n&nbsp;<br \/>\n<iframe src=\"https:\/\/www.youtube.com\/embed\/GhqAlFr5yxA\" width=\"560\" height=\"315\" frameborder=\"0\" allowfullscreen=\"allowfullscreen\"><\/iframe><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6211\u5011\u5728\u65e5\u5e38\u751f\u6d3b\u4e2d\u4eab\u53d7\u8457\u5404\u7a2e\u667a\u6167\u7522\u54c1\u6240\u5e36\u4f86\u7684\u65b9\u4fbf\uff0c\u7531\u65bc\u96fb\u8166\u5f37\u5927\u904b\u7b97\u80fd\u529b\u5e36\u4f86\u7684\u4f4e\u5ef6\u9072\uff0c\u5f88\u5bb9\u6613\u5c31\u8b93\u4eba\u5fd8\u8a18\u9019\u4e9b\u65b9\u4fbf\u5176\u5be6\u4f86\u81ea\u65bc\u96fb\u8166\u5728\u80cc\u5f8c\u9032\u884c\u7684\u5de8\u91cf\u904b\u7b97\uff0c\u4e5f\u5bb9\u6613\u5ffd\u7565\u96fb\u8166\u80fd\u89e3\u6c7a\u7684\u554f\u984c\u5176\u5be6\u6709\u5176\u9650\u5236\u3002\u8463\u4e16\u5e73\u6559\u6388\u5c07\u5f9e\u7c21\u55ae\u7684\u6578\u5b78\u554f\u984c\u51fa\u767c\uff0c\u4ecb\u7d39\u96fb\u8166\u7684\u53ef\u7b97\u6027\u3001\u53ef\u884c\u6027\uff0c\u63a2\u8a0e\u7576\u4eca\u96fb\u8166\u79d1\u5b78\u754c\u6578\u4e00\u6578\u4e8c\u91cd\u8981\u7684\u554f\u984c\uff0c\u5e36\u6211\u5011\u8a8d\u8b58\u73fe\u5728\u8a08\u7b97\u79d1\u5b78\u7684\u6a23\u8c8c\u3002<\/p>\n","protected":false},"author":20,"featured_media":34907,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3293,4371],"tags":[4517,4449,2139,4518],"aioseo_notices":[],"jetpack_featured_media_url":"https:\/\/case.ntu.edu.tw\/blog\/wp-content\/uploads\/2020\/01\/2280.jpg","_links":{"self":[{"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/posts\/34904"}],"collection":[{"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=34904"}],"version-history":[{"count":4,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/posts\/34904\/revisions"}],"predecessor-version":[{"id":34921,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/posts\/34904\/revisions\/34921"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=\/wp\/v2\/media\/34907"}],"wp:attachment":[{"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=34904"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=34904"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/case.ntu.edu.tw\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=34904"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}