什么是共同事物？

Question

记号有什么作用 co- 前缀时的意思 co-NP, co-RE （递归可枚举），或 co-CE （可计算可枚举） ?

Answer 1

通常，在数学术语中，前缀 共同 指的是 双重的 在某种意义上。对于复杂性和可计算性类，前缀 共同 有固定的含义：如果 X 是一类决策问题，那么 共X 是一类问题，其 补充 是在 X. 。也就是说，如果问题“这个对象是否具有属性 $P$” X, ，然后问题“此对象是否有属性$ neg p $？”在 共X.

例如，RE 是以下类别 半可判定问题, ，即存在图灵机可以验证肯定答案的问题。Co-RE 是一类有图灵机可以验证否定答案的问题。RE 中存在但 co-RE 中没有的一个众所周知的问题是停机问题（直观上，您可以通过运行图灵机完成来验证图灵机是否停止，但如果机器永远运行，您将永远无法确定） 。

NP 是可以在多项式时间内验证解决方案的问题类别；等价地，NP 是非确定性图灵机可以在多项式时间内解决的一类问题。 钴纳米粒子 是一类可以在多项式时间内证明无解的问题。未知 $ ext{NP} = ext{co-NP}$。

Answer 2

在理论计算机科学的更代数方面，表示双重，例如 吉尔斯的答案, ，但它具有非常精确的解释。如果感兴趣的概念（假设 一个产品）在类别理论中被形式化，然后是双重的（一个 共同体）是相同的概念，箭头朝相反的方向发展。

一个简单的例子（却是抽象）是一个想法 代数, ，对于函数$ f $，是一对$ langle s， alpha：fs to s rangle $。代数在对数据类型进行建模的计算机科学中很重要。代数的双重 煤堡, ，这是一对$ langle s， alpha：s to fs rangle $。煤桥对于建模系统很重要。

当我们双重化时发生了什么？好吧，箭头$ fs to s $被逆转，获得$ s to fs $。

关于这个想法的很酷的事情之一是，所有适合一个概念的理论都适用于双重概念，其中所有箭头都被逆转。