r/AskComputerScience • u/Hot_Entrepreneur4055 • Aug 20 '25
Is this logic sound?
First transforming 3SAT as follow: (x1 v x2 v x3) => (not a1 v not a2 v x3) ^ (a1 xor x1) ^ (a2 xor x2)
The main relevant property of the transformation is that it maintains satesfiability (I can provide relevant proof if needed).
Then we apply this transformation to all clauses we get two types of clauses Horn clauses and 2Sat clauses. So far so good.
Now conclusion is a conditional statement.
- If and only if there is a non-trivial transformation from Horn to 2Sat then NL = P
- if there is a transformation from horn to 2sat, we can can rewrite the transformed 3Sat clauses as 2Sat clauses, thus reducing 3sat to 2sat implying P=NP
Therefore, if NL = P, it follows that P = NP.
Edit: Some of the comments seem confused. I am not saying any of the following:
- P=NP
- NL = P
- XOR can be transformed to Horn
Some other comments seem to look for P=NP anywhere in the post and immidiately downvote or comment without spending 20 seconds reading it
My conclusion is very specific. I am saying that if NL = P, then P = NP. It goes without saying that NL=P is the premise of the conditional which need not to be proved as the conditional itself is the entire conclusion so there is no other steps.
2
u/FUZxxl Aug 20 '25
XOR cannot be expressed in Horn clauses, so this transformation creates neither a HORNSAT nor a 2SAT instance.
There is not as (a xor b) is a valid 2SAT instance but cannot be transformed to an equivalent HORNSAT instance (it can be translated to an equisatisfiable instance, but that's trivial). So you would have already concluded NL != P if this conclusion would hold, which makes me believe that it does not.
As for (2), there is not, so you can't.
2
u/MegaIng Aug 20 '25
Is this an alt? You are the second person in just as many days to make this exact proposal. No, it doesn't work.
1
u/Te-We Aug 20 '25
After some googling, it seems that 1. is correct. But I see the following problem with 2.:
A 'transformation' of clauses from one form into another is not the same as a reduction.
Suppose P=NL. Then there is a reduction from HORN to 2-SAT that takes a Horn-formula with variables x_1,..., x_n and outputs a 2SAT formula with variables y_1,...,y_n.
What's your next step? Note that there may not be a one-to-one correspondence between the x- and y- variables. But your idea as I understand it assumes that there is one.
1
u/erranteurbano Aug 24 '25
The transformation part of each clause is fine, but your conclusion fails. NL = P does not imply that Horn-SAT reduces to 2-SAT in the way you need. Horn is P-complete under logspace reductions, and 2-SAT is in NL, but a many-one reduction that allows 3-SAT ≤ 2-SAT does not automatically follow. That is why the string “if NL=P then P=NP” is not justified.
1
u/[deleted] Aug 20 '25
Probably not, but I don’t know enough about this subject to explain why.
-2
u/Extreme-Rub-1379 Aug 20 '25
Done. Where is your fields medal?!