- #1
Rilegatore
- 5
- 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?
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?