# NP algorithm for an optimization problem

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 ?

• Can lagranges multiplier method be used to obtain the maximum value? (Just a random thought) – Vivek Bagaria Mar 21 '14 at 16:26
• what does $\vec{x}\leq\vec{a}$ mean for vectors $\vec{x}$ and $\vec{a}$? – Turbo Mar 21 '14 at 21:37
• it's a componentwise comparison: shorthand for a set of inequalities. – Suresh Venkat Mar 22 '14 at 8:09