Is Hamiltonian still NP?

1,349
2
sup, just realized there is not graphtheory/combinatorial subforums.

is the hamiltonian cycle still considered and NP problem?
 
590
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).
 
644
1
I wonder what thought could have raised this question :)

-- AI
 
1,349
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.
 
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
 
1,349
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 for: Is Hamiltonian still NP?

  • Posted
Replies
3
Views
15K
  • Posted
Replies
3
Views
1K
Replies
9
Views
2K
  • Posted
Replies
7
Views
3K
  • Posted
Replies
1
Views
3K
  • Posted
Replies
10
Views
2K
  • Posted
Replies
7
Views
2K
  • Posted
Replies
4
Views
548

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top