Timeline for Detecting non-negativity of a single constraint by polyhedral constraints - $I$
Current License: CC BY-SA 4.0
29 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 11, 2021 at 11:02 | vote | accept | Turbo | ||
| May 11, 2021 at 11:02 | |||||
| May 11, 2021 at 11:02 | vote | accept | Turbo | ||
| May 11, 2021 at 11:02 | |||||
| May 10, 2021 at 12:50 | answer | added | Dima Pasechnik | timeline score: 2 | |
| May 10, 2021 at 12:28 | comment | added | Turbo | @DimaPasechnik Updated further comments. | |
| May 10, 2021 at 12:27 | review | Close votes | |||
| May 25, 2021 at 3:06 | |||||
| May 10, 2021 at 12:19 | history | edited | Turbo | CC BY-SA 4.0 |
added 335 characters in body
|
| May 10, 2021 at 12:09 | comment | added | Turbo | @DimaPasechnik Sorry my mistake bitlength $m=O(1)$. I am considering the situation $Ax=b$ is constraint and $a[i]$ is $i$th row of $A\in\{0,1\}^{m\times n}$. Now instead of doing linear programming to check for an $x$ if we had $B,c$ we can directly decide if $x$ exists. If no $x$ exists $B[a[i],b_i]\leq c$ would not be satisfied at an $i\in\{1,\dots,m\}$ leading to decidability without knowing $x$. | |
| May 10, 2021 at 12:08 | comment | added | Dima Pasechnik | sorry, I still do not get it. Indeed, $a\geq 0$, $b\geq 0$ alone imply the existence of $x$, you do not need any B and c! | |
| May 10, 2021 at 12:02 | history | edited | Turbo | CC BY-SA 4.0 |
deleted 30 characters in body
|
| May 10, 2021 at 11:59 | comment | added | Dima Pasechnik | I'm not suggesting to compute $x$. I merely say that and $x$ will exist, given conditions on $a$ and $b$ in 3. Thus the LHS of 3. will follow from a triviality like $1\geq 0$. | |
| May 10, 2021 at 11:52 | history | edited | Turbo | CC BY-SA 4.0 |
added 7 characters in body
|
| May 10, 2021 at 11:45 | comment | added | Dima Pasechnik | for all $a$, $b$ in 3. an $x$ solving the equation exists. So your B and c are not needed. | |
| May 10, 2021 at 11:43 | history | edited | Turbo | CC BY-SA 4.0 |
added 6 characters in body
|
| May 10, 2021 at 11:40 | comment | added | Dima Pasechnik | Are the signs of $a$ and $b$ specified? If the are not, why do you specify them in your question? | |
| May 10, 2021 at 11:36 | history | edited | Turbo | CC BY-SA 4.0 |
added 67 characters in body
|
| May 10, 2021 at 10:23 | comment | added | Dima Pasechnik | Or you want to encode with $B$ and $c$ the formula "if $b\neq 0$ then there exists $k$ so that $ba_k> 0$ ? | |
| May 10, 2021 at 10:19 | comment | added | Dima Pasechnik | 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). | |
| May 9, 2021 at 5:33 | history | edited | Turbo | CC BY-SA 4.0 |
edited title
|
| May 9, 2021 at 5:20 | history | edited | Turbo | CC BY-SA 4.0 |
deleted 12 characters in body
|
| May 9, 2021 at 5:14 | history | edited | Turbo | CC BY-SA 4.0 |
added 15 characters in body
|
| May 8, 2021 at 23:29 | history | edited | Turbo | CC BY-SA 4.0 |
deleted 539 characters in body
|
| May 8, 2021 at 23:22 | history | edited | Turbo | CC BY-SA 4.0 |
added 80 characters in body
|
| May 8, 2021 at 23:15 | history | edited | Turbo | CC BY-SA 4.0 |
added 20 characters in body
|
| May 8, 2021 at 18:31 | comment | added | Dima Pasechnik | something akin to Farkas Lemma? | |
| May 8, 2021 at 11:46 | comment | added | Turbo | Polyhedra encodes certain 'iff' information and utilizing polyhedra could be interpreted as Presburger. | |
| May 8, 2021 at 11:35 | review | Suggested edits | |||
| May 8, 2021 at 11:44 | |||||
| May 8, 2021 at 11:34 | comment | added | provocateur | logic tag is definitely inappropriate. | |
| May 8, 2021 at 11:07 | history | edited | Turbo | CC BY-SA 4.0 |
deleted 5 characters in body
|
| May 8, 2021 at 11:01 | history | asked | Turbo | CC BY-SA 4.0 |