# Existence of complete “asymptotic” optimization problems

Define a function $u:\lbrace 0,1 \rbrace^* \rightarrow \mathbb{R}$ to be an asymptotic optimization problem when the following conditions hold:

• There is an algorithm $U$ which computes the first $n$ digits of $u(x)$ in time at most $p(2^n, |x|)$ where $p$ is a polynomial
• There are $a$, $c > 0$ s.t. given $x$ a prefix of $y$ we have $|u(x)-u(y)|<2^{-c|x|}a$

It is possible to restrict attention to functions $u:\lbrace 0,1 \rbrace^* \rightarrow [0,1]$ since any function satisfying the 2nd condition can be brought to this form by a linear redefinition

Consider $u$, $v$ asymptotic optimization problems. $f: \lbrace 0,1 \rbrace^* \rightarrow \lbrace 0,1 \rbrace^*$ is a called a reduction of $u$ to $v$ when the following conditions hold:

• Given $x$ a prefix of $y$, $f(x)$ is a prefix of $f(y)$
• For any $u_0 < \sup u$ exists $w(u_0) < \sup v$ s.t. given $s \in \lbrace 0,1 \rbrace^\omega$, if $\lim_{n \rightarrow \infty}v(s_{<n}) > w(u_0)$ then $\lim_{n \rightarrow \infty}u(f(s_{<n})) > u_0$

The reduction is called polynomial-time when $f$ is computable in polynomial time

Is there $u^*$ an asymptotic optimization problem s.t. any asymptotic optimization problem $u$ is reducible to $u^*$ in polynomial time?

• I'm a bit confused by your second condition -- does it say that the longer $x$ gets, the worse of an approximation it may be? – usul Mar 9 '13 at 1:24
• @usul : Thx, I got a typo there :) – Vanessa Mar 9 '13 at 9:34