function [sol,x]=verbasintnpprob(A,t)
%    VERBASINTNPPROB     Verified solution of the basic NP-complete problem of interval computations.
%
%    This is an INTLAB file. It requires to have INTLAB installed under
%    MATLAB to function properly.
%
%    For a square real (noninterval) matrix A,
%    [sol,x]=verbasintnpprob(A)
%    either yields a verified real solution x of the system
%        -e <= A*x <= e,        (1)
%        norm(x,1) >= 1,        (2)
%    where e is the vector of all ones, or verifies that (1), (2) has no
%    solution, or gives no verified result:
%
%    sol= 1           x is a verified solution of (1), (2),
%    sol= 0           it is verified that (1), (2) has no solution;
%                     x is a vector of NaN's,
%    sol=-1           no verified result (A may be not square or not real).
%
%    [sol,x]=verbasintnpprob(A,1) [i.e., with additional input argument "1"]
%                     works in the same way as before, but it also produces screen
%                     output of the form "Expected remaining time: ... sec."
%                     This feature, however, slows down the actual computation.
%
%    COMMENT. In [1], Chapters 2 and 3, it is shown that the problem of
%    solvability of (1), (2) is NP-complete (even for nonnegative
%    positive definite rational matrices), and that NP-completeness or
%    NP-hardness of all the basic interval linear problems can be proved using
%    this fact. In this way the problem (1), (2) can be considered, at least
%    theoretically, the basic NP-complete problem of interval computations.
%
%    [1] M. Fiedler, J. Nedoma, J. Ramik, J. Rohn and K. Zimmermann, Linear
%    Optimization Problems with Inexact Data, Springer-Verlag, New York 2006.

%    Copyright 2008 Jiri Rohn
%
%    This work was supported by the Czech Republic National Research
%    Program "Information Society", project 1ET400300415.
%
%    WARRANTY
%
%    Because the program is licensed free of charge, there is
%    no warranty for the program, to the extent permitted by applicable
%    law. Except when otherwise stated in writing the copyright holder
%    and/or other parties provide the program "as is" without warranty
%    of any kind, either expressed or implied, including, but not
%    limited to, the implied warranties of merchantability and fitness
%    for a particular purpose. The entire risk as to the quality and
%    performance of the program is with you. Should the program prove
%    defective, you assume the cost of all necessary servicing, repair
%    or correction.
%
% set rounding to nearest
gr=getround;
setround(0);
% setting default output
[m,n]=size(A);
sol=-1; x=repmat(NaN,n,1);
% checking compatibility of data
if ~(m==n&&isreal(A)&&~isintval(A)) % error('matrix not square or not real'),
    setround(gr); return
end
if issparse(A)
    A=full(A); % sparse matrices not implemented yet
end
% time display
if (nargin==2)&&isequal(t,1) % t==1: display remaining time
    time=1;
else
    time=0;
end
tol=1e-10;
e=ones(n,1);
AA=midrad(A,ones(n,n));
% main part: application of verregsing
[reg,As]=verregsing(AA,time); % solution exists if and only if AA is singular; Fiedler et al., proof of Thm. 2.33
% output cases
if reg==-1 % no result
    sol=-1;
    setround(gr); return
end
if reg==1 % AA regular, verified no solution
    sol=0;
    setround(gr); return
end
if reg==0 % AA singular, verified that solution exists
    % finding a solution; solutions are Oettli-Prager vectors of AA taken as null vectors of mid(As)
    X=null(mid(As));
    if isempty(X) % no null vector available
        sol=-1;
        setround(gr); return
    end
    for x1=X % null vectors of mid(As) (candidates for solution) inspected
        x2=x1/(norm(x1,1)-tol); % tol used to ensure norm(x2,1)>=1
        xx=infsup(x2,x2);
        if all(in(A*xx,infsup(-e,e)))&&in(norm(xx,1),infsup(1,Inf)) % xx verified to be a solution
            sol=1;
            x=x2; % noninterval output
            setround(gr); return
        end
    end
    sol=-1;
    setround(gr); return
end