
PreviousNext
In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem
(ILP$_{\bf R}$) : Given a matrix $A \in {\bf R}^{m \times n}$ and vectors
$b \in {\bf R}^m$, $d \in {\bf R}^n$, decide if there is $x ...
more >>>
C.H.~Bennett, P.~G\'acs, M.~Li, P.M.B.~Vit\'anyi, and W.H.~Zurek
have defined information distance between two strings $x$, $y$
as
$$
d(x,y)=\max\{ K(x|y), K(y|x) \}
$$
where $K(x|y)$ is the conditional Kolmogorov complexity.
It is easy to see that for any string $x$ and any integer $n$
there is a string $y$ ...
more >>>
PreviousNext