%pnp.tex:
%%a Plain TeX file by Doron Zeilberger (x pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
Research Announcement: A  Computer-Generated Proof that P=NP
}
\rm
\bigskip
\centerline{ {\it
Doron 
ZEILBERGER}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg  at math dot rutgers dot edu} ,
\hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg} .
Written: April 1(!), 2009.
}
}


{\bf Abstract:} Using 3000 hours of CPU time on a CRAY machine,
we settle the notorious P vs. NP problem in the affirmative, by presenting
a ``polynomial'' time 
algorithm for the NP-complete {\bf subset sum} problem. Alas the complexity of our algorithm 
is $O(n^{10^{10000}})$ (with the implied constant being larger than the Skewes number).
This anticlimatic resolution 
of the ``central'' problem in theoretical computer science indicates
the fatal flaw of the ruling paradigm in computational complexity theory that equates ``polynomial time''
with ``fast'', and presents yet another cautionary tale about the human propensity to trust artificial
and crude {\it models} blindly, as witnessed in the recent collapse of Wall Street.


{\bf P=NP}

Like many solutions of long-standing open problems, the {\it main idea} of our solution is tantalizingly simple (by hindsight!).
Recall  the following NP-complete problem

{\bf The Subset Sum problem}: Given a set $T$ of integers, and an integer $b$, decide whether or not
there exists a {\it subset} $S \subset T$ such that
$$
b=\sum_{s \in S} s \quad .
$$

Consider the Laurent polynomial
$$
P(z)=z^{-b} \prod_{t \in T} (1+z^t) \quad .
$$
Obviously the subset problem is affirmative if and only if  the {\it constant term} of $P(z)$ is $> 0$.
Using Cauchy's integral formula, this boils down to computing
$$
A(T,b):={{1} \over {2 \pi i} } \int_{|z|=1} {{P(z)} \over {z}} \, dz .
$$
Making the substitution $z=exp(ix)$, $dz=i exp(ix) dx$, we can transform this into an integral on $[-\pi,\pi]$
$$
A(T,b):={{1} \over {2 \pi} } \int_{-\pi}^{\pi} P(e^{ix}) \, dx .
$$
We now use {\it Gaussian quadrature} to {\it approximate} this integral with an error
of $< 1$. By using a delicate analysis of the {\it error formula}, we can find in 
the ``polynomial'' time mentioned in the abstract, a number of points $N$, such that
the Gaussian Quadrature with that number of points does indeed have the required error bound.
Alas the $N$ (number of points), is huge (but still ``polynomial'' in the size of the inputs), and using {\it rigorous}
{\bf interval analysis}, rather than non-rigorous floating-point computations, we can estimate
the integral, as well as bound the error, thereby solving the problem in ``polynomial'' time.
The {\it rigorous} estimate of the error (crucial to the success of the decision algorithm), involves
solving more than ten thousand Linear Programming problems, each with more than one hundred thousand variables.
This system was generated automatically and dynamically, using a {\it genetic algorithm} and
{\it simulated annealing}, as well as sophisticated Markov Chains and Bayesian analysis.
Of course, we do not guarantee that this is the shortest possible proof, since it was generated
by a non-determinstic Turing machine,
but it is indeed a {\bf fully rigorous} proof. The validity of the proof was independently checked
by four other computers, running on different platforms and different programming languages.


{\bf Remark}: A considerable speed-up can be achieved if one uses ``analog'' computations, namely
an analytical balance easily obtained in any chemistry laboratory. First have the
computer plot the real and imaginary parts of $P(e^{ix})$, above $-\pi<x < \pi$, on high-quality paper. Second, print-out
these two plots. Third, using scissors, for each of these plots,
carefully cut the parts above and below the $x$-axis. Third, find the difference in weight between the
positive and negative parts, and divide by the weight of a unit square. If the sum of the absolute values
of the two differences is less than $\sqrt{2}/2$, then output {\it no}, otherwise {\it yes}.


Full details will apear elsewhere.

\end



