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

[Rilegatore]

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?

 

[fresh_42]

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.

 

[QuantumQuest]

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.

 

[Rilegatore]

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.

 

[mfb]

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.

 

[Rilegatore]

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.

 

[mfb]

I don't see a new view.

 

[Rilegatore]

Do you mean paper? It exists just in Russian.

 

[mfb]

No, I don't see what is new about what you describe. It looks trivial.

 

[Rilegatore]

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.