Date: Fri, 9 Oct 1998 10:10:28 +0200 (MET DST)
From: Carsten Lutz <clu@cantor.informatik.rwth-aachen.de>
To: rusin@math.niu.edu
Subject: complexity questions (fwd)

---------- Forwarded message ----------
Date: Thu, 8 Oct 1998 09:14:18 -0600 (MDT)
From: Brian Borchers <borchers@nmt.edu>
To: clu@cantor.informatik.rwth-aachen.de
Subject: complexity questions

Integer linear programming is NP-hard, and thus optimization over Z with
any sort of of polynomial constraints and objective function is NP-hard.

Furthermore, integer programming feasibility problems (is there an 
integer solution to this system of linear (in)eqaulities) are NP-hard
and can be formulated as nonconvex quadratic programming problems over
the reals.  Thus optimization over R with general polynomial constraints
is NP-hard.  
 
To show this last point, consider a 0-1 linear integer programming feasibility
problem:
 
    Determine whether or not there is a 0-1 vector x such that Ax=b.  
 
This can be converted into a quadratic system of equations as follows:
 
    (Ax-b)'*(Ax-b)=0              
     x_i*(1-x_i)  =0       i=1, 2, ... n

Note that ' means "transpose"
 
Note that this system of equations is clearly of size polynomial in the
size of the original system of equations.  

If you could determine the feasibility of this quadratic system of
equations in polynomial time, then you could solve the 0-1 linear
integer programming feasibility problem in polynomial time, and since
the 0-1 linear integer programming feasibility problem is NP-complete, 
you'd have shown that P=NP.  

Brian Borchers                          borchers@nmt.edu                     
Department of Mathematics               http://www.nmt.edu/~borchers/        
New Mexico Tech                         Phone: 505-835-5813                  
Socorro, NM 87801                       FAX: 505-835-5366