复杂度完备是否有统一的处理方式
好问题啊。不过第一个问题不知道答案。。个人感觉不存在完备性的复杂性类是因为没有把它彻底分开。比如NP-complete 和 co-NP-complete都存在。但是现在还不知道NP= ？co-NP。假设两者不相等且互不包含，一个推论就是集合（NP
co-NP）不是完备的。证明： 假设X是（NP
co-NP）-complete的。因为X属于（NP
co-NP）,不失一般性的假设X属于NP。那么因为X是（NP
co-NP）-complete的，所以任何一个co-NP问题都可以在多项式时间内reduce到X上。又因为X属于NP，那么X又可以reduce到一个NP-complete的问题上。所以根据transitivity 所有co-NP问题都可以reduce到NP-complete问题上。所以可以推出co-NP
NP。但是第二个问题“采用什么方式定义的复杂性类才有这样的完备问题？” 相对而言开放性就比较大了。。。当然存在这样的定义方式啦。只要随便挑一个问题X然后定义
为所有可以在多项式时间内reduce到X上的问题构成的集合就可以啦！那这个集合是完备的，因为X根据定义就是一个 【复杂度完备是否有统一的处理方式】
-complete的问题。^-^
■网友
你的问题太宏大，考虑下面一个问题，是其特殊情况：复杂性类多项式分层Polynomial Hierarchy是否有完全问题？PH是被广泛认为没有完全问题的，如果有的那么PH会塌缩到一个固定的层（大部分计算复杂性研究者认为不会塌缩）;反之，如果PH会塌缩到一个固定的层,那么是有完全问题的。所以判断多项式分层Polynomial Hierarchy是否有完全问题，就等于判断它是否塌缩，这是一个很大的问题。
■网友
看错题了，重新回答。没有，如果有的话，最明显的结论就是NP=P，因为对于一个属于P的问题，在得到一个可行解的情况下，通过PTIME可以reduce得到一个NP问题的解，那显然这个NP问题可以通过多项式时间解决，所以NP=P。
推荐阅读
- 傻子当国有银行行长都能赚钱这句话是否是对的
- 网通社|喜欢蔚来的越来越多了 连续四个月交付创新高 你是否愿意放弃特斯拉选择它？
- 豆瓣为啥受到同志社群的欢迎
- |PHEV车款没比较环保，新能源是否存在谎言呢？
- 运营商收取的流量费用价格是否合理
- 游戏公司一般咋识别游戏脚本
- 知乎上关于人生经验的介绍是否可能对青少年造成潜在危害
- 是否该停止密码掩饰了
- 织毛衣这种工艺是否会渐渐消失
- 给别人拉人头做项目，别人出事了，会连累到吗