User: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:
工作工具
[编辑]Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
