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

<ul>
<li>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</li>
<li>There are $a$, $c &gt; 0$ s.t. given $x$ a prefix of $y$ we have $|u(x)-u(y)|&lt;2^{-c|x|}a$</li>
</ul>

<p>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</p>

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

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

<p>The reduction is called polynomial-time when $f$ is computable in polynomial time</p>

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

CC BY-SA 3.0
2013-03-09T01:24:34.343Z
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
CC BY-SA 3.0
2013-03-09T09:34:49.930Z
@usul : Thx, I got a typo there :)
Vanessa
<cc.complexity-theory><optimization>
Existence of complete "asymptotic" optimization problems
Vanessa
# Existence of complete "asymptotic" optimization problems

(Asked by: username_0 on 2013-03-08)

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\_{ w(u\_0)$ then $\lim\_{n \rightarrow \infty}u(f(s\_{ 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?

**Tags:** cc.complexity-theory, optimization

> **Comments:**
> **username_1**: 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?  
> **username_0**: @username_1 : Thx, I got a typo there :)  

---

## 0 answers

