Is Hamiltonian still NP?

  • #1
neurocomp2003
1,366
3
sup, just realized there is not graphtheory/combinatorial subforums.

is the hamiltonian cycle still considered and NP problem?
 

Answers and Replies

  • #2
master_coda
591
0
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).
 
  • #3
TenaliRaman
644
1
I wonder what thought could have raised this question :)

-- AI
 
  • #4
neurocomp2003
1,366
3
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 should have been my question but I just wanted to see if there was apaper out their that said H=P.
 
  • #5
TenaliRaman
644
1
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
 
  • #6
neurocomp2003
1,366
3
hahah i have an algorithm that I would like to try and see if it goes anywhere...not going to say it'll solve NP=P, but i want to see if it can go somewhere.
 

Suggested for: Is Hamiltonian still NP?

  • Last Post
Replies
8
Views
455
  • Last Post
Replies
4
Views
890
Replies
1
Views
2K
  • Last Post
Replies
33
Views
234
  • Last Post
Replies
16
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
337
Replies
38
Views
441
Replies
1
Views
130
  • Last Post
Replies
2
Views
680
Top