使用者:Apppletree
大家好。我是一名研究生，目前在北京，希望為維基百科做一些貢獻。
2010年3月28日：希望能夠徵集對完善維基百科上計算複雜性理論相關條目有興趣的朋友，一起討論如何進行這項工作。
2008年4月6日：目前維基百科的中文版仍不能直接訪問，在我這裡需要通過代理，速度較慢。所以我可能還是會將精力放在英文維基上。
2008年8月8日：可能是托奧運的福，可以直接訪問這裡了。。逐漸做點事情吧，趁著暑假無聊。
下面的信息從User:Wing的頁面中拷貝過來
計算複雜性
[編輯]- 2010年3月28日：發現自己很不靠譜，維基上的寫作時斷時續。當然部分的與學校的網絡狀況有關。目前在美國，希望能時常進行一下相關的工作。特別的希望徵集有相同志願的朋友一起進行完善。如果你有這方面的興趣，請在我的討論頁留言。
- 2010年1月9日：研二第一學期快要過去了，準備繼續撰寫中文維基上複雜性相關的條目。
我認為目前，計算複雜性在中文維基上，應該側重普及基本概念和研究內容，而不一定要側重於前沿和系統化的總結之前的工作。這是由於計算複雜性是一個相對非常年輕的領域，目前少有中國研究人員在該領域進行研究。所以我想重要的是挖掘相關的內涵，引領讀者對其主要內容有較準備的理解，進而引發對該領域的研究興趣。
所以我目前感興趣的是一個小的項目：複雜性理論的歷史和主要研究者的貢獻。將在這個寒假進行。
- 2009年7月16日：目前關注計算複雜性相關條目的撰寫。由於計算複雜性是一個相對新起的研究領域，對相關專業詞彙的翻譯目前並無公開的定論，所以在這裡總結如下。
翻譯原則：原詞彙儘量參考英文維基相關的詞條。翻譯時，儘量採用日常工作時所用的翻譯，對維基百科中已有的詞條採取重定向的辦法進行連結。
命名規則：因為在實際工作中，我們更多的是使用複雜性類的縮寫，特別的一些複雜性類全稱所蘊含的理解並不是最直觀的理解方式，如NC）的全稱為Nick's Class，是為了紀念對此類電路進行了許多研究的Nick Pippenger。再比如 NP，其命名源自非確定性圖靈機（Non-deterministic Turing machine），而目前較為通用的理解是利用「關係定義式」。所以我們將複雜性類的縮寫當作方便的記號來去使用。
所以在該領域，存在著使用縮寫還是使用全稱作為主條目的問題。在英文維基上，兩者都是可能的，如對NP，其主條目名稱為「NP (complexity)」；而對AM，其主條目名稱為「Arthur-Merlin protocol」。在一般情況下，我們採取英文維基的命名標準。
基本詞彙
[編輯]- Computational complexity: 計算複雜性
- Complexity class: 複雜性類
- Decision problem: 判定性問題
- NP: 非確定性多項式時間複雜性類
- NP-complete: NP完備
- Interactive proof system: 交互式證明系統
- Arthur-Merlin protocol: 亞瑟-梅林協議
常用詞綴
[編輯]由於複雜性理論中常用到增添詞綴的方法來形成新的複雜性類，或形容一類問題的性質，我們在這裡對這些詞綴和它們的翻譯進行一些歸納：
- "co-": 後接複雜性類，例如coNP，coAM等。定義為對後接的複雜性類中的語言（或問題）做取補操作。當需要對後接複雜性類進行翻譯時，我們用「反」接複雜性類中文名，如對coNP，翻譯為「反非確定性時間複雜性類」；而大多數情況下，我們不對後接複雜性類進行翻譯，此時在複雜性類英文名後加「補」，如對coNP，翻譯為「NP補」。後者也是實際工作中的情況。更多例子：對AM，我們將coAM翻譯為AM補；
- "-complete": 前接複雜性類，例如NP-complete，PSPACE-complete等。翻譯為「完備」，作形容詞。如NP-complete，翻譯作NP完備；
- "-hard": 前接複雜性類，例如NP-hard，L-hard等。翻譯為「難」，作形容詞。如L-hard，翻譯作「L難」；
Reduction related | 歸約相關
[編輯]- Turing reduction:
- Karp reduction: