\documentstyle[IEEEtran]{article}
\begin{document}

\title{Linear Interval Equations: Computing Sufficiently Accurate
Enclosures is NP-Hard}
\author{J. Rohn}

\pagestyle{myheadings}

\markright{APIC'95, El Paso,
Extended Abstracts,
A Supplement to the international journal of {\rm Reliable
Computing}\ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ }

\maketitle

\auffil{The author is with Charles University and Czech Academy of
Sciences, Prague, Czech Republic.}

\newtheorem{theorem}{Theorem}

For a system of linear interval equations $$A^I x=b^I\eqno{(1)}$$
($A^I$ square), {\bf enclosure} is defined as an interval vector
$[\underline y,\overline y]$ 
satisfying $$X\subseteq [\underline y,\overline y]$$ where $X$ is the
solution set: 
$$X=\{x;\,Ax=b {\rm \ for\ some\ } A\in A^I, B\in B^I\}.$$
If $A^I$ is regular, then there exists the narriwest enclosure
$[\underline x,\overline x]$ 
given by ${\underline x}_i=\min_X x_i$, ${\overline x}_i=\max_X x_i$
for each $i$. Computing $[\underline x,\overline x]$ was proved to be
NP-hard \cite{1}. But it turns out that the same is true for computing
``sufficiently accurate'' enclosures: 

\begin{theorem}
Suppose there exists a polynomial-time algorithm which for each {\bf
strongly} regular $n\times n$ matrix $A^I$ and each $b^I$ (both with
rational bounds) computes a rational enclosure 
$[\underline y,\overline y]$ for (1) satisfying 
$${\overline x}_i\le {\overline y}_i\le {\overline x}_i+{1\over
32n^4}\eqno{(2)}$$ for each $i$. Then {\bf P=NP}.
\end{theorem}

\noindent{\bf Comments}

$A^I$ is called strongly regular if $\rho(|A^{-1}\Delta)<1$ (a
well-known sufficient regularity condition). 

P and NP are well-known complexity classes. The conjecture that
P$\ne$NP, although unproved, is widely believed to be true. 

Hence, the problem of computing sufficiently accurate enclosures is by
by far more {\bf difficult} than previously believed: an existence of
a polynomial-time algorithm yielding the accuracy (2) would imply
polynomial-time solvability of all problems in the calss NP, thereby
making an enormous breakthrough in theoretical computer science. 

\begin{thebibliography}{99}
\bibitem{1}
J. Rohn, V. Kreinovich, ``Computing exact
componentwise bounds on solutions of linear systems with interval data is
NP-hard'',
{\it SIAM Journal on Matrix Analysis and Applications (SIMAX),}
1995, Vol. 16, No. 2 (to appear).    
\end{thebibliography}

\end{document}