求解任一考卷上(decidable)是非題在polynomial time可reduce成SAT問題？

最近在想一個問題，

令問題X為，求取求解任一考卷上decidable的是非題的程序，

X 是否在polynomial time能reduce to SAT(satifiability) problem？

我假設，考卷上的是非題目其中一題，是有限個字的，為n個字。

且所用的字，可以在一本符號大全的書上找到，

而這本書有X'個符號，(包含空字元符號)，這我們把題目上的每一個字用logX'取上高斯的bit數來表示，

令bit數為K。則我們可以設計一SAT Algorithm把題目每一個字都輸入下去，看是否satisfy。

總共是輸入nk個bit看是否satisfy，若是satisfy 則 輸出為圈，否則輸出為叉.

所以求解任一考卷上的(decidable)是非題的問題應該是能在polynomial time reduce to SAT problem的!

再想想，若不是是非題的情況，

則假設答案是有限個字所能表示的情況，令最多可用i個字表示，

因為所選的符號書包含空字元符號，所以答案實際上為j個字<=i,

而答案是什麼，可想成答案中每一個字元的第y個bit是否為1 ，(y有i*k個)，

若satisfy則為1。所以要run SAT i*k次。

PS. any NP problem reduce to SAT is trivial, but SAT reduce to NP problem X, X is called NP-Complete.

後記：所以這結論是trivial的…

NP Problem

這一、兩天花了一些時間在研究啥是NP,NP-Complete,NP hard,

首先介紹P,是找得到polynomial time可解決的problem,

而NP problem 就是Non-determistic polynomial time problem,

也就是找得到nd-choice在polynomial time可解決的problem.

至於NP hard:有一problem X,而所有的NP problem在polynomial time可reduce to X,

稱problem X為NP hard.

在這邊reduce指的是: A is reducible to problem B, 表示解了B就可以解決A問題,所以計算A問題,

不比計算B問題複雜(A cannot be harder than solving B)

NP-Complete:若是一個problem 屬於NP,也屬於NP hard,則此problem 是NP-COmplete.

而且若是一個NP-Complete problem存在一polynomial time的解法，

則所有NP problem都有 polynomial time的解法。

燒肉粽專賣店

喜歡吃燒肉粽的朋友有福了，
中和安和路上，有一家燒肉粽大賣場哦，
裡面有賣粽子、四神湯、人參雞湯、碗桂…等，
他的粽子，有分南部水煮粽、北部蛋黃三寶粽…等，
是難得一見的肉粽專門店哦，
詳細地址在：台北縣中和市安和路141號
老饕麼可以去嚐一嚐^^

小明式哲學

有一天，全班最後一名，想到一個問題很苦惱：
就去問他旁邊的同學，
請問:鯨魚跟人，在神的評價中，哪個好？
他同學回答，你看鯨魚那麼大，當然是鯨魚好。
過了幾天，最後一名又想到一個相關的問題，
就去問小英:汽車跟人，在神的評價中，哪個好？
小英回答:在神的評價中，都是一樣的。
又過了幾天，最後一名又很苦惱，
他決定向小明請教這最難的一題，
他問:人和狗，在神的評價中哪個好？
小明很認真的回答：
狗大便比較小，人的大便比較大。
狗對地球的汙染比人小，
所以結論是…
最後一名：?
小明:人不如狗!