A Consult: NP=P and P (3-SAT) - Is It Well Known?

  • A
  • Thread starter Thread starter Rilegatore
  • Start date Start date
  • Tags Tags
    p vs np
AI Thread Summary
The discussion centers on the representation of 3-SAT formulas as a conjunction of two polynomial formulas, raising the question of whether this approach is well-known or novel. Participants clarify that while 3-SAT is NP-complete, the representation does not imply P=NP, as finding solutions for both formulas simultaneously remains complex. There is skepticism regarding the novelty of this representation, with some considering it trivial and lacking new insights into NP-class problems. The challenge lies in the interdependence of terms within the 3-SAT expression, which complicates finding a solution efficiently. The original poster seeks academic references or papers on this representation to further explore its validity.
Rilegatore
Messages
5
Reaction score
0
I need a consult.

There is representing of 3-SAT formula as a conjunction of pair logical formulas. Each of this formulas has polynomial algorithm for searching response about its satisfiability and (if the formula sat - we can find in polynomial time any decision of all possible). It is not means P=NP because the problem is to find the same decisions for both formulas. It means just we can represent 3-SAT formula as conjunction of pair formulas
and for this two formulas we can find decisions in polynomial time.

The question is the next: such representing is well known or it's something new?
 
Physics news on Phys.org
I'm not quite sure whether I understood you correctly.
The problem with NP=P and a 3-SAT formula is not, that it couldn't be verified in polynomial time or that some expressions are in P.
The crucial points are
a) that any Boolean expression could be solved and
b) to find a solution at all in polynomial time that could (of course easily) be verified in P.
 
Rilegatore said:
The question is the next: such representing is well known or it's something new?

3-SAT problem is about determining the satisfiability of a formula in conjunctive normal form, where each clause is limited to at most three literals. This is an NP complete problem. This is stated in Cook - Levin theorem.
 
Thanks for answers.

I don't talk about "3-SAT=P". But when I talk "3-SAT = P and P" I mean I can represent any general 3-SAT formula as conjunction (with "and" operation) of two (and only two) polynomial formulas. That means for each of this formulas I can find value of variables when the formula is sat or I can say about formula it's unsat.

Can you imagine - non determine polynomial (NP) is conjuction just two polynomial function (P and P)? It's very interesting property of the nature of NP-class.

I asked many professional maths - nobody can't tell me about such translation of the 3-SAT formula. That's why I asked about it here.
 
Last edited:
Rilegatore said:
I mean I can represent any general 3-SAT formula as conjunction (with "and" operation) of two (and only two) polynomial formulas.
This does not help. For a given term of a 3-SAT expression, it is easy to find a solution - you can even do so by trial and error. The problem is the dependence of the different terms - a solution to one term is in general not a solution to another term. And there the exponential factor comes in for all known algorithms to solve the problem.
 
  • Like
Likes QuantumQuest
mfb said:
This does not help. For a given term of a 3-SAT expression, it is easy to find a solution - you can even do so by trial and error. The problem is the dependence of the different terms - a solution to one term is in general not a solution to another term. And there the exponential factor comes in for all known algorithms to solve the problem.
This doesn't for what?
Such representation - it's new view on class NP. It doesn't means P=NP or something else great result.
 
I don't see a new view.
 
Do you mean paper? It exists just in Russian.
 
No, I don't see what is new about what you describe. It looks trivial.
 
  • #10
You want to say there is an algorithm of translation 3-SAT (CNF) to the conjuction of two logic formulas for which we can find values of variables when it's sat or to find it's unsat for any values of variables. And it's possible to make it for both formulas in polynomial time?

I'm trying to find a paper about it. I'll be glad if you can help me.
 
Back
Top