Skip to main content
10 of 13
added 6 characters in body
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Detecting non-negativity of a single constraint by polyhedral constraints - $I$

We consider $$\langle a,x\rangle=b$$ (linear constraints) where $x\in\mathbb R^n$ and every entry in $a=(a_1,\dots,a_n)$ is in $\mathbb Z_{\geq0}^{n}$ (non-negative) and the entry $b$ is in $\mathbb Z_{\geq0}$ (non-negative) and are of $m=poly(n)$ bitlength.

Is there an universal polyhedron $By\leq c$ (depending on $m,n$) satisfying the properties

  1. $B\in\mathbb Z^{q\times(n+1)},c\in\mathbb Z^{q}$ where $q=poly(n)$
  2. $\log_2\max_{i,j}|B_{i,j}c_i|=poly(n)$
  3. $\forall a,b\in\mathbb Z_{\geq0}^{n+1}\cap[0,2^m]^n\times2^{m}\exists x\in\mathbb R_{\geq0}^n:\langle a,x\rangle=b\iff B[a,b]'\leq c$

satisfied?

Turbo
  • 13.9k
  • 1
  • 27
  • 76