<p>Consider the following optimization problem</p>
<blockquote>
<p><strong>INSTANCE</strong>: vectors <span class="math-container">$\vec{a}, \vec{b}, \vec{c}$</span>, matrices <span class="math-container">$A, B$</span>, threshold <span class="math-container">$\theta$</span>.</p>
<p><strong>PROBLEM</strong>:</p>
<p>Let <span class="math-container">$f={\displaystyle \max_{\vec{x}, \vec{y}}} (\vec{x}+\vec{c}) \cdot \vec{y}$</span></p>
<p>subject to <span class="math-container">$A\vec{x}\leq \vec{a}$</span> and <span class="math-container">$B\vec{y}\leq \vec{b}$</span></p>
<p><strong>Is <span class="math-container">$f \le \theta$</span></strong> ?</p>
</blockquote>
<p>This problem is in co-NP (provide a witness that <span class="math-container">$f &gt; \theta$</span>).</p>
<blockquote>
<p>Is this problem in NP ?</p>
</blockquote>

CC BY-SA 3.0
2014-03-21T16:26:42.147Z
Can lagranges multiplier method be used to obtain the maximum value? (Just a random thought)
Vivek Bagaria
CC BY-SA 3.0
2014-03-21T21:37:35.173Z
what does $\vec{x}\leq\vec{a}$ mean for vectors $\vec{x}$ and $\vec{a}$?
Turbo
CC BY-SA 3.0
2014-03-22T08:09:31.880Z
it's a componentwise comparison: shorthand for a set of inequalities.
Suresh Venkat
<cc.complexity-theory><optimization>
NP algorithm for an optimization problem
user22135
# NP algorithm for an optimization problem

(Asked by: username_0 on 2014-03-21)

Consider the following optimization problem

> **INSTANCE**: vectors $\vec{a}, \vec{b}, \vec{c}$, matrices $A, B$, threshold $\theta$.
>
> **PROBLEM**:
>
> Let $f={\displaystyle \max\_{\vec{x}, \vec{y}}} (\vec{x}+\vec{c}) \cdot \vec{y}$
>
> subject to $A\vec{x}\leq \vec{a}$ and $B\vec{y}\leq \vec{b}$
>
> **Is $f \le \theta$** ?

This problem is in co-NP (provide a witness that $f > \theta$).

> Is this problem in NP ?

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

> **Comments:**
> **username_1**: Can lagranges multiplier method be used to obtain the maximum value? (Just a random thought)  
> **username_2**: what does $\vec{x}\leq\vec{a}$ mean for vectors $\vec{x}$ and $\vec{a}$?  
> **username_3**: it's a componentwise comparison: shorthand for a set of inequalities.  

---

## 0 answers

