P vs NP and the analog machine

From: The Lord of Chaos \(Suresh Devanathan\) (surkum_removetheunderscore_here_dev_and_here_1_at_yahoo.com)
Date: 02/22/04 

Date: Sat, 21 Feb 2004 19:27:21 -0800

Hello, i have with me a very interesting MATLAB program. Basically, it's a
program that suboptimally "solves" TSP, in O(N^2) using the assumption that
addition of costs have a gaussian distribution. It's not that it actually
"solves" TSP, rather it dodges TSP in the following way.

The program is not able to search about sqrt(N!) paths out of N!. However
sqrt(N!)/N! -> 0, as N goes to infty. So, the probability that all paths,
are not compared goes to 0. On the other hand, for a finite but large N,
there are still sqrt(N!) paths that are missed by the algorithm. So, in a
way, the problem is still present.

------

clear;
% n is the number of cities
 n = 100;

% create a random matrix

 rr = rand(n,n) ;

% city is a symmetric matrix with a_ij = cost of going from city i to city
% j
 rr = (rr - min(min(rr)))/(max(max(rr)) - min(min(rr)) + 1) ;
 city = (rr + rr')/2;

% alias
il = 1:n;

% the max value of the city matrix is at 1. This is equivalent to
% normalizing the matrix

% Now, the diagonal elements are set to 1. This way they are avoided in
% comparisons
city( il + (il -1)*n) = 1;

% Use sampling to calculate mean and standard deviation
% Interestingly, the distribution of 'total costs', along path is
% gaussian.
% It follows from the fact that
% total cost = cost_( a to b) + cost_(b to c) + cost_(c to d) + ....

% L is the number of samples
 L = 1000;
 p = zeros(1,n);

for i = 1:L
 % the idea behind the following logic is that
 % randomly sort (1 to n)
 % after getting a random arragement, look up randrows_i , randrows_(i+1)
 % in the city matrix and sum up the costs
 randrows = sortrows([ rand(n,1) (1:n)']);
 p(i) = sum(city( n*(randrows(1:n-1,2)-1) + randrows( 2:n,2))) ...
                  + city(randrows(n,2), randrows(1,2)) ;
end;

% Our Traveling Sales Man problem solution starts here
% First, find the smallest matrix element

fmin = sortrows([city(:) (0:n*n-1)']);

e_solution_cost = [];
%for i = 1:n
% for j = 1:n
pa = [];
% pa(1) is the row of the smallest element
% pa(2) is the col of the smallest element

pa(2) = floor( fmin(1,2)/n) + 1;
pa(1) = mod(fmin(1,2),n) +1;

% this is the basic alogrithm
% after finding the starting point, now basically, what we do is that
% we go from link a_(kj) , where 'j' is all cities that the salesman never
visited
% we travel thru the city j, that yeilds min a_{kj}

for k = 2:n-1
indx = setdiff( 1:n, pa);
fmin= sortrows([ city(pa(k), indx)' indx']);
% and pa, stores the link
pa = [pa fmin(1,2)];
end;

% this is estimated cost from our suboptimal solution finder
e_solution_cost = [e_solution_cost ...
          (sum(city( n*(pa(1:n-1)-1) + pa( 2:n))) ...
                  + city( n*(pa(1)-1) + pa(n)) )];

% end;
%end;
solution_cost = min( e_solution_cost)

% the histogram
hist(p,50)

mean(p)
'std p'
std(p)

city( il + (il -1)*n ) = 0;
m_p = sum(sum(city))/n

% this step gives the estimated accuracy of the solution
% based on the gaussian distribution assumption
%factorial(n) *
( 0.5+ 0.5*erf((solution_cost - m_p)/ (sqrt(2)*std(p))))

 u = (solution_cost - m_p)/ (sqrt(2)*std(p));

 - exp(-u^2)/(sqrt(pi))*( 1/u - 1/(2*u^3))