論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 nanosecond, ns 毫微秒，例如 123456700 quarter, qq,
Read more »

推薦使用的9款編程字體

-
圖片
  1、Consolas Consolas是一套等寬字體的字型，屬無襯線字體，由Lucas de Groot設計，這套字型使用了微軟的ClearType字型平滑技術，非常好看 2、Menlo Menlo也是一個無襯線等寬字體，由Jim Lyles設計，首次出現於2009年8月上市的Mac OS X Snow Leopard系統內建字體之一。 Menlo 之前是Xcode 中的默認字體，是DejaVu Sans Mono 的衍生品。 3、Source Code Pro Source Code Pro 是Adobe 公司號稱最佳的編程字體。 而且還是開源的。 它非常適合用於閱讀代碼，支持Linux、Mac OS X 和Windows 等操作系統，而且無論商業或個人都可以免費使用。 下載地址： https://  github.com/adobe-fonts/  source-code-pro 4、Monaco Monaco 字體是OS X 系統默認的字體，與Consolas 一樣都非常適合程序開發人員，很明顯一股濃濃的蘋果風味 5、Hack Hack 是一種專門用來顯示編程語言的字體，其基於Bitstream Vera 和DejaVu 項目的開源字體， 0O以及1lI等都清晰可辨，是碼農的福音。 下載地址： https://  github.com/source-found  ry/Hack 6、Fira Code Fira 是Mozilla 公司主推的字體系列。 Fira Code 是其中的一員，專為寫程序而生。 出來具有等寬等基本屬性外，還加入了編程連字特性（ligatures）。 Fira code 其實基於Fira Mono 字體，然後對操作符做了特殊處理，這樣更符合通常的閱讀習慣。 下載地址： https://  github.com/tonsky/FiraC  ode 7、Droid Sans Mono Droid Sans Mono也是專為編程人員打造的一款字體，字體看起來平滑大氣，整體上給人一種舒適的感覺。 8、Lucida Sans Typewriter Lucida Sans Typewriter字體是一款擁有高辨識性的經典等寬字體，字型乾淨大氣，易讀性出色，就像是打字機打出來的字體一樣，可用於網頁設計或編程設計 9、Anonymous Pro An
Read more »

類別型態 vs 基本型態

-
基本型態 類別型態 目的 效率 類型 long、int、double、float、boolean、byte Long、Integer、Double、Float、Boolean、Byte 語法 基本型態 變數名= XX; 類別型態 變數名=new 類別型態(); 自動裝箱(Auto Boxing) 您要使用包裹型態（Wrapper Types）才能將基本資料型態包裝為物件，前一個小節中您已經知道在 J2SE 5.0 之前，要如下才能將 int 包裝為一個 Integer 物件： Integer integer = new Integer(10); Long k=new Long(0); 在 J2SE 5.0 之後提供了自動裝箱的功能，您可以直接如下撰寫來包裹基本型態： Integer integer = 10; Long k=0L; 自動拆箱(unboxing) public class AutoBoxDemo2 { public static void main (String[] args) { Integer i1 = 100 ; Integer i2 = 100 ; if (i1 == i2) System.out.println( "i1 == i2" ); else System.out.println( "i1 != i2" ); } } Integer pool 的範圍為1byte :-127~128 物件型態的處理時間比基本型態還慢!!! class wrapperclass { public static void main ( String[] args ) { long
Read more »