关于在线性条件下NP≠P的证明

  • 打印
  • 收藏
收藏成功
微博 QQ空间 微信


打开文本图片集

摘要：本文证明了逻辑公式中所含有的辑门的总个数是否可转化为多项式的等价于逻辑公式中所含有的自由变元总次数是否可转化为多项式的。从而利用逻辑公式中所含有的自由变元总次数，来判断P类与NP类问题。针对NP中的类皇后问题Simqueen（n），证明了Simqueen（n）的在线性条件下非单调电路复杂度是不可能为多项式的，从而说明Simqueen（n）在线性条件下不是一个P类问题。（剩余1357字）

试读结束

目录
monitor