查看我的证明CO-NP！= P.

Question

这是业余爱好级别的工作，而不是我的工作。 我写了这个摘录，分享一些关于CO-NP的想法。

这个想法是在CO-NP中选择一个问题类别，如果电路复杂性，正确的答案是难以验证的，将其表达为单位的SAT公式，并显示也存在一个简短的证书，其位的长度恰好是条款数量的两倍。这可能是真是假的，即所有CO-NP问题都有这种形式的短证书（CO-NP？= NP），但我表明，无论那个如何，这个问题的简短证书都可以任意难以努力找到，因为与NP的交错关系。基本上，我希望突出NP和CO-NP的伪装之间的特定循环依赖性。踩踏CO-NP= P的论点是NO TM可以希望攻击搜索子凸起时间中的短证书的问题，因为我定义问题的方式使其包含任意数量的“实际随机”。基本上，它是一个特定的配方，用于从简单的证书构建“怪物”CO-NP问题。

现在我对任何正式训练的人都有很多问题：

• 具有此类别的问题，以不同的名称表示？
• 这是一个明显的死胡同还是未开发的？
• 如何表达相同的想法，但更正式地反对TM功能？

Answer 1

wtlu处于p.

算法：

• 通过添加每个对文字（x +〜x）= 1并用新变量替换〜x来制作单个子句。
• 挑选一个大的Prime P，至少大于子数的数量。
• 将1 in-k SAT配方变为线性方程式模数P.表单（x，y，z ...）= 1中的每个原始子句变为等式（x，y，z ...）= 1 mod p。
• 执行高斯消除。
• 如果公式是WTLU实例，则在达到行梯形形式之前发现矛盾，以矛盾的等式0= k mod p（用k！= 0）。

为什么它有效：

如果有两组子句覆盖相同的文字集，例如（C1 + C2 + C3 ...）= X和（C1'+ C2'+ C3'）= Y和x！= y，那么它也是模拟模数p。因此，方程式Modulo P的系统也不满足。

Answer 2

这是一个反驳。一种类似的证明结构，可以很容易地证明XOR-SAT很难。

1. 带有一个巨大的空间的XOR-SAT配方。您无法使用类似分辨率的算法解决。

2. 现在存在短暂的不可起点证书，因为XOR-SAT处于P.

中

3. 如果您不知道消除，则将随机子句组合在一起，直到两个子句具有相同的变量，一行等于零，另一个行等于一个。排队是一个特殊情况，而条款没有共同的文字。

4. 将随机子句和变量添加到XOR-SAT公式中，以使其更加困难到随机做事。

但实际上，您可以在多项式的时间和空间中进行高斯消除，直到两行互相抵消以产生0= 1。

要扩展您的论点并使它有趣您需要至少表明与XOR-SAT存在根本区别，因为开始，没有类似于消除的过程，您可以在其中一个接一个地取出变量在忽略额外信息的同时隔离2个冲突条款的过程中。