論P, NP, NP-Complete, NP-Hard問題

-
deterministic Turing machine(DTM)
確定性圖靈機 		Nondeterministic Turing machine (NTM)
非確定性圖靈機
DTM跟NTM的差別
最早的有限狀態機。
狀態儲存關於過去的資訊，就是說：它反映從系統開始到現在時刻的輸入變化。
轉移指示狀態變更，並且用必須滿足確使轉移發生的條件來描述它。
動作是在給定時刻要進行的活動的描述。
有多種類型的動作：
進入動作（entry action）：在進入狀態時進行
退出動作（exit action）：在退出狀態時進行
輸入動作：依賴於當前狀態和輸入條件進行
轉移動作：在進行特定轉移時進行
 非確定型圖靈機和確定型圖靈機的不同之處在於，在計算的每一時刻，
根據當前狀態和讀寫頭所讀的符號，機器存在多種狀態轉移方案，
機器將任意地選擇其中一種方案繼續運作，直到最後停機為止。
如果給予 Turing machine 某個 state 和某個 symbol 下，它的下一步如果只有一種可能。
那我們就稱它為 deterministic Turing machine (DTM)。		 非確定性圖靈機（NTM）是一種理論計算模型，其控制規則在某些給定情況下指定了多個可能的動作。
也就是說，NTM的下一個狀態不是完全由其動作和它所看到的當前符號決定的
如果有一群演算法用DTM來做計算所需時間是 polynomial time，那這類演算法或問題被稱為Ｐ問題，Ｐ就是 polynomial-time 的縮寫。 另外如果有一群演算法用NTM來做計算所需時間是 polynomial time，那這類問題被稱為NP問題，NP是 non-deterministic polynomial-time 的縮寫。



P NP NP-Complete NP-hard
一個問題若存在有演算法，其時間上限為O(P(n))，
P(n)為n之多項式時，此一演算法即為有效率的演算法。
n為問題大小(即資料數量) 		若一個問題X可以找到non-deterministic algorithm 來處理，
而且演算法執行時間為O(P(n))，則稱X為NP-problem。。
  • 它是一個NP問題
  • 其他屬於NP的問題都可在多項式時間內歸約成它。
 如果任何一個NP problem Y 皆可以滿足Y∝X
則稱Problem X為NP-hard problem則稱Problem X為NP-hard problem
the Cook–Levin theorem, also known as Cook's theorem,
states that the Boolean satisfiability problem is NP-complete.
That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine
to the Boolean satisfiability problem.
證明了布爾可滿足性問題（SAT）是NP完全問題。
換句話說，任何NP裡面的問題可以在多項式時間內，
使用圖靈機，將之歸約成「一個布林方程式是否存在解」這個問題。
NP關係
NP關係
史蒂芬庫克(Stephen Cook)證明了一個十分重要的性質：
性質(A)：「任一個 NP 內的問題都可以，在多項式時間內，被轉換成滿足問題。」
性質(B)：「任一個 NP 內的問題都可以，在多項式時間內，被轉換成任一個 NP-complete 問題。」
性質(C)：「任一個 NP 內的問題都可以，在多項式時間內，被轉換成任一個 NP-hard 問題。」
性質(D)：「滿足問題在集合 P 中，若且唯若，P=NP。」

留言

張貼留言

這個網誌中的熱門文章

[HTML]標籤-下

-
圖片
[HTML]標籤-上 定義清單(Define list)  <dl>  <dt>標題 </dt>  <dd>內容一 </dd>  <dd>內容二 </dd>  <dd>內容三 </dd>  </dl> 範例 前端技術 html css javascript 後端技術 C# java python 連結  <a href='http://www.google.com.tw'>Google</a>     Google 父網頁存取子網頁路徑 同資料夾下 < a href ='檔案名稱'>同資料夾檔案</ a > 子資料夾 < a href ='子資料夾名稱/檔案名稱'>子資料夾檔案</ a > 孫資料夾 < a href ='子資料夾名稱/孫資料夾名稱/檔案名稱'>孫資料夾檔案</ a > 依此類推 子網頁存取父網頁路徑 父資料夾網頁 < a href =' ../檔案名稱' >同資料夾檔案</ a > 祖資料夾網頁 < a href ='../../檔案名稱'>子資料夾檔案</ a > 新視窗中開啟網頁 < a href = '網頁網址' 'target' = '_blank'...
Read more »

[Python]基礎課程

-
Python 起源 1991年Python正式誕生 Python底層是由Ｃ語言開發的直譯器 Python由Python軟體基金會管理 Python 相較於其他語言優勢 較受歡迎的主流語言 入門檻較低 應用多元 Python 應用的領域 資料科學 人工智慧 開發/管理網站 遊戲開發 .. 目前主流的開發環境 網路開發 Google Colaboratory 本機開發 Anaconda
Read more »

[系統]解除電腦限制頻寬

-
圖片
  第1步 在鍵盤上按下win+R，然後輸入 gpedit.msc 第2步  電腦設定 →  系統管理範本 →  網路 →  QoS封包排程器 第3步  限制可保留的頻寬 第4步  勾選已啟用→頻寬限制0 Windows找不到 gpedit.msc 怎麼辦? 第1步 在鍵盤上按下win+R，然後輸入   regedit 第２步 HKEY_CURRENT_USER → Software → Policies → Microsoft → MMC 按照路徑點擊就能找到了 點進去將數值設為０就可以了 第３步 如果沒有找到的話，可以自己建一個 在桌面新增一個筆記本文件，輸入下面這段程式碼，存檔- 副檔名要改成．ｂａｔ @echo off pushd "%~dp0" dir /b %SystemRoot%\servicing\Packages\Microsoft-Windows-GroupPolicy-ClientExtensions-Package~3*.mum >List.txt dir /b %SystemRoot%\servicing\Packages\Microsoft-Windows-GroupPolicy-ClientTools-Package~3*.mum >>List.txt for /f %%i in ('findstr /i . List.txt 2^>nul') do dism /online /norestart /add-package:"%SystemRoot%\servicing\Packages\%%i" pause 然後用系統管理員身分執行就可以了
Read more »

[HTML]標籤-上

-
[HTML]標籤-下 教學網站 開發環境 VS Code 開發環境 html 結構 : ! + Tab 測試文字 : lorem + Tab 開啟Go live 大綱 所有標籤都要用<tag>開頭 </tag>結尾 標題 <h1< h1標題樣式 <h2> h2標題樣式 <h3> h3標題樣式 <h4> h4標題樣式 <h5> h5標題樣式 <h6> h6標題樣式 段落 <P> 粗/斜體 <b> 粗體 <strong> 強調 <i> 斜體 <em> 斜體強調 上/下標 <sup>上標 E=MC 2 <sub>下標 CO 2 換行 < br/ >可以忽略開頭標籤 空白 ...
Read more »

[AlaSQL] 多data查詢+累計

-
Total_Sales 表格 Name Sales John 10 Jennifer 15 Stella 20 Sophia 40 Greg 50 Jeff 20 要算出累積總計，我們就鍵入以下的 SQL 語句： SELECT a1.Name, a1.Sales, SUM(a2.Sales) Running_Total FROM Total_Sales a1, Total_Sales a2 WHERE a1.Sales <= a2.Sales OR (a1.Sales=a2.Sales AND a1.Name = a2.Name) GROUP BY a1.Name, a1.Sales ORDER BY a1.Sales DESC, a1.Name DESC; 結果: Name Sales Running_Total Greg 50 50 Sophia 40 90 Stella 20 110 Jeff 20 130 Jennifer 15 145 John 10 155 var sql =  SELECT a1.Name, a1.Sales, SUM(a2.Sales) Running_Total FROM ? a1, ? a2 WHERE a1.Sales <= a2.Sales OR (a1.Sales=a2.Sales AND a1.Name = a2.Name) GROUP BY a1.Name, a1.Sales ORDER BY a1.Sales DESC, a1.Name DESC; "       Com_data = alasql(sql, [ Total_Sales  ,  Total_Sales  ])    
Read more »

How to Check the MySQL Version

-
  From the Command Line Use the following command to check the version of your local MySQL server. This command is not specific to any operating system. This command is compatible with all Linux, Windows, and macOS versions running MySQL. mysql -V  Here is the output. # mysql -V mysql Ver 14.14 Distrib 5.7.15, for Win32 (AMD64)   SELECT VERSION Statement Use the  SELECT VERSION()  command in the MySQL database client to check the MySQL version. SELECT version(); Here is the output. MariaDB [***]> SELECT version(); +-----------------+ | version() | +-----------------+ | 10.3.37-MariaDB | +-----------------+ 1 row in set (0.000 sec)
Read more »

[SQL Sever] 日期時間

-
SQL Server 中，有這些型態來表示日期： DATE  型態 - 格式是 YYYY-MM-DD DATETIME  型態 - 格式是 YYYY-MM-DD HH:MI:SS SMALLDATETIME  型態 - 格式是 YYYY-MM-DD HH:MI:SS SQL Server GETDATE()  取得現在的日期時間 DATEPART()  取出日期時間中特定的部分 DATEADD()  增加或減少指定的時間間隔 DATEDIFF()  日期相減 CONVERT()  格式化日期時間顯示 SQL Server GETDATE() 取得現在的日期時間 在 SQL Server 你可以使用 GETDATE() 函數來取得當前的日期時間。 GETDATE() 語法 (Syntax) GETDATE() GETDATE() 用法 (Example) 這個 SQL： SELECT GETDATE () AS CurrentDateTime 會得到現在的日期時間例如： 2018 -11-30 13 :10 :02.047 SQL Server DATEPART() 取出日期和時間中特定的部分 在 SQL Server 中，我們可以用 DATEPART() 函數來取出日期和時間中特定的部分，比如年、月、日、時、分、秒等。 DATEPART() 語法 (Syntax) DATEPART(datepart , date) DATEPART() 會返回一個整數，其中 datepart 參數用來指定要返回的部分，datepart 可以是這些值： datepart (全名和縮寫) 返回值說明 year, yyyy, yy 年，例如 2007 month, mm, m 月，例如 10 day, dd, d 日，例如 30 hour, hh 時，例如 12 minute, n 分，例如 15 second, ss, s 秒，例如 32 millisecond, ms 毫秒，例如 123 microsecond, mcs 微秒，例如 123456 nanosec...
Read more »

python 套件安裝指令

-
  Table 一. 什麼是 pip 和為什麼需要他？ 二. 如何安裝 pip ? ▍安裝 pip 前請留意 ▍Mac 的朋友安裝 pip 看這邊 ▍Windows 的朋友安裝 pip 看這邊 ▍Linux 的朋友安裝 pip 看這邊 三. pip 指令全記錄 pip 安裝套件 pip 更新套件 pip 移除安裝過的套件 查看目前安裝過的 python 套件清單 四. 如何使用 pip 一次安裝多個套件 一. 什麼是 pip 和為什麼需要他？ pip – The Python Package Installer ¶ pip is the  package installer  for Python. You can use pip to install packages from the  Python Package Index  and other indexes. HTTPS://PIP.PYPA.IO/EN/STABLE/ 就如同上述  pip 官方說明  所述，pip 是一個 Python 安裝管理套件工具，如果你今天要使用任何與 Python 有關的套件，基本上都會用到 pip 來安裝或是更新 Python 相關套件唷！ 二. 如何安裝 pip ? ▍安裝 pip 前請留意 目前 Python 3 的 3.4 版本以上 或是 Python 2 的 2.7.9 版本以上的 Python 都已經自帶 pip 了! 所以如果不是 Python 版本過舊的話，基本上不用需要安裝 pip 唷！ 想要查詢目前使用的 Python 版本的話，在終端機中輸入以下指令，就可以知道目前的 Python 版本囉： 1 2 3 $ python -- version   > Python 3.7.7 ▍Mac 的朋友安裝 pip 看這邊 1. 到  pip document 官方網站  建議的載點下載 pip 安裝檔 1 $ curl https : //bootstrap.pypa.io/get-pip.py -o get-pip.py 2. 啟動剛剛下載好的 get-pip.py 檔案，就安裝完成囉！ 1 $ python get - pip . py 3. ...
Read more »

Mysql Event Not Working

-
檢查排程是否有開啟 SELECT @@event_scheduler; SELECT @@global.event_scheduler; 設定開啟 SET GLOBAL event_scheduler = ON ; How to force an event to execute in MySQL Move all the code within the event into a stored procedure Make the event only call the stored procedure Test the stored procedure with the CALL syntax.
Read more »