Skip to main content
Post Undeleted by Turbo
Post Deleted by Turbo
edited tags
Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
added 92 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Let $$\langle a,x\rangle=b$$ be a linear constraint 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)$ bit length.

Is there a polyhedron $By\leq c$ (depending on $a,b$) 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|=O(n)$ ($O(n)$ bit length)
  3. $B,c$ constructible in $O(\log n)$ time in $poly(n)$ processors ($NC^1$ complexity)
  4. $\exists x\in\mathbb R_{\geq0}^n:\langle a,x\rangle=b\iff B[a,b]'\leq c$ or at least $B[a,b]'\leq c\implies \exists x\in\mathbb R_{\geq0}^n:\langle a,x\rangle=b$

satisfied?

I think there might be (perhaps every entry of $B,c$ can be computed in $O(\log n)$ time).

Let $$\langle a,x\rangle=b$$ be a linear constraint 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)$ bit length.

Is there a polyhedron $By\leq c$ (depending on $a,b$) 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|=O(n)$ ($O(n)$ bit length)
  3. $B,c$ constructible in $O(\log n)$ time in $poly(n)$ processors ($NC^1$ complexity)
  4. $\exists x\in\mathbb R_{\geq0}^n:\langle a,x\rangle=b\iff B[a,b]'\leq c$

satisfied?

I think there might be (perhaps every entry of $B,c$ can be computed in $O(\log n)$ time).

Let $$\langle a,x\rangle=b$$ be a linear constraint 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)$ bit length.

Is there a polyhedron $By\leq c$ (depending on $a,b$) 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|=O(n)$ ($O(n)$ bit length)
  3. $B,c$ constructible in $O(\log n)$ time in $poly(n)$ processors ($NC^1$ complexity)
  4. $\exists x\in\mathbb R_{\geq0}^n:\langle a,x\rangle=b\iff B[a,b]'\leq c$ or at least $B[a,b]'\leq c\implies \exists x\in\mathbb R_{\geq0}^n:\langle a,x\rangle=b$

satisfied?

I think there might be (perhaps every entry of $B,c$ can be computed in $O(\log n)$ time).

edited title
Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Detecting non-negativity of a single constraint by polyhedral constraints - $II$ (parallel complexity)

added 148 characters in body
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading
Source Link
Turbo
  • 13.9k
  • 1
  • 27
  • 76
Loading