1樓：Shangyin Tan
你的題目和地下的文字不對應。另外，證明TSP屬於NP，只要有P的YES的certifier就可以了。你說的NO，假如有P的驗證的話，那TSP就是coNP的了。
我們現在知道TSP屬於NP，但我們不知道NP是不是等於coNP。現在NP=coNP還是open problem。
2樓：
證明問題屬於NP，不用從3SAT出發多項式(時間)歸約，那是證明下界。屬於NP是要證上界。只需要給出乙個非確定的多項式時間求解演算法（猜測-檢驗模式的演算法），即樓上說的利用多項式時間可檢驗來證，再或者利用NP=PCP(logn,1)的表徵，證明它存在概率可檢驗系統。
證明完全性是要證明上、下界。不清楚的話，建議翻一下Spiser的教材，唐常傑老師有中譯本。
3樓：李欣宜
一般我們說的TSP是求最短路徑，所以也沒有存在不存在這一說，最短路徑一定是存在的。看問題的意思應該是把TSP描述成類似這樣的decision problem，那麼就可以當作Hamiltonian cycle problem的乙個特殊形式了
對於decision problem來說，可以在多項式時間內被verify的solution指的是給出的乙個具體的解，在這個問題裡面指的是演算法X給出某個迴路C作為問題的解，我們可以去verify這個C是否cover了所有的頂點和邊，是否是乙個Hamiltonian cycle，是否滿足長度<=k……
但演算法X對於某個圖G直接聲稱不存在這樣的迴路，那麼它針對的就是decision而非給出solution了，這裡的decision就是存在性本身。或者也可以理解為給出了乙個空的解集，verify這個空集內所有的solution當然也是在多項式時間內的。
當然，題外話，這樣去classify NP-complete problem的場合很少，一般還是互相reduce來判斷是否為NP-complete problem
如何評價旅行商問題（TSP）的幾種常用求解演算法？
林光爵 模擬退火演算法可以迅速將徑長壓到極低，對1000個拜訪點的旅行計畫，可以壓低徑長到真正最低值的1.01倍。模擬退火不是乙個好命名，應叫做徐徐降溫法，或叫徐冷法。怎麼降溫呢？就是當看到一旅行計畫 a.b c.d e.f 其中 a b c d e f 都是平面上一點 而 表示其中間還有很多點不列...
如何證明如下的問題？
黃俊文 關於這個問題，我有乙個大概的思路，但是中間會遇到問題，下面我闡述一下思路 先說說A這個集合的大小，通過題設結論可以看出A應該是乙個無限集，但其實問題就在這裡，對於題中所限定的多項式，我們很難證明其定義的A是乙個無限集，我猜測通過初等的手段只能證明 次數不大於2的情況。這種情況只需要計算A中數...
如何證明這個級數問題？
畦哇矽 問題 設 為實數列，定義 求證 若數列 有界且 則 我們的核心思路是，假設沒有，於是 會無限次地遠離 又因為 所以 會無限次地靠近 因為 受到限制，所以 在一次靠近和一次遠離之間行進得很慢，經歷了很多很多項才從 靠近狀態 變成 遠離狀態 而這麼多項離 靠近狀態 越來越遠的值能夠對平均數造成比...