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

P≠NP that simple?

  1. Jun 28, 2015 #1
    If exponential functions are transcendental functions, then they can not be expressed in a polynomial algebraic form. If so, then P≠NP. Is that so simple?
     
  2. jcsd
  3. Jun 28, 2015 #2

    jbriggs444

    User Avatar
    Science Advisor

    No. It is not that simple. Can you please elaborate for us in your words what the question P=NP means?
     
  4. Jun 28, 2015 #3
    P means means the processing time of a computer algorithm is represented by a polynomial function of time.
    NP means processing time of a computer algorithm is represented by an exponential function of time.
     
  5. Jun 28, 2015 #4

    pwsnafu

    User Avatar
    Science Advisor

    No, P is the class of all mathematical problems which can be solved by an algorithm which runs in polynomial time.
    NP is the class of all mathematical problems whose solution can be verified by an algorithm which runs in polynomial time.
     
  6. Jun 28, 2015 #5
    However, the solution of all mathematical problems in NP class are solved by an algorithm which runs in exponential time, isn't it?
     
  7. Jun 28, 2015 #6

    pwsnafu

    User Avatar
    Science Advisor

    Yes, but we don't know if the converse is true. There may be problems which can be solved in exponential time whose solution verification also require exponential time.
     
  8. Jun 29, 2015 #7
    But I guess this contradicts your definition of NP:
    .
    So how NP which is supposed by definition to be verified in polynomial time, now require exponential time?
     
  9. Jun 29, 2015 #8

    pwsnafu

    User Avatar
    Science Advisor

    No it doesn't. There's the class P (solvable in polynomial time). There is NP (verifiable in polynomial time). There is EXPTIME (solvable in exponential time). And lastly NEXPTIME (verifiable in exponential time). We know that
    ##P \subset NP \subset EXPTIME \subset NEXPTIME##
    and also that ##P \neq EXTIME ##and ##NP \neq NEXTIME##. At least one of the inclusions is strict, we don't know which one.

    If I pick a problem from EXPTIME the solution might be verifiable in polynomial time, or maybe not. It could be true that ##NP = EXPTIME##, in which case your definition is fine. But we don't know that.
     
    Last edited: Jun 29, 2015
  10. Jun 29, 2015 #9
    For me it is all about mutual exclusion. Please look at the attached 2x2 table which I just made.
    If you do so, the verification of the solution in polynomial time will not invalidate that P is mutually exclusive with EXPTIME.
     

    Attached Files:

  11. Jun 29, 2015 #10
    Please look at the attached 2x2 table which I just made now.
    If you do so, it won`t invalidate that both P and EXPTIME are mutually exclusive. So if the problem is solvable in exponential time (EXPTIME) but verified in polynomial (NP), it won`t be transformed one day to be solvable in polynomial (P) because it can`t be solvable in polynomial and exponential time at the same time.
     

    Attached Files:

  12. Jun 29, 2015 #11

    pwsnafu

    User Avatar
    Science Advisor

    I have no idea what you are arguing now. "Mutually exclusive" means both cannot be true at the same time, i.e. there does not exist a problem which is both in P and in EXPTIME. That's nonsense, every problem in P is also in EXPTIME.
     
  13. Jun 29, 2015 #12
    Good starting point now, so how come that every problem in P is a problem in EXPTIME? This again bring us back to the first post, that exponential function is transcendental ones!
     
  14. Jun 29, 2015 #13

    jbriggs444

    User Avatar
    Science Advisor

    A problem class is solvable in "exponential time" if the solution to every problem in that class whose size is n takes no more than ken steps for some constant k.

    A problem class is solvable in "polynomial time" if the solution to every problem in that class whose size is n takes no more than knj for some constants k and j.

    Note that the number of steps required to solve a particular problem in a particular class is always an integer. It is never transcendental.
     
  15. Jun 29, 2015 #14
    But ken can not be expressed in a finite terms of knj. Also, if you put "verified" instead of "solvable" in the your statement, then quotes from pwsnafu becomes true. namely, the solution of a problem which can be verified in a polynomial time can not be verified in exponential time, if i understood i correctly.
     
    Last edited: Jun 29, 2015
  16. Jun 29, 2015 #15

    pwsnafu

    User Avatar
    Science Advisor

    So? Exponentials grow faster than any ##n^j## (provided j is fixed). That's all that matters.

    The statements you quoted are true. It's called the time heirachy theorem.
    We know that ##P \neq EXPTIME## and ##NP \neq NEXPTIME##.
    We don't known if ##P \neq NP## or if ##NP \neq EXPTIME##.

    You did not understand correctly. ##NP \neq NEXPTIME## means that there exists at least one problem which can be verified in exponential time but not in polynomial time. Remember, ##NP \subset NEXPTIME##.
     
    Last edited: Jun 29, 2015
  17. Jun 29, 2015 #16
    OK that is more clear for me now. So if we can prove that there exists at least one problem which is solvable in exponential time but can not be verified in polynomial time, then we prove that NP≠EXPTIME.
     
  18. Jun 29, 2015 #17

    pwsnafu

    User Avatar
    Science Advisor

    Correct.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: P≠NP that simple?
  1. P vs NP (Replies: 15)

  2. P=np refuted (Replies: 3)

  3. P = np formula (Replies: 7)

  4. A proof for P vs NP (Replies: 8)

  5. P Versus NP Problem (Replies: 5)

Loading...