1樓：
你的問題太巨集大，考慮下面乙個問題，是其特殊情況：
複雜性類多項式分層Polynomial Hierarchy是否有完全問題？
PH是被廣泛認為沒有完全問題的，如果有的那麼PH會塌縮到乙個固定的層（大部分計算複雜性研究者認為不會塌縮）;反之，如果PH會塌縮到乙個固定的層,那麼是有完全問題的。
所以判斷多項式分層Polynomial Hierarchy是否有完全問題，就等於判斷它是否塌縮，這是乙個很大的問題。
2樓：Qian Chen
好問題啊。不過第乙個問題不知道答案。。
個人感覺不存在完備性的複雜性類是因為沒有把它徹底分開。比如NP-complete 和 co-NP-complete都存在。但是現在還不知道NP= ？
co-NP。假設兩者不相等且互不包含，乙個推論就是集合（NPco-NP）不是
完備的。
證明： 假設X是（NPco-NP）-complete的。因為X屬於（NPco-NP）,不失一般性的假設X屬於NP。
那麼因為X是（NPco-NP）-complete的，所以任何乙個co-NP問題都可以在多項式時間內reduce到X上。又因為X屬於NP，那麼X又可以reduce到乙個NP-complete的問題上。所以根據transitivity 所有co-NP問題都可以reduce到NP-complete問題上。
所以可以推出co-NPNP。
但是第二個問題「採用什麼方式定義的複雜性類才有這樣的完備問題？」 相對而言開放性就比較大了。。。當然存在這樣的定義方式啦。
只要隨便挑乙個問題X然後定義為所有可以在多項式時間內reduce到X上的問題構成的集合就可以啦！那這個集合是完備的，因為X根據定義就是乙個-complete的問題。^-^
3樓：
看錯題了，重新回答。
沒有，如果有的話，最明顯的結論就是NP=P，因為對於乙個屬於P的問題，在得到乙個可行解的情況下，通過PTIME可以reduce得到乙個NP問題的解，那顯然這個NP問題可以通過多項式時間解決，所以NP=P。
有哪些見過的時間複雜度為無限大的演算法？
梁六喵 看見過一種奇葩的排序方法，叫睡眠排序，每個資料乙個執行緒，sleep的時間是資料的值，資料小的先喚醒，資料大的後醒，按照醒來的順序自然就排好了，不知道這個時間複雜度怎麼算 停機問題判定演算法，由於停機問題不可解所以時間複雜度是無窮大 upd 據其他答主所說，似乎時間複雜度無窮大就不滿足 演算...
如何以O N 的時間複雜度找到N N矩陣的乙個區域性最小值？
假設你這個矩陣是個凸凹不平的面，那麼極值就是面和另外乙個平行平面相切的地方，梯度下降法就可以，二階偏導數為零即是極值點，但區域性最小值沒什麼意義，區域性到底多大，哪個區域性你又沒給出。修改一下，O N 時間只夠掃瞄常數條線，所以既然你說了，那肯定是打靶法，先打 2個離散點，再判斷周圍九宮格，過濾重複...
為什麼隨著系統的複雜度越來越高，一些定律就是解釋起來很困難，比如由粒子物理定律到化學定律？
幾年前弟弟問我化學和物理的區別是什麼，旁邊兩個妹妹也都看過來。我說 你們都知道手機怎麼用吧 停頓 但你們知道手機怎麼造嗎？宇宙就是由簡單向複雜演化的乙個過程。最初只有幾條甚至可能是一條 簡單 的規則，在最初的極端狀態下是有可能無中生有的。我們都知道量子起伏，在當前宇宙普通環境，或者說低能量狀態下，允...