Amoeba Solves Traveling Salesman (P=NP)

Seen something interesting in the news or on the intertubes? Discuss it here.

Moderators: Zamfir, Hawknc, Moderators General, Prelates

jewish_scientist
Posts: 1047
Joined: Fri Feb 07, 2014 3:15 pm UTC

Amoeba Solves Traveling Salesman (P=NP)

Postby jewish_scientist » Thu Jan 03, 2019 12:18 am UTC

Here is a news article about it. Basically, the amoeba they used moves toward food and away from light, so the researchers set the situation up so that food corresponds to cities and light corresponds to the distance between them. The whole set up is too complicated for me to really understand, let alone summarize. As the number of cities increased, the time taken to reach the food increased linearly. Therefor, P = NP.

I spotted what may be a problem with the experiment however. Although they got a lot of trials, they only tested the amoeba for up to 8 'cities'. Isn't it possible that the amoeba can only solve the problem in exponential time, but for small values it looks linear. My calculator represents y= 2x as an almost perfect line on the interval (0, 0.1). Why couldn't a similar thing happen here?
"You are not running off with Cow-Skull Man Dracula Skeletor!"
-Socrates

User avatar
CorruptUser
Posts: 10550
Joined: Fri Nov 06, 2009 10:12 pm UTC

Re: Amoeba Solves Traveling Salesman (P=NP)

Postby CorruptUser » Thu Jan 03, 2019 12:40 am UTC

P/NP rants

The P/NP problems always bugged me due to impossible combinations being checked. For instance, a common problem is "in this list of X numbers, do any sum to 0?". The brute force method is to check every combination, which if there are 100 numbers is 2^100 combinations to check, but the faster method is to split up the numbers into two sub-groups, create a list of all possible combinations of those sub-groups, and then check to see if any combination in the first subgroup matches in the second group. But why not first eliminate the impossible combinations first? An odd number, for instance, requires an even number of odd numbers to become an even number (zero), so it doesn't make sense to even bother with a combination of "odd-odd-even-odd" rather than just check stuff like "odd-even-odd". Surely you could group the odd numbers by themselves in the initial split, and as long as there are relatively similar amounts of even and odd numbers this would make the odd group much faster to compute? As for the even group, divide everything by two (at the end, multiply by two) and now you have even and odd numbers again, and surely you can skip the impossible combinations.

Of course, what makes two so special? Couldn't you check based on, say, three? A number that had a remainder of 1 needs to be added to another number or sum of numbers with a remainder of 2, so couldn't you simultaneously sort all the numbers into groups based on their remainders, and only check sequences that could possibly result in a remainder of 0? But then, couldn't you check based on every prime number, and only check numbers that when divided by 5, their remainders would also sum to 0? But wait, how much extra computing power is needed to simultaneously sort everything into to each group based on their remainders for each prime? And ugh, *brainsplat*

User avatar
MartianInvader
Posts: 809
Joined: Sat Oct 27, 2007 5:51 pm UTC

Re: Amoeba Solves Traveling Salesman (P=NP)

Postby MartianInvader » Thu Jan 03, 2019 1:26 am UTC

The problem you've spotted is indeed a problem. Humans and algorithms can already solve the traveling salesman problem in linear time up to n=8.
Let's have a fervent argument, mostly over semantics, where we all claim the burden of proof is on the other side!

User avatar
ConMan
Shepherd's Pie?
Posts: 1691
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Amoeba Solves Traveling Salesman (P=NP)

Postby ConMan » Thu Jan 03, 2019 1:50 am UTC

CorruptUser wrote:P/NP rants

The P/NP problems always bugged me due to impossible combinations being checked. For instance, a common problem is "in this list of X numbers, do any sum to 0?". The brute force method is to check every combination, which if there are 100 numbers is 2^100 combinations to check, but the faster method is to split up the numbers into two sub-groups, create a list of all possible combinations of those sub-groups, and then check to see if any combination in the first subgroup matches in the second group. But why not first eliminate the impossible combinations first? An odd number, for instance, requires an even number of odd numbers to become an even number (zero), so it doesn't make sense to even bother with a combination of "odd-odd-even-odd" rather than just check stuff like "odd-even-odd". Surely you could group the odd numbers by themselves in the initial split, and as long as there are relatively similar amounts of even and odd numbers this would make the odd group much faster to compute? As for the even group, divide everything by two (at the end, multiply by two) and now you have even and odd numbers again, and surely you can skip the impossible combinations.

If P != NP, then it means that the optimal algorithm for solving an arbitrary problem in NP \ P will always scale worse than polynomially. It means that regardless of the improvements you make to reducing the search space or speeding up the search algorithm or whatever will not get you below that limit, just reduce the base of the exponent or the constant in front of it. And you have to include all of the work done to remove the impossible combinations as part of your algorithm, too - if you're looking at various combinations of values modulo k, and you're doing that for every k within some range, and if that range scales based on the size of the list or the range of the numbers in it, then it's likely that checking all of those combinations will be a non-polynomial algorithm in itself (and if it isn't, then odds are that the final step of checking the lists will still be non-polynomial, even if it's faster than the brute force method).
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

idonno
Posts: 327
Joined: Fri Apr 03, 2015 3:34 am UTC

Re: Amoeba Solves Traveling Salesman (P=NP)

Postby idonno » Thu Jan 03, 2019 6:04 am UTC

I feel like I must be missing something because it looks to me like the entire experiment is cheating. My understanding is that they already solved the problem and as soon as the amoeba starts extending down one channel it starts getting probable cost feedback on every other channel without having to compute anything. Unless there is a P method to calculate that feedback on all of the paths simultaneously, aren't they just giving it the already computed answer in a linear fashion.

User avatar
Zamfir
I built a novelty castle, the irony was lost on some.
Posts: 7606
Joined: Wed Aug 27, 2008 2:43 pm UTC
Location: Nederland

Re: Amoeba Solves Traveling Salesman (P=NP)

Postby Zamfir » Thu Jan 03, 2019 7:54 am UTC

As the number of cities increased, the time taken to reach the food increased linearly. Therefor, P = NP.

The amoeba is not that smart, though. It only finds a feasible route in about 90% of the problems, and it doesn't find optimal routes at all. It just finds routes that are, on average, a tad shorter than the average of all feasible routes. So the amoeba does some form of optimizing. Which is perhaps interesting knowledge about this amoeba, or even in general about the problem-solving capabilities of 'simple' physical systems.

But this is not a linear-time algorithm for the TSP. That would require optimal solutions, for all problem instances. Presumably, the amoeba-algorithm fails mostly on the difficult (and interesting) instances.


feel like I must be missing something because it looks to me like the entire experiment is cheating.

I don't think so. The feedback signal only encourages shorter routes over longer routes, and punishes infeasibility. You don't need to solve the TSP to generate such a signal. It's more an encoding of the problem.

Also, I don't think that gradient descent on such a signal would give you feasible solutions ( like the amoeba does, mostly). You would presumably get stuck in a local minimum before you find a feasible solution, but I am not 100% on this. The authors write as if the amoeba does better than a trivial algorithm would, but I have only skimmed the text.

idonno
Posts: 327
Joined: Fri Apr 03, 2015 3:34 am UTC

Re: Amoeba Solves Traveling Salesman (P=NP)

Postby idonno » Thu Jan 03, 2019 2:28 pm UTC

I read the more detailed report and I still think this is cheating in some manner
To do this, the researchers use a neural network model in which every six seconds the system updates which channels are illuminated. The model incorporates information about the distance between each pair of cities, as well as feedback from the amoeba's current position in the channels.

Whatever the computation is here it is incorporating feedback from other current positions in channels which does not seem like a linear problem since the channel count is not linear and the process of calculating feedback is clearly extrinsic to the amoeba and must be taken into account. This is doing more than representing difficulty as they use it to completely cut off routes that seem non viable to prevent invalid selections.

"In our stellate chip for solving the n-city TSP, the total area of the body of the amoeba becomes n when the amoeba finally finds an approximate solution," Aono told Phys.org

Also, major points off to the reporter for over reporting the findings since the actual researches clearly said the solution is "approximate". Finding an approximate solution in linear time, even a really good one, is no where near as big a deal as actually finding an actual linear solution to the problem.

User avatar
Zamfir
I built a novelty castle, the irony was lost on some.
Posts: 7606
Joined: Wed Aug 27, 2008 2:43 pm UTC
Location: Nederland

Re: Amoeba Solves Traveling Salesman (P=NP)

Postby Zamfir » Thu Jan 03, 2019 3:00 pm UTC

yeah, i don't find it perfectly clear what they do. I based my impression on this:
All light stimuli LVk are updated synchronously on the basis of the following recurrent neural network dynamics [14,17,18], which was derived from the Hopfield–Tank–Amari model [21].

LVk(t+Δt)=1−σ1000,−0.5(∑ WVk,Ul⋅σ35,0.6(XUl(t))),

σγ,θ=1/(1+exp(−γ⋅(x−θ))),

WVk,Ul=
−λ(if V=U and k≠l)
−μ(if V≠U and k=l)
−ν⋅dist(V,U)(if V≠U and |k−l|=1),
0(otherwise).

The sigmoid function σ35,0.6 adjusts the sensitivity of the control, σ1000,−0.5 performs similar to the step function and the inhibitory coupling weight WVk,Ul (= WUl,Vk < 0) results in the decrease in XUl with the increase in XVk and vice versa. Parameters λ = 0.5, μ = 0.5 and ν impose the following constraints on TSP, respectively: (i) prohibition of revisiting a once-visited city, (ii) prohibition of simultaneous visits to multiple cities and (iii) minimization of the total distance, where dist(V, U) is the distance between cities V and U. To maximize the effect of (iii), it is necessary to set ν as large as possible so that differences in inter-city distances can be maximally amplified. However, ν must be below an upper limit ν⋆, otherwise some branches are illuminated even when they select some possible tours. The value of the limit ν⋆=−θ/(dist(V⋆,V′⋆)+dist(V′⋆,V′′⋆)) is obtained numerically, where θ = −0.5 and {V⋆,V′⋆,V′′⋆}=argmax{V,V′,V′′}(dist(V,V′)+dist(V′,V′′)). Thus, λ, μ and ν can be automatically determined for given a map. For the eight-city map, we set ν to be ν⋆≃0.008197>ν=0.0081. Similarly, for the four-, five-, six- and seven-city maps, we set ν = 0.00495, 0.00565, 0.0067 and 0.0076, respectively.

It reads to me as a function that encodes the problem.
W is matrix that represents the problem instance - which channels may be active at the same time, which channels are consecutive to each other and what is their distance. X is the current state vector.

The numbering is: Vk is a channel representing a visit to city V in the k-th slot of the trip. Same for Ul, mutatis mutandis.
XUl is the fraction of channel Ul filled by the amoeba.

idonno
Posts: 327
Joined: Fri Apr 03, 2015 3:34 am UTC

Re: Amoeba Solves Traveling Salesman (P=NP)

Postby idonno » Fri Jan 04, 2019 2:15 pm UTC

I'm not missing something? That is a non linear function right?
I don't entirely follow the function but I don't see any way you can assign 1 cost value to a channel and not be feeding more information than the initial problem. If you have a simple 3 city problem, channel C3 has 2 possible costs, Route AC and Route BC. No matter what single cost the formula puts on C3 or how it arrives at it, I don't see how that can possibly not be engaging in part of the decision making process. If the formula is making part of the decision and is non linear, this solution isn't linear.


Return to “News & Articles”

Who is online

Users browsing this forum: No registered users and 24 guests