Review my proof that Co-NP != P

Question

This is hobby level work, not my job. I wrote this excerpt to share some ideas about Co-NP.

The idea is to pick a problem category in Co-NP, where the correct answer is hard to verify because of circuit complexity, express it as 1-in-k SAT formula, and show there also exists a short certificate, whose length in bits is exactly twice the number of clauses. It might be true or false that all of Co-NP problems have such a short certificate in this form (Co-NP ?= NP), but I show that regardless of that, the short certificate for this problem can be made arbitrarily hard to find, because of the interleaved relationship with NP. Basically, I want to highlight a particular circular dependency between the oracles of NP and Co-NP. The argument to stomp against Co-NP = P is that no TM can hope to attack the problem of searching for the short certificate in subexponential time, because the way I define the problem makes it contain an arbitrary amount of "actual random". Basically, it is one specific recipe to build a "monster" Co-NP problem from a simple certificate.

Now I have many questions for anyone with more formal training than me:

• Has this category of problem been expressed with a different name?
• Is this an obvious dead end or unexplored?
• How can I express the same ideas but more formally against TM capabilities?

Answer 1

WTLU is in P.

Algorithm:

• Make the 1-in-k SAT formula monotone by adding one clause for each pair of literals (x + ~x) = 1 and replacing ~x with a new variable.
• Pick a large prime p, at least larger than the number of clauses.
• Turn the 1-in-k SAT formula into a system of linear equations modulo p. Each original clause in the form (x,y,z...)=1 becomes an equation (x,y,z...)=1 mod p.
• Perform Gaussian Elimination.
• If the formula was a WTLU instance, then a contradiction is found before row echelon form is reached, in the form of a contradictory equation 0 = k mod p (with k != 0).

Why it works:

If there are two sets of clauses that cover the same set of literals, such that (C1+C2+C3...) = X and (C1'+C2'+C3'...) = Y and X != Y, then it is also the case modulo p. Thus, the system of equations modulo p is not satisfiable either.

Answer 2

Here's a counterargument. A similar proof structure, could be easily used to prove that XOR-SAT is hard.

1. Take an unsatisfiable XOR-SAT formula with a large space. You can't solve it with a resolution-like algorithm.

2. Now there exists a short unsatisfiability certificate, because XOR-SAT is in P.

3. If you don't know about elimination then you combine random clauses together until two clauses have the same variables, one row equals zero and the other row equals one. Lining up is a special case of addition where the clauses have no literals in common.

4. Add random clauses and variables to the XOR-SAT formula to make it harder to randomly do things.

But in reality you can do Gaussian Elimination in a polynomial amount of time and space until two rows cancel each other to produce 0=1.

To expand your argument and make it interesting you would need to at least show that there is a fundamental difference with XOR-SAT, for a start that there is no process similar to elimination where you can take out the variables one by one during the process of isolating the 2 conflictual sets of clauses while ignoring the extra information.