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?

  • 1
    $\begingroup$ 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? $\endgroup$ – usul Mar 9 '13 at 1:24
  • $\begingroup$ @usul : Thx, I got a typo there :) $\endgroup$ – Squark Mar 9 '13 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.