Reply to thread

Message

[QUOTE="Joshua Cranmer, post: 3597577"]
I wish to expound on this idea:

NP-hard problems are such because of the fact that one needs to look at 
the entire problem to be able to infer which next step is best. To date, 
the best correct algorithms more or less rely on "try all, but we know 
these paths won't work."

To find a P algorithm, one would have to condense the entire global 
solution space--in polynomial time--into some higher-order information 
that one can then use to pick the next node in Î©(N) of time (I'm tempted 
to say Î¸(N), but it could very well be true that the act of generating 
the information produces output in such a way that the next step is Î¸(1)).

If you want my opinion, I think a very good line of thought would focus 
on cataloging what one gives up by NOT choosing to visit a particular 
node next.

In any case, I'm beginning to also get the suspicion that I've been 
killfiled by JSH... Oh well, Patricia is probably more experienced than 
I in this area anyways.
[/QUOTE]

Verification