13
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 ...
7
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 ...
6
Using Trie Data Structure, you can solve this problem in $O(m + n)$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values).
Let say we know that all integers in $A$ are 32-bit values. Use the following steps:
Create an empty trie. Every node of trie may contains at most two children
for 0 and 1 bits.
Insert all values in $A$ into ...
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.
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 ...
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$...
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
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$.
...
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
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}^\...
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
It doesn't work, for example if x2 = 0 then xoredResult & x2 = 0 all the time no matter what else the set of numbers contains.
Or for an other example, the set { 1, 2, 3 } xors to zero (so it ANDed by any of its members, or even anything else, yields zero) but contains no repeated elements.
2
For every $i \in \{0,\ldots,n\}$ (where $n$ is the length of the array) and for every $a,b,c \in \{0,\ldots,15\}$, we determine whether it is possible to partition the first $i$ elements of the array into four subsets, the first three of which XOR to $a,b,c$, respectively. We also compute the XOR of the entire array. Using the information for $i = n$, we can ...
2
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$.
2
"Binary toggling games" are generally just arithmetic problems over GF(2).
Your particular problem is equivalent to the following over GF(2):
$$\sum_i V_iS_i = 1 + A_M $$
If we write $\vec{S} = [S_1, S_2, \dots]^T$ and $V = [V_1, V_2, \dots]^T$ we find that your problem is actually a simple matrix equation over GF(2):
$$V\vec{S} = 1 + A_M$$
You can ...
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
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
Yes, if $x$ and $y$ are chosen independently of each other.
One way to quickly see this is to note that the map $x \mapsto x \oplus y,$ for some constant $y,$ is a permutation of $\{0,1\}^n.$ This means that if $x$ is uniformly distributed over $\{0,1\}^n$ and $y$ is constant, then $x \oplus y$ is also uniformly distributed. And since $x \oplus y$ is ...
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
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
