Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Posts:
822
Registered:
9/1/10


NP Problem(s)olution(s0)
Posted:
Nov 11, 2012 10:23 AM


Consider the entire list of incompatible students on the list from the Dean to be a single "incompatible student" called (s)
Now so long as the "incompatible student" called (s) never appears on the 100 generated list the list is satisfactory.
Begin to generate a list. Does the list contain any portion of "incompatible student" called (s)? If yes, remove any portion of "incompatible student" (s), but retain the interior set of compatible students.
As with any NPComplete problem we only need to eliminate the undesirable portion of the singular trait we seek. For instance if I choose the shortest path, any path after the first path chosen, found to be longer is immediately outside the realm of shortest path. Any path found to be shorter than the first chosen path, is said to be within the realm of shortest paths. Immediately, if any pair contains a path inside the realm of shortest paths, check it against the other pairs of shortest paths. Any path found to be greater than any other pair of shortest paths is immediately rejected, and any pair of shortest paths to be found less than any other pair of shortest paths is accepted and tested against other pairs continually. Until by exponential reduction, the ideal pair is sought and found and tested.



