Evidence that P $\neq$ NP
Craig Alan Feinstein
cs0310060.tex
\documentclass [12pt]{amsart}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {hyperref}

\begin{document}
\title{Evidence that P $\neq$ NP}
\author{Craig Alan Feinstein}
\date{March 16, 2004}
\maketitle
\begin{scriptsize}
\begin{center} \bigskip \noindent \textbf{Baltimore, Maryland
U.S.A. email: cafeinst@msn.com, BS"D}
\end{center}

\bigskip \noindent \textbf{Abstract:} The question of whether
the class of decision problems that can be solved by deterministic
polynomial-time algorithms, $P$, is equal to the class of decision
problems that can be solved by nondeterministic polynomial-time
algorithms, $NP$, has been open since it was first
formulated by Cook, Karp, and Levin in 1971. In this paper, we
give evidence that they are not equal by examining the SUBSET-SUM
problem.

\bigskip \noindent \textbf{Disclaimer:} This article was authored
by Craig Alan Feinstein in his private capacity. No official
support or endorsement by the U.S. Government is intended or
should be inferred.

\end{scriptsize}
\clearpage

Let $P$ be the class of decision problems that can be solved by
deterministic polynomial-time algorithms and $NP$ be the class of
decision problems that can be solved by nondeterministic
polynomial-time algorithms. It has been an open question since the
early 1970's whether or not $P = NP$. In this note, we give
evidence that they are not equal. The argument in this note is put
forward in a purely intuitive spirit and should not be interpreted
as a rigorous proof; however, the author is by no means claiming
that a rigorous version of the argument presented here is
impossible. And the author welcomes and challenges anyone to produce a
rigorous version. Let us start out by
considering the following commonly known $NP$ problem:

\bigskip\noindent \textbf{SUBSET-SUM}: \textit{Given $n \in \mathbb N$,
vector ${\rm {\bf a}} \in \mathbb Z^n$, and scalar $b \in \mathbb
Z$ (each represented in binary), determine whether there exists a
vector, ${\rm {\bf x}} \in \{0,1\}^n $, such that ${\rm {\bf a}}
\cdot {\rm {\bf x}} = b$.}

\bigskip\noindent Let $S=\{{\rm {\bf a}}\cdot {\rm {\bf x}}:
\mbox{ }{\rm {\bf x}} \in \{0,1\}^n\}$, so the SUBSET-SUM problem
is to determine whether $b \in S$. And consider the following
algorithm, which we shall call algorithm $\mathcal A$, found in a
paper by G.J. Woeginger (2003) and brought to the attention of the
author by R.B. Lyngsoe, which runs in $O(2^{\frac{n}{2}})$ time
(assuming that the algorithm can perform
arithmetic in constant-time and that the algorithm can sort in linear-time)
and can be described as follows:

Sort sets $b-S^-=b-\{{\rm {\bf a}} \cdot {\rm {\bf x}} \in
S:\mbox{ }x_1=...=x_{\lceil \frac{n}{2} \rceil}=0\}$ and
$S^+=\{{\rm {\bf a}} \cdot {\rm {\bf x}} \in S:\mbox{ }x_{\lceil
\frac{n}{2} \rceil+1}=...=x_n=0\}$ in ascending order. Compare the
first two elements in each of the lists. If there is a match, then
stop and output that there is a solution. If not, then compare the
greater element with the next element on the other list. Continue
this process until there is a match, in which case there is a
solution, or until one of the lists runs out of elements, in which
case there is no solution.

We now state and argue two propositions:

\bigskip\noindent \textbf{Proposition 1:} \textit{Algorithm $\mathcal A$
has the best running-time (with respect to $n \geq N$ for large $N$)
of all algorithms which solve SUBSET-SUM, assuming that the algorithms can perform
arithmetic in constant-time and that the algorithms can sort in linear-time.}

\bigskip\noindent \textit{Argument}: We use induction on $n$: We shall leave
it to the reader to find a large enough $N$ to verify the basis
step. Let us assume true for $n$ and prove true for $n+1$: Any
algorithm that solves SUBSET-SUM, given input $([{\rm {\bf
a}}:a_{n+1}],b)$, equivalently solves two subproblems by
determining whether $b-a_{n+1} \in S$ or $b \in S$ (where $S$ is
defined as above for problems of size $n$). Now, if these two
subproblems were completely unrelated to one another, then the
fastest algorithm that solves SUBSET-SUM for problems of size
$n+1$ would solve both subproblems individually using algorithm
$\mathcal A$, by the induction hypothesis; however, the two
subproblems are in fact related to one another in that they both
involve set $S$, so information obtained from solving any one of
the subproblems may be used to solve the other subproblem - Notice
that if solving one of the subproblems takes 6 units of time, 3
units to sort lists $S^-$ and $S^+$ and 3 units to go through the
lists, then it is possible to solve the other subproblem in only 3
units of time, since the lists are already sorted from solving the
first subproblem. Such a procedure takes a total of 9 units of
time, instead of the 12 units of time that it would take to solve
both subproblems individually with algorithm $\mathcal A$.

And it is possible to make even more use of information obtained
from solving any one of the subproblems to save time solving the
other subproblem: If $n$ is odd and the algorithm sorts sets
$S^{-} \cup (S^{-} +a_{n+1})$ and $S^{+}$ instead of sorting sets
$S^{-}$ and $S^{+}$, then the algorithm will take 4 units of time
to sort the lists and 4 units of time to go through the lists, a
total of 8 units of time instead of the 12 units of time that the
algorithm would take to solve both subproblems individually with
algorithm $\mathcal A$. And when $n$ is even, the running-time of
such an improved strategy will not differ from that of the first
intelligent strategy that we mentioned, which takes 9 units of
time. When this improved strategy is implemented, the algorithm
not only solves each subproblem in the fastest way possible by the
induction hypothesis, but also the algorithm makes use of any
information that is obtained from solving any one of the
subproblems to save time solving the other subproblem whenever it
is possible to do such. Therefore, such an algorithm will, for
problems of size $n+1$, have the best running-time of all
algorithms which solve SUBSET-SUM. Since this procedure is, in
fact, descriptive of how algorithm $\mathcal A$ works on problems
of size $n+1$, we have evidence that algorithm $\mathcal A$ has
the best running-time of all algorithms which solve SUBSET-SUM.
\qed

\bigskip\noindent \textbf{Proposition 2:} \textit{Algorithm $\mathcal A$ has
the best asymptotic running-time (with respect to $n$) of all algorithms
that solve SUBSET-SUM when the input is restricted
so that each $|a_i|<2^n$ and $|b|<n \cdot 2^n$.}

\bigskip\noindent\textit{Argument}: Since set $S$ can still be of size $2^n$ when
the input is restricted so that each $|a_i|<2^n$ and $|b|<n \cdot
2^n$, roughly the same arguments in Proposition 1 which show that
$\mathcal A$ is the best algorithm to solve the unrestricted
SUBSET-SUM problem apply also to the restricted SUBSET-SUM problem
where each $|a_i|<2^n$ and $|b|<n \cdot 2^n$. So since SUBSET-SUM
is in $NP$ and $\mathcal A$ runs in super-polynomial time with
respect to $n$ for input of polynomial size $O(n^2)$ (when
expressed in binary), we have evidence that $P \neq NP$.\qed

\bigskip\noindent \textbf{Acknowledgements:} I would like to thank G-d,
my wife Aliza, my parents, my grandparents, and all my true friends for
giving me the inspiration to write this paper.

\bigskip\noindent \textbf{References}:

\bigskip\noindent Bovet, P.B. and Crescenzi, P.
\textit{Introduction to the Theory of Complexity}. Prentice Hall,
1994.

\bigskip\noindent Blum, L., Cucker, F., Shub, M., and  Smale, S.
\textit{Complexity and Real Computation}. Springer-Verlag, New
York, 1998.

\bigskip\noindent Cook, S., ``The Complexity of Theorem Proving
Procedures'', \textit{Conference Record of Third Annual ACM
Symposium on Theory of Computing}, pp. 151-158, 1971.

\bigskip\noindent Karp, R.M., ``Reducibility Among Combinatorial
Problems'', in: Miller, R.E. and Tatcher, J.W., eds.,
\textit{Complexity of Computer Computations}, Plenum Press,
85-103, 1972.

\bigskip\noindent Papadimitriou, C. \textit{Computational Complexity}.
Addison Wesley, 1994.

\bigskip\noindent Razborov, A.A. and Rudich, S., ``Natural Proofs'', \textit{J. Comput.
System Sci.}, 55, pp. 24-35, 1997.

\bigskip\noindent Woeginger, G.J., ``Exact Algorithms for NP-Hard Problems'',
\textit{Lecture Notes in Computer Science}, Springer-Verlag Heidelberg,
Volume 2570, pp. 185-207, 2003.


\end{document}
