Another approach to Decide Solvability of Univariate IntegerPolynomials, and a possible Multivariate Extension - Theory

Hi All,

The Conjecture-1 in the Version_2 of my paper had a serious flaw in
it. As a result, I have now modified Conjecture-1, and have now
published my Version_3 paper on http://arxiv.org/abs/0803.0018

In my Version_3, I have also added instructions on how 3-SAT with u
binary variables may be converted to the Question of deciding whether
or not a u-variate real polynomial has a real root in the hyper-
quadrant defined by every variable being greater than 0.

So please read my paper at http://arxiv.org/abs/0803.0018

I have NOT made any other serious change to my paper.

I am eagerly awaiting your comments, and reviews, on my paper.

Thanks & faithfully,
-Deepak

Dr. Moews, Dr. Saugata, Dr. Kayal, Dr. Tim Chow, Dr. Diaby, and Mr.
Radek Hofman,

There are 5 important observations I just made regarding the structure
of the multivariate Polynomial Equation obtained from 3-SAT, using the
procedure in the last page of my paper at http://arxiv.org/abs/0803.0018

These 5 observations are as follows:

Observation-1: The degree, N, is bounded by a constant.

Observation-2: The number of terms separated by + or - signs, is
bounded by a polynomial function of the number of clauses in the 3-
SAT, and the number of binary variables in the 3-SAT instance.

Observation-3: Within each term, the number of variables involved in
the product, is bounded by a constant (this constant is 3 to be
precise, as 3-SAT has only 3 literals per clause).

Observation-4: The max coefficient, M, is bounded by a polynomial
function of the number of clauses in the 3-SAT, and the number of
binary variables in the 3-SAT instance.

Observation-5: As BETA's lower bound is similar to the lower bound of
the Min_Separation_between_real_roots (I have explained the reason for
this in Lemma-3.2 of my paper), so the Inverse of BETA must be bounded
by an exponential function of the number of clauses in the 3-SAT, and
the number of binary variables in the 3-SAT instance.

I agree that my two Conjectures might not help in making a P-time
algorithm for 3-SAT, primarily because of the fact that the inverse of
BETA increases exponentially with the size of the 3-SAT instance, as
described in my Observation 5.

However, do you feel that my two Conjectures might improve the current
best algorithm's complexity for NP-Complete problems, which I
understand is O(C^(1.5N)) ?

Also another remaining task for us, is to get a solid mathematical
proof for Conjecture-1. It is obvious that the 3-SAT instance is
unsatisfiable, if the multivariate Polynomial obtained from the 3-SAT
instance, is a factor of some Polynomial with positive coefficients.
However, the opposite is not necessarily true, i.e. we cannot
immediately conclude that the 3-SAT instance is satisfiable, if it is
impossible to show that the multivariate Polynomial obtained from the
3-SAT instance, is a factor of some Polynomial with positive
coefficients. Going further, the multivariate case might not be as
simple as the univariate case (note that in the univariate case, based
on the solid proofs shown in my paper, we may conclude that P=0 is
unsolvable if P is a factor of some polynomial with positive
coefficients, and that P=0 is solvable if it is not possible to show
that P is a factor of some polynomial with positive coefficients).

I hope you will be able to give me some pointers on my 3 Questions:

QUESTION-1: Am I correct regarding the 5 observations that I made
regarding the structure of the multivariate polynomial Equation
obtained from 3-SAT (I would especially like to know whether my
Observations 4 & 5 are correct) ?

QUESTION-2: Do you feel that if my two Conjectures are true, then they
might improve the current best algorithm's complexity for 3-SAT, which
I understand is O(C^(1.5N)) ?

QUESTION-3: Is it possible for us to get a solid mathematical proof
for Conjecture-1 ?

I look forward to your replies to my 3 Questions.

Thanks,
-Deepak

There was a typo error in the last sentence of my para 10 of my
previous post. The correct sentence should read: - "note that in the
univariate case, based on the solid proofs shown in my paper, we may
conclude that P=0 is unsolvable in ]0,+infinity[ if P is a factor of
some polynomial with positive coefficients, and that P=0 is solvable
in ]0,+infinity[ if it is not possible to show that P is a factor of
some polynomial with positive coefficients".

After more study, I now think that BETA's inverse increases
polynomially, and not exponentially, with the number of vars & number
of clauses in the 3-SAT instance. This is via a simple reduction to
the univariate case.

Before that, for the benefit of all those who are lost on what is
BETA, you may consider BETA as the mimum absolute value of the
imaginary component in the complex roots of the multivariate
polynomial derived from the 3-SAT instance, as described in the last
page of my paper http://arxiv.org/abs/0803.0018

OK now coming back to the point, the reason why I believe that BETA's
inverse increases polynomially is explained in the following 6 steps:

1.) Consider the multivariate polynomial equation derived from the 3-
SAT as P(X1, X2, X3, ... Xu)=0.

2.) The degree of the above equation is bounded by a constant (this
constant is 2 to be precise), so if we consider 2^(N-1) cases of each
element of {X2, X3, ... Xu} being either 1 or 2, then we can get
2^(N-1) different Equations in 1 variable, i.e. in X1.

3.) If any one of the above 2^(N-1) univariate quadratic Equations has
a solution, then the 3-SAT does have a solution.

4.) Also, the max absolute value of coefficients in the above 2^(N-1)
univariate quadratic Equations, is a polynomial function of the number
of variables & the number of clauses in the 3-SAT instance.

5.) Similarly, even if we were to repeat our step 2. to obtain 2^(N-1)
univariate quadratic Equations for each of the variables Xi, i belongs
to [1,N], it is still found that the max absolute value of
coefficients in the 2^(N-1) univariate quadratic Equations in Xi, is a
polynomial function of the number of variables & the number of clauses
in the 3-SAT instance.

6.) Note that when we are obtaining the univariate quadratic equation
in one variable, by considering all other variables to be either equal
to 1 or 2, we are basically considering points of local optima in the
sketch of the multivariate polynomial.

Thus, in the worst case, the minimum absolute value of any imaginary
part of the multivariate Equation is always either some polynomial
function of the number of variables & clauses in the 3-SAT, or equal
to inverse of this polynomial function.

Thus, the inverse of BETA is most probably a polynomial function of
the size of the 3-SAT instance.

However, in spite of this, I believe that it might still need a u-
variate T having an exponential number of terms, which when multiplied
with multivariate P, would yield a u-variate with positive
coefficients, to show that P does not have a root in the positive
hyperquadrant defined by each variable being greater than 0. The
reason is that when we consider a univariate P, i.e. P(X), this is
basically a univariate quadratic, that needs to be multiplied with T
having a number of terms equal to PI*(MAX), to give an expression with
positive coefficients. When we go on to have a 2-variate P, then the
number of terms in T is likely to increase to T^2. When we have a 3-
variate P, then T is likely to have T^3 terms. So when we have u-
variate P, then T is likely to have T^u terms, which is exponential in
u.

Thus, my above argument indicates that the complexity of my approach
increases as an exponential function, of the size of the 3-SAT
instance, even though BETA is probably a polynomial function, of the
size of the 3-SAT instance.

Sorry for the typo-error in my last-but-one paragraph of my previous
message. The corrected para should read as:

However, in spite of this, I believe that it might still need a u-
variate T having an exponential number of terms, which when multiplied
with multivariate P, would yield a u-variate with positive
coefficients, to show that P does not have a root in the positive
hyperquadrant defined by each variable being greater than 0. The
reason is that when we consider a univariate P, i.e. P(X), this is
basically a univariate quadratic, that needs to be multiplied with
univariate T having a number of terms equal to PI*MAX_COEFFICIENT, to
give an expression with positive coefficients. When we go on to have a
2-variate P, then the number of terms in 2-variate T is likely to
increase to (PI*MAX_COEFFICIENT)^2. When we have a 3-variate P, then 3-
variate T is likely to have (PI*MAX_COEFFICIENT)^3 terms. So when we
have u-variate P, then u-variate T is likely to have
(PI*MAX_COEFFICIENT)^u terms, which is exponential in u.

After some more enlightening discussions with Dr. Moews, we found that
every u-variate Polynomial "P" (for u > 1) is capable of having roots
with arbitrarily small imaginary components. A simple proof is as
follows. Let {X1,X2,...Xu} denote the variables in P. Let us assign
X1=(a)+I(b), where a and b are real, and where b is arbitrarily small,
and where "I" denotes the imaginary component. Now, it is
straightforward to understand that by substituting this value of X1 in
P, we can obtain complex solutions for the remaining variables
{X2,X3...Xu} such that P evaluates to zero. Though the solutions of
these remaining variables may or may not have arbitrarily small
imaginary components, it is obvious that X1 can have an arbitrarily
small imaginary component.

Thus, though my current definition of BETA as the smallest absolute
value of the non-zero imaginary component in the complex roots of P,
does exist if P is Univariate, this definition does not exist if P is
multivariate.

Therefore, I propose a new definition of BETA as follows.

BETA = minimum
(minimum_abs_value_of_non_zero_Imaginary_components_of_roots_of_Xi_in_P,
for all {Xj belongs to Reals, j not equal to i}, for every i in [1,u])

Sorry if my above definition sounds wrong in strict math language, but
what I basically mean is that if we were to select a particular
variable Xi, and get infinite permutations of all other variables
being put as every Real number, then we will get infinite Univariate
Polynomials in Xi. Now again repeat this for every i in [1,u], where u
is the number of vars in P. So what I am saying is that BETA is the
minimum absolute value of non-zero Imaginary components of roots,
obtained from all these Univariate Real Polynomials.

Also, my Conjecture-1 of my ARXIX paper "http://arxiv.org/abs/
0803.0018" is true. And I have a proof for this as follows. Let
P'=P^2. It is obvious that if we were to look at the REAL-sketch of
P', then P' can either touch the Y=0 plane if P' has a real root, or
P' will be above the Y=0 plane if P' does not have a real root. Now
select any variable Xi, and get infinite permutations of all other
variables being put as every Real number, then we will get infinite
Univariate Polynomials (I denote the family of these Univariate
Polynomials as Li) in Xi. Now again repeat this for every i in [1,u],
where u is the number of vars in P'. It is obvious that if P' does not
have a root (i.e. it is above the Y=0 plane in every possible way of
looking at P'), then it should be possible to identify Polynomials
(based on Theorem-1) of my paper, which when multiplied with the each
of the Univariate family Li, would yield a resulting polynomial with
positive coefficients, if Xi does not have a real positive root. This
means that when we consider the multivariate P' as a whole, then it
should be possible to identify a multivariate T, which when multiplied
with P, would yield a multivariate V with positive coefficients, if P
does not have a real root in the space defined by each var being > 0.
Thus (P*P)*T = V, which means P is a factor of V.

A question some of you might have is that while getting the Univariate
Polynomials in Xi, why are we putting the other variables (i.e. the
vars other than Xi) as only Real numbers, why not put them as some
Complex numbers with Imaginary components? The reason is that we are
interested in the planes containing local minima only in the REAL-
sketch of P, and not in the IMAGINARY-sketch of P.

Now coming back to my u-variate Polynomial "P" derived from 3-SAT. In
the paragraphs that follow, "P" shall refer to the u-variate
polynomial derived from the 3-SAT instance.

If you see carefully, the inverse of BETA (based on my new definition)
in P, is polynomially bounded by the size of the 3-SAT instance. The
reason is that if we obtain 2^(N-1) univariate quadratics in Xi, by
putting all other variables != Xi, as either 1 or 2 in P, then the
coefficients of the quadratics are integers that are polynomially
bounded by the 3-SAT size. By putting all other variables as either 1
or 2, we are considering planes of local minima in the REAL-sketch of
P.

A question some of you might again have is, why are we putting the
other variables as only 1 or 2, why not put them as some other Real
numbers? The reason is because if we put these other variables as Real
numbers other than 1 or 2, because in that case we will not be
considering planes of local minima, but these will be some other
planes that are not cutting the local minima.

So I hope you all agree that the inverse of BETA (based on my new
definition) is indeed polynomially bounded by the size of the 3-SAT
instance.

Still, inspite of the fact that BETA's inverse is polynomially bounded
by the size of the 3-SAT instance, I still believe that we might most
probably need an exponential amount of effort to express the
polynomial T, which needs to be multiplied with polynomial P derived
from 3-SAT, to yield a polynomial V with positive coefficients, to
show that the 3-SAT instance is unsatisfiable.

One way of expressing T can be T = T1*T2*T3...*Tu, where "*" denotes
the multiplication operator. T1 is a univariate polynomial in X1,
whose degree is polynomially bounded by the 3-SAT size (more
precisely, the degree is equal to
PI*MAX_COEFF_IN_ALL_UNIVARIATE_QUADRATICS_IN_X1_OBTAINED_BY_PUTTING_ALL_OTHER_VARS_OF_P_EQUAL_TO_EITHER_1_OR_2).
Similarly, T2, T3,..Tu are univariate polynomials in X2, X3,...Xu
respectively, whose degrees is polynomially bounded.

It is obvious that even if the degrees of T1, T2, T3, ...Tu are each
bounded by a smallest number possible (i.e. 1), then if we expand the
product of T1*T2*T3...*Tu, we will still get an expression, where the
number of terms is exponential in "u".

Therefore, if we want to prove P=NP, then we must try and focus our
efforts in trying to express T, not by expanding T1*T2*T3...*Tu, but
by some other smarter technique.

Or we could directly try to show somehow that T*P = V with positive
coefficients, where size of expressing both T and V is a polynomial
function of the size of P.

The "heuristic" reason why I believe that there is a small chance that
this is possible, is because it might be possible to define a u-
variate Polynomial, without actually listing its coefficients. One
parallel inspiration I draw is from the example of SLPs (Straight Line
Programs), which are able to give a P-time expression of Univariate
Polynomials, though there could be an exponential number of monomial
terms in this Univariate Polynomail (note that if we try to define
this polynomial by enlisting its coefficients, then it would take
exponential effort).

I eagerly look forward to your comments/questions.

Thanks & faithfully,
-Deepak