0
$\begingroup$

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.

$\endgroup$
11
  • 2
    $\begingroup$ logic tag is definitely inappropriate. $\endgroup$ Commented May 8, 2021 at 11:34
  • $\begingroup$ Polyhedra encodes certain 'iff' information and utilizing polyhedra could be interpreted as Presburger. $\endgroup$
    – Turbo
    Commented May 8, 2021 at 11:46
  • $\begingroup$ something akin to Farkas Lemma? $\endgroup$ Commented May 8, 2021 at 18:31
  • $\begingroup$ Sorry, I don't understand the question. Do you already know that $a$ and $b$ are as specified? Cause of they are, then $x$ wil always exist (just one positive $a_k$ will do, in fact). $\endgroup$ Commented May 10, 2021 at 10:19
  • $\begingroup$ Or you want to encode with $B$ and $c$ the formula "if $b\neq 0$ then there exists $k$ so that $ba_k> 0$ ? $\endgroup$ Commented May 10, 2021 at 10:23

1 Answer 1

2
$\begingroup$

By Farkas Lemma $Ax=b,\ x\geq 0$ is solvable if and only if $A^\top y\geq 0,\ b^\top y<0$ is not solvable.

That's the best one can do here, I don't think anything telling you individual solvability of each equation will help - especially if you know already that each individual equation is solvable.

$\endgroup$
9
  • $\begingroup$ I am looking for a formal proof no polyhedra involving $B$ exists and it is likely a simple convexity argument and I am missing it. 'I don't think' is not convincing. $\endgroup$
    – Turbo
    Commented May 10, 2021 at 13:52
  • $\begingroup$ anything that only depend on an individual equation will not work, and your B is like this. $\endgroup$ Commented May 10, 2021 at 14:04
  • $\begingroup$ I think I can sense it but I do not see it. $\endgroup$
    – Turbo
    Commented May 10, 2021 at 14:21
  • $\begingroup$ Any $B, c$ so that the corr. system of inequalities holds for any $a\geq 0$, $b\geq 0$ will do. These $B, c$ all describe the same polyhedron, the positive ortant. $\endgroup$ Commented May 10, 2021 at 15:33
  • $\begingroup$ So there is a $B$? $\endgroup$
    – Turbo
    Commented May 10, 2021 at 15:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .