• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 2
Sort:
by name
by year
Article
Grigoriev D., Podolskii V. V. Computational Complexity. 2015. Vol. 24. No. 1. P. 31-64.

A tropical (or min-plus) semiring is a set $\mathbb{Z}$ (or $\mathbb{Z \cup \{\infty\}}$) endowed with two operations: $\oplus$, which is just usual minimum, and $\odot$, which is usual addition. In tropical algebra a vector $x$ is a solution to a polynomial $g_1(x) \oplus g_2(x) \oplus \ldots \oplus g_k(x)$, where $g_i(x)$'s are tropical monomials, if the minimum in $\min_i(g_{i}(x))$ is attained at least twice. In min-plus algebra solutions of systems of equations of the form $g_1(x)\oplus \ldots \oplus g_k(x) = h_1(x)\oplus \ldots \oplus h_l(x)$ are studied. In this paper we consider computational problems related to tropical linear system. We show that the solvability problem (both over $\mathbb{Z}$ and $\mathbb{Z} \cup \{\infty\}$) and the problem of deciding the equivalence of two linear systems (both over $\mathbb{Z}$ and $\mathbb{Z} \cup \{\infty\}$) are equivalent under polynomial-time reductions to mean payoff games and are also equivalent to analogous problems in min-plus algebra. In particular, all these problems belong to $\mathsf{NP} \cap \mathsf{coNP}$. Thus, we provide a tight connection of computational aspects of tropical linear algebra with mean payoff games and min-plus linear algebra. On the other hand we show that computing the dimension of the solution space of a tropical linear system and of a min-plus linear system is $\mathsf{NP}$-complete.

Added: May 30, 2015
Article
Vereshchagin N., Bauwens B. F., Makhlin A. et al. Computational Complexity. 2018. Vol. 27. No. 1. P. 31-61.

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal  machine, it is possible to compute  in polynomial time  on input $x$ a  list of polynomial size guaranteed to contain a $O(\log |x|)$-short program  for $x$. We also show that there exist computable functions that map every $x$ to a list of size $O(|x|^2)$ containing a $O(1)$-short program for $x$ and this is essentially optimal  because we prove that such a list must have  size  $\Omega(|x|^2)$. Finally we show that for some machines, computable  lists containing a shortest  program must have length $\Omega(2^{|x|})$.

Added: Apr 22, 2017