本文证明了逻辑公式中所含有的辑门的总个数是否可转化为多项式的等价于逻辑公式中所含有的自由变元总次数是否可转化为多项式的。从而利用逻辑公式中所含有的自由变元总次数，来判断P类与NP类问题。针对NP中的类皇后问题Simqueen(n),证明了Simqueen(n)的在线性条件下非单调电路复杂度是不可能为多项式的，从而说明Simqueen(n)在线性条件下不是一个P类问题。最后得到了在线性条件下NP≠P。
科研之友
微信
新浪微博
Facebook
分享链接
