11
2-SAT-with-XOR-relations can be proven NP-complete by reduction from 3-SAT. Any 3-SAT clause $$(x_1 \lor x_2 \lor x_3)$$ can be rewritten into the equisatisfiable 2-SAT-with-XOR-relations expression $$(x_1 \lor \overline{y}) \land (y \oplus x_2 \oplus z) \land (\overline{z} \lor x_3)$$ with $y$ and $z$ as new variables.
9
A classical result of Berlekamp, McEliece, and van Tilborg shows that the following problem, maximum likelihood decoding, is NP-complete: given a matrix $A$ and a vector $b$ over $\mathbb{F}_2$, and an integer $w$, determine whether there is a solution to $Ax = b$ with Hamming weight at most $w$.
You can reduce this problem to your problem. The system $Ax = ...
8
Bitwise operations like (bitwise) AND, OR, and XOR don't make much sense from the perspective of decimal expansion. They do make some sense in bases which are powers of 2 like hexadecimal, since in such bases they also operate digit by digit.
7
You haven't specified the arity of your XOR relations, but like in the usual SAT-to-3SAT reduction, you can always arrange that their arity be at most 3. Now you are in great position to apply Schaefer's dichotomy theorem, which will tell you whether your problem is in P or NP-complete (these are the only two options). If it turns out to be in P, the next ...
6
Your problem is known as calculating the minimal distance of a (binary) linear code, and is NP-hard, as shown by Vardi. It is even NP-hard to approximate within any constant factor, as shown by Dumer, Miccancio and Sudan.
6
The most common definition of xor is $a\oplus b=(a+b)\bmod 2$, on vertices applied to every coordinate seperately of course. In base-10 case, you have to introduce two operations: $a\oplus b=(a+b)\bmod 10$ and $a\ominus b=(a-b)\bmod 10$. (Notice that in base-2 case they coincide). Now you have
$$c=a\ominus b \quad\text{for coding}\quad\text{and}\quad a=c\...
5
It seems to me that $a = a_i \oplus \dots \oplus a_n$ holds all necessary information: the $1$bits in $a$ are the bits you need to flip in (exactly) one of the $a_i$. As you are only allowed to add, you have to find one $a_i$ where the corresponding bit $j$ is $0$ and flip it -- this causes the same cost for all $a_i$, that is $2^j$, so the choice does not ...
5
By Schaefer's dichotomy theorem, this is NP-complete.
Consider the case where all clauses have 2 or 3 literals in them; then we can consider this as a constraint satisfaction problem over a set $\Gamma$ of relations of arity 3. In particular, the relations $R(x,y,z)$ are the following: $x \lor y$, $x \lor \neg y$, $\neg x \lor \neg y$, $x \oplus y \oplus z$...
5
There are only 16 distinct binary operations possible for $a$ op $b$, i.e., $0, 1, a, b, \overline{a}, \overline{b}, ab, a\overline{b}, \overline{a}b, \overline{a}\overline{b}, a+b, a+\overline{b}, \overline{a}+b, \overline{a}+\overline{b},ab+\overline{a}\overline{b}$ and $a\overline{b}+\overline{a}b$. XOR is $a\overline{b}+\overline{a}b$.
With decimal ...
5
Hint 1: Intuitively, $\oplus$ implies exactly one of the two inputs is $1$ ($B$ and $C$ here). Whereas, $(\bar{B}\bar{C} + BC)$ implies both inputs are $0$ or both are $1$.
Hint 2: Start from $\overline{(B \oplus C)}$, expand it, use De'Morgan's laws, simplify and you should reach $(\bar{B}\bar{C} + BC)$.
5
Consider the truth table for $(\overline{B}\overline{C}+BC)$. It has 1's exactly when $B$ and $C$ get the same value, which is exactly when $(B\oplus C)$ gets 0, hence, $\overline{B\oplus C}$ is equivalent to $(\overline{B}\overline{C}+BC)$.
5
Some useful guidelines for writing are:
Who is my audience?
Will my audience understand what I am writing?
Will my usage of language be distracting or otherwise take attention away from the message I'm trying to make?
In this case, your audience is probably another computer scientist who has at least some knowledge of your area. Therefore, yes, I would ...
4
Suppose that your numbers are $n$-bit long. Then you can think of them as elements of the vector space $\mathbb{F}_2^n$. The number $X$ can be written as an XOR of $a_1,\ldots,a_m$ if $X$ is in the linear span of $a_1,\ldots,a_m$. In order to determine whether $X$ is in the linear span of $a_1,\ldots,a_m$, you can use Gaussian elimination.
3
No. $a\oplus b = c$ and $c\oplus b = a$ are just rearrangements of the same equation, since
$$a\oplus b = c \iff (a\oplus b)\oplus b = c\oplus b\iff a=c\oplus b\,.$$
3
Let me mention a generalization of this algorithm, which works in any Abelian group:
$$
\begin{align*}
x_\text{temp} &= x_\text{in} + y_\text{in} \\
y_\text{out} &= x_\text{temp} - y_\text{in} \\
x_\text{out} &= x_\text{temp} - y_\text{out}
\end{align*}
$$
The proof is left to the reader. Your case corresponds to the group $\mathbb{Z}_2^n$, in ...
3
Your proof is correct in intention, but the style is not adequate.
Of course, there is no perfect style, and most of us could improve
their style, myself included.
Still, hoping readers will not be too harsh, here is an attempt at
writing it, as an example, following your own proof. It may be too
verbose, one of my own failings. (it is also a bit ...
2
Here is another way you could try. To express $y=x_1 \oplus x_2 \oplus \dots \oplus x_n$ (the exclusive-or of $x_1,\dots,x_n$), try the following constraints:
$$y = x_1 + x_2 + \dots + x_n - 2t$$
$$0 \le y \le 1$$
where $y$ and $t$ are constrained to be integers.
There are no guarantees this will work better than a sequence of 2-input xors or a tree of 2-...
2
Your question is addressed (for the parity of $n$ bits) by Troy Lee, who shows in his paper The formula size of PARITY that the (optimal) formula size (number of literals) of parity on $n = 2^\ell + k$ bits (where $0 \leq k < 2^\ell$) is $2^\ell (2^\ell + 3k)$. In your particular case, $\ell = k = 1$ and so the formula size is $10$, matching your formula, ...
2
No, there is no intuitive meaning in terms of decimal. Bitwise operations are defined (literally) as operations on bits, and bits don't correspond directly to decimal digits.
2
Arbitrary paths
If you want to know whether there exists a not-necessarily-simple path from $a$ to $b$ with weight $x$, here is a one-sided test:
Compute a cycle basis for the graph, $c_1,\dots,c_k$; this can be done in polynomial time. Let $p$ denote any simple path from $a$ to $b$. Let $W(p)$ denote its weight and $W(c_i)$ the weight of the cycle $c_i$....
2
This seems like a rather difficult question. Here is one approach.
Every 3CNF on $n$ variables can be encoded as a binary string of length $8n^3$ (how?). Consider the following two languages:
$$
\begin{align*}
L_1 &= \bigcup_{n=1}^\infty \{ xy0^{8n^3} : |x|=n, |y|=8n^3, \text{$x$ is an assignment satisfying the 3CNF $y$} \}, \\
L_2 &= \bigcup_{n=1}^\...
1
Yes, there are ways to improve the efficiency greatly.
Let ${}_k{i}$ be the $k$-th digit of $i$ in binary representation, i.e., it is 0 if $\lfloor i/2^k\rfloor$ is even and 1 otherwise. For example, since $19=(10011)_2$, $_019=1$, $_119=1$, $_219=0$, $_319=0$, $_419=1$. In most programming languages, ${}_k{i}$ can be computed as $(i\text{>>}k)\%2$.
...
1
Introducing another integer variable $t$, you can express the condition $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ as in the following canonical form.
$$x_1 + x_2 + \dots + x_n - 2t \le 1$$
$$- x_1 - x_2 - \dots - x_n + 2t \le -1$$
$$(x_1, x_2, \cdots, x_n) \le (1,1,\cdots,1)$$
$$(x_1, x_2, \cdots, x_n, t) \ge \mathbf 0$$
$$(x_1, x_2, \cdots, x_n, t) \in \...
1
Suppose that there exists a Las Vegas algorithm $A^f$ asking $q(n)=o\big(2^{n/2}\big)$ queries. Let $Q_f\subseteq\{0,1\}^n$ be the random variable which denotes the set of queries raised by the algorithm with oracle $f$.
Sample $f$ from the uniform distribution over the collection of all difference preserving functions, and choose $s\in\{0,1\}^n$ uniformly ...
1
The answer depends on the instance of the problem; For example;
$$(x_0 \oplus x_1) \wedge (x_0 \oplus \neg x_1)$$ has no solution at all.
However;
$$(x_0 \oplus x_1) \wedge (x_0 )$$ has solutions.
Finding the solutions, or the inconsistency is not that hard. You convert the problem into a linear system of equations as;
$$(x_0 + x_1) \equiv 1 \mod 2, \...
1
This is just linear algebra. Let $x$ be the vector over $\mathbb{Z}_2$ representing the initial state of the board, and let $y$ be the goal state of the board. Let $v_i$ be the vectors corresponding to the allowed flips (flipping corresponds to adding some $v_i$). Then we want to check whether $x+y$ is in the span of the $v_i$.
1
I have other idea, I am not sure if it is correct:
Let $k$ will be number of clauses and $n=5$ number of variables.
I reduce $3-$SAT problem, for each clause $c_i=(x_1, x_3, \neg x_5)$ I create language $$L_i= \{1\{0,1\}\{0,1\}\{0,1\}\{0,1\},\{0,1\}\{0,1\}1\{0,1\}\{0,1\}, \{0,1\}\{0,1\}\{0,1\}\{0,1\}0 \}$$
So $L_i$ contains patterns which satisfy $c_i$. Of ...
1
One reasonable heuristic would be to use a greedy algorithm, which at each step picks a query that is likely to reduce the space of possibilities as much as possible.
Suppose you care about the maximum number of questions (worst-case). Then I suggest the following strategy. At any point, you have a set $S$ of possible values of $X$ that remain. For each ...
1
XOR does have meaning on how decimal numbers are stored especially if you are considering using signed decimal notation. I think of XOR because it is useful in calculations requiring the 2's Complement.
You need to learn how negative numbers are stored in computers and also consider instances where Big Endian and Little Endian are used when testing your ...
1
The question there asks:
"If $f()$ is one way, is it true that $h(x_1,x_2)=f(x_1)\oplus f(x_2)$ is also one way."
This claim is incorrect. There exists some $f$ whose respective $h$ is not one way anymore.
However, the above doesn't apply to all $f$'s. It is possible that there exists some one-way $f$ whose respective $h$ remains one-way. But it needs ...
Only top voted, non community-wiki answers of a minimum length are eligible
