-1
$\begingroup$

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?
$\endgroup$
10
  • 3
    $\begingroup$ "where the correct answer is hard to verify because of circuit complexity" This is the problem. We don't know that anything in Co-NP is hard. Whenever attempting a proof like this, you have to answer some questions. For example, why are 2-SAT and 3-SAT different, according to your proof? Either way, realize that this problem has been attempted thousands of times, and has a million dollar price. if you're wondering if you're on the wrong track, then you probably are. $\endgroup$ – jmite Jun 10 '20 at 18:47
  • 3
    $\begingroup$ Oh, and saying "there's no chance to solve in subexponential time because..." is too vague of an explanation, and there just might be a TM doing some crazy weird calculation that can actually get behind this 'problem' $\endgroup$ – nir shahar Jun 10 '20 at 18:52
  • 4
    $\begingroup$ @d3m4nz3 Right, but I'm pointing out that, already in the second sentence of your description, you've assumed your conclusion. it seems a good indicator that you're probably on the wrong track. $\endgroup$ – jmite Jun 10 '20 at 18:59
  • 2
    $\begingroup$ If you could show us what really you have done (and not only the vague ideas) then maybe we will be able to help you. But as $P=NP$ is an open problem - you can safely assume anything vague is probably not solving that $\endgroup$ – nir shahar Jun 10 '20 at 19:06
  • 3
    $\begingroup$ @d3m4nz3 I will suggest you to try writing it in more formally and rigorously. Most probably you will find a flaw, but you will definitely learn a lot in the process. Also, don’t be disheartened! $\endgroup$ – prime_hit Jun 10 '20 at 21:40
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you sir! It's almost like everything in is P, one way or another. $\endgroup$ – d3m4nz3 Jun 14 '20 at 10:55
  • $\begingroup$ I don't understand what this answer has to do with the question. What is WTLU? How does adding that clause make the formula monotone? It still has negated variables, right? What are you claiming the results of the Gaussian elimination will tell you about the original formula? What does this have to do with what was asked? Can you edit your answer to elaborate? $\endgroup$ – D.W. Jun 14 '20 at 21:04
  • 1
    $\begingroup$ Weird Two Lines Unsat (WTLU), is the Co-NP subproblem described by OP. He intended to show that Co-NP is not equal to P by separating this subclass from P. However, I show that there is a very easy polynomial time algorithm to solve any problem in WTLU. Thus the argument falls apart. I will to try edit the answer to clarify. $\endgroup$ – j4cks0n Jun 14 '20 at 21:12
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you sir for your counterexample. How long before the humans start knowing the truth about computational complexity and mathematics? $\endgroup$ – d3m4nz3 Jun 11 '20 at 9:01
  • 2
    $\begingroup$ The size of the human brain is very small. So I would say about the same time than machines to get a sense of humour. $\endgroup$ – th0mps0n Jun 11 '20 at 9:07
  • 2
    $\begingroup$ Oh well, an exponential amount of time then. $\endgroup$ – d3m4nz3 Jun 11 '20 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.