0
$\begingroup$

Does there exist an equation system with only linear equalities and inequalities and exhibits a NAND-like behavior? By 'NAND-like' I mean, among all the variables in the system there are 3 vars $x_1$, $x_2$, and $x_3$, such that all solutions with $x_3 = 0$ imply $x_1 = x_2 = 1$, and all solutions with $x_3 = 1$ can be classified into 3 categories, with each category receiving at least 1 solution:

  1. $x_1 = 1$, $x_2 = 0$

  2. $x_1 = 0$, $x_2 = 1$

  3. $x_1 = x_2 = 0$

Note: the converse does not need to be hold.

$\endgroup$
6
  • 2
    $\begingroup$ This question does not seem research level to me (see the FAQ). Besides, without context it's hard to guess why we should be bothered to solve this exercise or disprove the statement (no offense meant). $\endgroup$ Dec 12, 2013 at 12:38
  • $\begingroup$ If $x_i$ are not integers I suppose you can't do this (probably it would imply P=NP). $\endgroup$
    – joro
    Dec 12, 2013 at 13:00
  • $\begingroup$ All variables can be real numbers. $\endgroup$ Dec 12, 2013 at 13:43
  • 2
    $\begingroup$ If all variables are real and all (in)equations are linear then the set described by the system is convex. Then surely the condition $x_3=0\Rightarrow x_1=x_2=1$ is impossible since the solution set will contain the whole segment $[(0,0,0) , (1,1,0) ]$. $\endgroup$ Dec 12, 2013 at 14:09
  • 2
    $\begingroup$ Spending a few minutes more thought suggests the following: represent the NAND truth table as 4 points in R^3. The tetrahedron with those 4 vertices should meet your criteria, and also be the intersection of four half spaces. The four inequalities should be straightforward (one is x_3 <= 1), and I leave that to you. $\endgroup$ Dec 12, 2013 at 17:51

2 Answers 2

2
$\begingroup$

EDIT

In a comment the OP wants $x_i$ reals.

In this case I believe this is impossible with a linear system since almost sure it would imply $P=NP$.

In particular I believe one can't linearly encode $x_i \in \{0,1\}$ for $x_i$ real or rational.


EDIT 2

Due to discussion in comments, here is the explicit CNF: $$ ((x_1 \lor x_3) \land (x_2 \lor x_3) \land (\lnot x_1 \lor \lnot x_2 \lor \lnot x_3)) $$

Original answer for integers

If I understand correctly you want to work with variables $x_i \in \{0,1\}$ and the solutions of the system to be exactly the solutions to $x_3 := x_1 \; \rm{NAND} \; x_2 $

This is possible and one approach is first to convert the formula to Conjunctive Normal Form.

Then encode it to linear system:

Replace $\lnot x$ by $ 1-x$.

Encode each clause $ x_1 \lor x_2 \ldots \lor x_n$ as $ x_1 + x_2 \ldots +x_n >0 $

(taking into account the negation).

You get a system of inequalities containing $x_i$ and $ 1 - x_j$.

Will try to make explicit system.

$\endgroup$
7
  • $\begingroup$ I assume $x_i$ are integers and one can trivially force them in {0,1}. If they are not integers probably it can't be done since it probably would imply P=NP. $\endgroup$
    – joro
    Dec 12, 2013 at 13:36
  • $\begingroup$ Let's try again. First constrain the (integer) variables $x_1, x_2, x_3$ to lie in $\{0,1\}$. Let $y = x_1 + x_2$. Then $x_1 \land x_2 \iff y \geq 2$. So $x_1 \text{ NAND } x_2 \iff y < 2$. So it would suffice to have indicator variables for inequalities. I don't know how optimistic that is. $\endgroup$
    – Ben Barber
    Dec 12, 2013 at 13:48
  • $\begingroup$ @BenBarber It is certainly possible, not sure if yours is entirely correct. In a comment the OP wants $x_i$ reals. I suppose this makes the answer negative. $\endgroup$
    – joro
    Dec 12, 2013 at 13:50
  • $\begingroup$ @joro With integers only I'm not so sure if it is possible with a purely linear system (i.e. without nonlinear indicator functions and similar tools). $\endgroup$
    – Waldemar
    Dec 12, 2013 at 13:58
  • $\begingroup$ @Waldemar I am pretty sure, will try to make explicit solution. So you have the boolean OR,AND,NOT with inequalities and $1-$ which is certainly a basis. $\endgroup$
    – joro
    Dec 12, 2013 at 14:07
1
$\begingroup$

Try \begin{eqnarray*} x_3 & \leq & 1 \\ x_1 + x_3 & \geq & 1 \\ x_2 + x_3 & \geq & 1 \\ x_1 + x_2+ x_3 & \leq & 2. \end{eqnarray*}

$\endgroup$
1
  • $\begingroup$ I'm unsure about the categories part; you could use x_i > 1/2 or some related combination perhaps. $\endgroup$ Dec 12, 2013 at 18:27

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