為什么？因為如果一個決策問題是可以有效地解決的，那就意味著我們可以有效地找到它的解決方案 。
然后，給出一個解決方案，我們可以簡單地通過與問題的實際解決方案比較來驗證它 。換句話說，生成解決方案的算法的正確性自動證明了該解決方案 。
從這個結(jié)論可以看出，很明顯，NP包含的問題子集也是有效可解的 。這個子集被定義為P 。
- P是所有可有效解決的決策問題的集合，是NP的一個子集 。基本算法是多項式時間可解的 。象棋決策問題不屬于NP問題，因為沒有一種有效的算法可以檢查給定的棋盤是否有效 。魔方?jīng)Q策問題屬于NP問題，因為判斷一個給定的魔方是否是一個解是很簡單的 。
另一方面，沒有證據(jù)表明這樣的算法不存在 。事實上，這樣的算法仍然有可能存在，而且還沒有被發(fā)現(xiàn) 。數(shù)獨的決策問題也是一樣 。
事實上，對于許多其他主要問題，包括布爾可滿足性問題，旅行推銷員問題，子集和問題，派系問題，圖著色問題——盡管我們已經(jīng)證明這些問題是NP，但沒有證據(jù)表明他們在P。這就是P=NP問題的意義所在：
P和NP真的是一樣的嗎？
如果是的話，這就意味著NP中的所有問題都可以被有效地解決，盡管我們?nèi)匀粵]有找到實現(xiàn)這一點的神秘算法 。否則，在NP中存在一些無法有效解決的問題，任何嘗試解決將意味著浪費我們的時間和精力 。
大多數(shù)時候，不能有效地解決問題是一件消極的事情 。然而，在某些情況下，我們可以從問題的“硬度”中獲益 。屬于NP而不屬于P的問題，其主要特點是很難解決，但很容易驗證其解決方案 。
給定兩個正整數(shù)n和k，判斷n是否有一個質(zhì)因數(shù)小于k 。——質(zhì)因數(shù)分解決策問題
由于該問題的解可以有效地驗證，因此我們知道該問題屬于NP，給定一個整數(shù)c，它需要“多項式時間”來知道c是否是一個比k小的質(zhì)數(shù)，還是n的因數(shù) 。
但是，目前還沒有一種算法可以在多項式時間內(nèi)解決這一問題 。因此，使用兩個相當大的質(zhì)數(shù)，就可以計算它們的乘法，這用于生成一個公鑰和一個私鑰 。
公鑰可以為所有人所知，并用于加密消息 。使用公鑰加密的消息只能在合理的時間內(nèi)使用私鑰解密，假設(shè)沒有有效的方法將一個大整數(shù)分解為它的質(zhì)數(shù)因子 。
猜你喜歡
- 錦鯉一般養(yǎng)幾條最好 錦鯉是什么魚
- 瑤的銘文怎么配最強 這套銘文絕對強
- 大自然中的指南針有哪些? 大自然中的指南針是什么
- fgo黑貞技能材料
- 目前智能手機內(nèi)存最大是哪幾款 內(nèi)存最大的手機排行
- 購買的基金應(yīng)該賣出的最佳時間 基金什么時候賣出最合適
- 懷舊服法師裝備搭配 原來這樣搭配最厲害
- 冬天養(yǎng)生吃五種蔬菜 5種冬季最養(yǎng)生的蔬菜介紹
- 最火qq名字 qq的名字大全
- 財神應(yīng)該擺在哪里最招財 財神擺在哪里好