Return to Question

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=O(1)$ 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\in\{0,1\}^n, b\in\mathbb Z\cap[1,2^{m}]$ $$B[a,b]'\leq c\implies\exists x\in\mathbb R_{\geq0}^n:\langle a,x\rangle=b$$

satisfied?

We consider $$\langle a,x\rangle=b$$ (linear constraints) where $x\in\mathbb R_{\geq0}^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=O(1)$ 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\in\{0,1\}^n, b\in\mathbb Z\cap[1,2^{m}]$ $$B[a,b]'\leq c\implies\exists x\in\mathbb R_{\geq0}^n:\langle a,x\rangle=b$$

satisfied?

If we had a $B,c$ and we are given $Ax=b$ a linear system and are required to identify if no $x\in\mathbb R_{\geq0}^n$ satisfies $Ax=b$ we can check $B[a[i],b_i]'\leq c$ at every $i\in\{1,\dots,\ell\}$ where $\ell$ is number of rows in $A$ and if there is no $x$ at least one of $B[a[i],b_i]'\leq c$ would be not satisfied.

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}$ $$B[a,b]'\leq c\implies\exists x\in\mathbb R_{\geq0}^n:\langle a,x\rangle=b$$

satisfied?

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=O(1)$ 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\in\{0,1\}^n, b\in\mathbb Z\cap[1,2^{m}]$ $$B[a,b]'\leq c\implies\exists x\in\mathbb R_{\geq0}^n:\langle a,x\rangle=b$$

satisfied?

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?

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}$ $$B[a,b]'\leq c\implies\exists x\in\mathbb R_{\geq0}^n:\langle a,x\rangle=b$$

satisfied?