Follow Slashdot stories on Twitter

 


Forgot your password?
Close
typodupeerror
×
Science

Let Nature Solves NP-Complete Problem 48

Posted by timothy from the unconventional-approaches dept.
An Anonymous Coward writes: "Why not? Here's a start: Tourist Map Illuminates shortest route Light up a gas-tube graph with electricity to find the shortest path between two points. Can they extend this to multiple vertices to instantly solve the NP-Complete traveling salesman problem?"
This discussion has been archived. No new comments can be posted.

Let Nature Solves NP-Complete Problem More

Let Nature Solves NP-Complete Problem

Comments Filter:
  • This just goes to show you that not ALL high-tech elegant solutions require digital circuitry.

  • This would be excellent news ... (Score:2, Insightful)

    by Anonymous Coward
    ... if finding the shortest route between 2 points on a network was actually an NP-Complete problem
    • The travelling salesman finds the shortest path through a graph visiting every point exactly once... computationally one must try every possibility of routes in order to find the path with the least cost... which increases polynomially with respect to the number of points on the graph ... classifying it as NP-Complete. What I don't understand is how this is actually a solution to this problem since wouldn't multiple electrodes trace a path to another electrode even if it was already connected? Therefore invalidating the solution by the definition (where the shortest path hits each point exactly ONCE)

      • Re:shortest path IS np-complete NOT (Score:5, Insightful)

        by gkatsi ( 39855 ) on Monday June 10, 2002 @06:34PM (#3676091)
        First, shortest path algorithms do NOT consider every possible route. Instead, they consider the best extention to an already known shortest path (starting with the shortest path to the beginning, which is obviously 0). [roughly -- Dijsktra's algorithm is slightly more complicated, but not much].

        Second, if the number of operations increases polynomially, how does the problem get classified as NP complete? Never mind the fact that a lower bound alone is not enough to put a problem in a specific class, if the complexity is actually O(n^2), then the problem is clearly in P, not NP.

        Other than a nice hack, this article does not describe any important breakthrough.
        • it's called leinthal's paradox -- the cost is NOT O(n^2) the cost is O((n-1)!) (http://konf2.ims.ac.jp/review/sec4.html [ims.ac.jp])
          Djikstr a's algorithm merely simplifies the correct procedural solution by limiting the sample space (which introduces a possibility of error) -- it APPROXIMATES the solution because the exact calculation is NP-Complete... another reference: here [warwick.ac.uk]
          • Electricity will only find the shortest path. This is an n^2 operation. Maybe it does it faster than that, but it is an n^2 operation with computers, which is pretty cheap.

            The travelling salesman problem on the other hand, which is not what the article talks about, imposes additional constraints: the path must visit all nodes and it must form a cycle (ie end where it began). These additional constraints are what make this an NP-complete problem. But unless the article is missing critical information, they have not found a way to impose those constraints.

            The links you mention are about the TSP, not the shortest path problem.
            • the 'additional' constraints are the elements that comprise the travelling salesman problem... n^2 is for the dijkstra algorithm, again, an approximation of the correct solution without checking the total problem space... you seem to be misinformed, have you ever taken a course in combinatorics?
            • I am being stupid and talking out of my ass, the original post was about the Travelling salesman problem, which is npc... and I misread your post as being about the main post being non-npc -- i.e. this whole conversation was line noise. my bad.

              let's reiterate - traveling salesman: np-complete

              shortest path between two arbitrary points in a graph of n points - O(n^2)

              /me should go get some more caffeine
        • Theres many algorithms for finding shortest path, fromsimple bradth first/depth first through steepest ascent hill climbing, to ones that estimate remaining distance, to routing tables, and of course dijiska
      • which increases polynomially with respect to the number of points on the graph ... classifying it as NP-Complete.

        WHAT? This has nothing to do with NP-Completeness. A problem A is NP complete iff it is NP and for all problems B in NP, B can be reduced to to A in polynomial time. (this means you can convert any problem in NP to an NP-Complete problem in polynomial time and the solution to B can be determined by running an input on A)
        So unless you can show this your claim about np completeness is complete bull.
        • actually, a decision problem A is NP-Complete if every other problem in NP space is reducable to A. meaning that for any problem in NP space, there is a polynomial time algorithm which changes it into A... which is test by comparing the SAME input to A and the function modified by the polynomial time algorithm and showing them to result in the same truth table. (Cook, 1971). The TSP problem, a subset of the problems encompassed by computational complexity theory... In trying all possible routes, the number of given combinations is N! which is itself NP-Hard, but the decision aspect... given a the costs and the number of points is there a route cheaper than x? is NP Complete. For this and other TSP information, here's a good link [princeton.edu] you should review before accusing people of spouting 'complete bull'.
          • From http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/a nnotated_np.html [liv.ac.uk] -- a list of selected np-complete problems

            Number: 27

            Name: Travelling Salesman [ND22] 3-4

            Input: A set C of n cities {c1,...,cn}; for each pair of cities (ci,cj) (1
            Question: Is there an ordering of the n cities such that the value sum from i=1 to n-1 dpi(i),pi(i+1)+dpi(n),pi(1) is no more than B?

            Comments: In effect what this problem is asking is whether there is a tour of the given collection of cities that visits each city exactly once and takes up total distance no more than B. There is a huge volume of literature concerning approximation methods, search heuristics, special case methods, etc for this very well studied problem. A bibliography has been compiled.
      • I'd just like to point out that this is not the traveling salesman problem. This is the shortest point between any two points, not all points on the map. Read the article.
  • that 5 sentence blurb was the whole article? Seems like a fascinating solution to a problem, surely someone could have written another 3 or 4 sentences.

    no mention of how this could apply to programmable MEMS or anything, and this is EE Times, odd.

  • I prefer the slime mould version... (Score:4, Informative)

    by SIGFPE ( 97527 ) on Monday June 10, 2002 @05:56PM (#3675805) Homepage
    ...here [cosmiverse.com]
  • This doesn't strike me as all that impressive. They need to customize hardware for any city they wish to model. One can consider this to be a form of preprocessing, and for a fair comparison to be made, one must also allow preprocessing to be done using the computational method. After preprocessing, results can be obtained using an array lookup.

    This may be interesting, but I doubt it's all that revolutionary.

  • Shortest-path problems are easy ... (Score:4, Informative)

    by Daniel Dvorkin ( 106857 ) on Monday June 10, 2002 @05:57PM (#3675816) Homepage Journal
    ... for computers too. Any decent book on algorithms will give you several elegant, easy-to-implement, blazingly fast methods. The TSP, like all NP problems, is much different. Thinking about the gas-tube device (which is a really cool idea, I must say) there's no way to apply it to the TSP. Electricity just doesn't work that way.
  • It is kindof neat that someone had this idea and produced a working model (pictures, anyone?) But by the time a skilled laborer builds a piece of equipment which solves the problem, a computer will have computed the solution a few billion times over, including the time it took to program and input the problem.

    Furthermore it doesn't solve the problem satisfactorily, for instance how do you make a one way street in a neon tube? How do you post speed limits for electrons?

    There may be solutions to these questions, and more, but the computer will still solve all these problems more quickly than any person or group of people can build a device which can do so.

    The larger question of whether nature can provide solutions to unsolved problems is, of course, a resounding yes. But we've known that for awhile, what's new? The problem is translating the question into a form nature can handle, then interpretig the results. As we come ever closer to biological computers we will have a better grasp of performing such experiments - the question is whether quantum computers will come first (which apparently solve every NP problem - according to the optomistic physicists, anyway ;-)

    -Adam

    • Re:Neat, but not quite as useful as one might thin (Score:1, Insightful)

      by Anonymous Coward
      Furthermore it doesn't solve the problem satisfactorily, for instance how do you make a one way street in a neon tube?

      Diodes (allows current to flow only one way)

      How do you post speed limits for electrons?

      Resistors (regulates the flow of current more than the speed -- but you get the idea)
      • These devices wouldn't apply to a neon tube in nearly the same way.

        You couldn't model the map as a circuit since current would flow through as all of the circuit - you might be able to glean some information from the current in each road, but then you're still executing a search.

        The helium tube is an instantaneous solution, but putting resistors and diodes in the tube wouldn't work since you're dealing with much higher voltages and lower currents.

        -Adam

  • Question (Score:2, Interesting)

    by Lomby ( 147071 )
    From my physics classes, I recall that electricity follows the line of least resistance.

    Now, this means at every crossroad, the electron flow will select the road with the least electric resistance.

    This leads to a kind of greedy algorithm, that possibly leads to a good approximation of the shortest path, but still an approximation.

    Or does the current flow path oscillate to find the absolute resistance minimum, so it does not get stuck in a relative minimum?

    Or do I miss something?

    • Re:Question (Score:3, Informative)

      by Fantanicity ( 583135 )
      The current doesn't oscillate or travel solely along the path of least resistance.
      Electrons do not select anything. The current flows from start to finish along all possible paths; but because the shortest path has the least resistance (there is less material to flow through) more electrons get through that path per unit time than other paths - hence the current is higher.
      In this case, all paths will glow, the shortest path will glow the most. With the right balance of voltage and material, the shortest path can glow significantly more than other paths.
  • There was a paper in Science [scienceonline.org] a few years back that took a similar approach.

    I don't have the references any more (but here [cornell.edu] is a similar source), but here's the gist: They built strands of RNA with specific sites being mapped to parts of the travelling salesman solution, replicated those strands billions of times with PCR. and mixed well. The reactions that prevaled were logically the "shortest" path.

    Nature abounds with massively parallel computing engines.
  • There was a neat Scientific American article about twenty years ago about fast analog solutions to hard problems.

    The example that sticks in my mind was sorting numbers with dry spaghetti, where the spaghetti was broken at a lenght that represented the size of the number. If you hold the spaghetti vertically in a column and touch the top you will have selected the largest number. Iterate until numbers are sorted from greatest to least. You have a linear time sorting algorithm.

    They also had a factoring machine.

    Unfortunately, all of these solutions lose big on setup time. Building the analog solving tools is generally difficult, and becomes difficult faster than standard mathematical methods. I suspect this may be universal.

  • Answering the question (Score:2, Informative)

    by andfarm ( 534655 )
    No.

    This resistance-path method will only find the shortest path from one point to another -- a task for which there already exist solutions which can complete in polynomial time. A *full* path (which is required as a solution to the Travelling Salesman problem) is not directly solved by this method.

  • Knotted String and Dijkstra (Score:4, Interesting)

    by alacqua ( 535697 ) on Monday June 10, 2002 @11:13PM (#3677405) Homepage
    Here's two other amazing solutions. Knotted string and Dijkstra's algorithm.

    There are several methods that can be used to solve this problem. One way is to make a model of the map by knotting together pieces of string whose lengths are proportional to the lengths of the roads. To find the shortest path, take hold of the knots corresponding to A and L - and pull tight!
    -Introduction to Graph Theory, Robin J. Wilson

    How can we find the shortest route from one location to another?... Dijkstra's Algorithm (Dijkstra [1959] and Whiting-Hillier [1960]) solves this problem quickly,...
    -Introduction to Graph Theory, Douglas B. West

    Check any book on graph theory or on algorithms for the details of Dijkstra's algorithm.

    The setup with the tourist map is kind of cool but hardly a breakthrough for math or computer science.

Slashdot Top Deals

In the future, you're going to get computers as prizes in breakfast cereals. You'll throw them out because your house will be littered with them.

Close