Hi all,
I'm tring to solve 103 Box Stacking problem. I have a graph representation of the boxes in adjacency list.
Is there is any good algorithm to find the longest path ? (any reference)
Thanks,
Reemus Kumar
longest path
Moderator: Board moderators
Cosmin.ro: NP-what? 
The correct phrase here would be "is known to be NP-hard", meaning:
- if we were able to solve this problem in polynomial time, we would be able to solve any problem from NP in polynomial time
- it is not even known whether there is a non-deterministic polynomial algorithm for this problem
[No offense intended, of course... It's just that I've been TAing a formal languages course for several years, so one can imagine I get a bit upset when people misuse the notation
]
The correct phrase here would be "is known to be NP-hard", meaning:
- if we were able to solve this problem in polynomial time, we would be able to solve any problem from NP in polynomial time
- it is not even known whether there is a non-deterministic polynomial algorithm for this problem
[No offense intended, of course... It's just that I've been TAing a formal languages course for several years, so one can imagine I get a bit upset when people misuse the notation
]Wouldn't the correct phrase actually be, "is known to be FNP-hard", since it's a function problem? And the second point is not implied by the NP/FNP-hardness, as you seem to indicate.misof wrote:Cosmin.ro: NP-what?
The correct phrase here would be "is known to be NP-hard", meaning:
- if we were able to solve this problem in polynomial time, we would be able to solve any problem from NP in polynomial time
- it is not even known whether there is a non-deterministic polynomial algorithm for this problem
I agree with you here an all points.misof wrote:[No offense intended, of course... It's just that I've been TAing a formal languages course for several years, so one can imagine I get a bit upset when people misuse the notation ]
Hehe, I got what I asked for 
The clarifications are in place, of course. The intended formulation was "the problem is NP-hard and we don't know whether it is NP-complete". My second point is just the translation of "we don't know whether it is NP-complete" into words.
As of the other point, even the decision problem (given a graph G and an integer K, is K the length of the longest path in G?) is NP-hard.
The clarifications are in place, of course. The intended formulation was "the problem is NP-hard and we don't know whether it is NP-complete". My second point is just the translation of "we don't know whether it is NP-complete" into words.
As of the other point, even the decision problem (given a graph G and an integer K, is K the length of the longest path in G?) is NP-hard.
Nothing brightens the day up like a little nitpicking.
The IMO more standard choice of decision problem for longest path would be "Given G and K, does G have a path of length at least K", which is NP-complete. That is why I dragged in FNP, so that the "not known to be NP-complete" part would stay true.
The IMO more standard choice of decision problem for longest path would be "Given G and K, does G have a path of length at least K", which is NP-complete. That is why I dragged in FNP, so that the "not known to be NP-complete" part would stay true.
Misof wrote:
he intended formulation was "the problem is NP-hard and we don't know whether it is NP-complete".
Sir , i am very poor in English . i don't understand what r u saying ? All
NP-complete problems r NP-hard ,but some NP-hard problems r not
known to be NP-complete .
A problem L is NP-hard if and only if Satisfiability reduces to L.
A problem L is NP-complete if and only if L is NP-hard and L belongs to NP.
Misof wrote:
he intended formulation was "the problem is NP-hard and we don't know whether it is NP-complete".
Sir , i am very poor in English . i don't understand what r u saying ? All
NP-complete problems r NP-hard ,but some NP-hard problems r not
known to be NP-complete .
A problem L is NP-hard if and only if Satisfiability reduces to L.
A problem L is NP-complete if and only if L is NP-hard and L belongs to NP.
he intended formulation was "the problem is NP-hard and we don't know whether it is NP-complete".
Sir , i am very poor in English . i don't understand what r u saying ? All
NP-complete problems r NP-hard ,but some NP-hard problems r not
known to be NP-complete .
A problem L is NP-hard if and only if Satisfiability reduces to L.
A problem L is NP-complete if and only if L is NP-hard and L belongs to NP.