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

Is Hamiltonian still NP?

  1. Jul 25, 2005 #1
    sup, just realized there is not graphtheory/combinatorial subforums.

    is the hamiltonian cycle still considered and NP problem?
  2. jcsd
  3. Jul 25, 2005 #2
    The problem of finding a Hamiltonian cycle in a graph is NP-complete (and therefore NP). This is a proven fact; it is not something that is under consideration (and so it will not change in the future).
  4. Jul 28, 2005 #3
    I wonder what thought could have raised this question :)

    -- AI
  5. Jul 28, 2005 #4
    having an algorithm that i want to code but i'm lazy. and if the question of NP=P was solved then there was no point =] guess that shoulda been my question but I just wanted to see if there was apaper out their that said H=P.
  6. Jul 30, 2005 #5
    As master_coda has stated, Hamiltonian is "proved" to be NP-complete.
    Now, if i understand your last post, then you seem to have an algorithm for Hamiltonian in which case you have solved the NP=P problem!! When are we going to see your paper coming out :D

    -- AI
  7. Jul 30, 2005 #6
    hahah i have an algorithm that I would like to try and see if it goes anywhere...not gonna say it'll solve NP=P, but i wanna see if it can go somewhere.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook