Is Hamiltonian still NP?

  • #1
1,356
2
sup, just realized there is not graphtheory/combinatorial subforums.

is the hamiltonian cycle still considered and NP problem?
 

Answers and Replies

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

-- AI
 
  • #4
1,356
2
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.
 
  • #5
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
1,356
2
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.
 

Related Threads on Is Hamiltonian still NP?

  • Last Post
Replies
3
Views
15K
  • Last Post
Replies
3
Views
2K
Replies
9
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
4
Views
622
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
16
Views
1K
  • Last Post
Replies
5
Views
1K
Top