Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A NP = P and P (3-SAT)

Tags:
  1. Sep 15, 2016 #1
    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?
     
  2. jcsd
  3. Sep 15, 2016 #2

    fresh_42

    Staff: Mentor

    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.
     
  4. Sep 15, 2016 #3

    QuantumQuest

    User Avatar
    Gold Member

    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.
     
  5. Sep 16, 2016 #4
    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: Sep 16, 2016
  6. Sep 30, 2016 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  7. Oct 2, 2016 #6
    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.
     
  8. Oct 2, 2016 #7

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I don't see a new view.
     
  9. Oct 4, 2016 #8
    Do you mean paper? It exists just in Russian.
     
  10. Oct 4, 2016 #9

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    No, I don't see what is new about what you describe. It looks trivial.
     
  11. Oct 5, 2016 #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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: NP = P and P (3-SAT)
  1. SAT is NP-complete (?) (Replies: 10)

  2. P vs NP and factoring (Replies: 3)

Loading...