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$ May 8, 2021 at 11:34
  • $\begingroup$ Polyhedra encodes certain 'iff' information and utilizing polyhedra could be interpreted as Presburger. $\endgroup$
    – Turbo
    May 8, 2021 at 11:46
  • $\begingroup$ something akin to Farkas Lemma? $\endgroup$ 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$ 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$ 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
    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$ May 10, 2021 at 14:04
  • $\begingroup$ I think I can sense it but I do not see it. $\endgroup$
    – Turbo
    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$ May 10, 2021 at 15:33
  • $\begingroup$ So there is a $B$? $\endgroup$
    – Turbo
    May 10, 2021 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.