13
votes
Accepted
Is 2-SAT with XOR-relations NP-complete?
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 $...
- 7,833
11
votes
Accepted
Is weighted XOR-SAT NP-hard?
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 ...
- 269k
8
votes
Accepted
XOR two numbers
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 ...
- 269k
7
votes
Is 2-SAT with XOR-relations NP-complete?
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 ...
- 269k
7
votes
XOR two numbers
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}, \...
- 4,697
6
votes
Accepted
Minimum XOR for queries
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-...
- 474
6
votes
Accepted
Subset of numbers whose XOR has least Hamming weight
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, ...
- 269k
5
votes
Accepted
Can I use "XORing" in my thesis?
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'...
D.W.♦
- 140k
5
votes
Is 2-SAT with XOR-relations NP-complete?
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 $\...
D.W.♦
- 140k
4
votes
Is is possible to determine if a given number is xor combination of some numbers?
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 ...
- 269k
3
votes
Accepted
Can I simplify successive XOR operations?
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, ...
- 33k
3
votes
Find value of $a$ or $b$ of two XOR equations
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\,.$$
- 80.1k
3
votes
Is my simplified explaination of the XOR swap correct?
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} ...
- 269k
3
votes
Is my simplified explaination of the XOR swap correct?
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 ...
- 19.1k
2
votes
Express XOR with multiple inputs in zero-one integer linear programming (ILP)
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$$
$$...
D.W.♦
- 140k
2
votes
Accepted
Odd Parity Function
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$...
- 269k
2
votes
XOR two numbers
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.
- 80.1k
2
votes
Accepted
NP-complete language as a result of xoring two PTIME languages
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:
$$
\...
- 269k
2
votes
Path in a graph with a given xor of weights of edges
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$;...
D.W.♦
- 140k
2
votes
If XOR of n distinct numbers is ANDed over one of the number, the result would be zero
It doesn't work, for example if x2 = 0 then xoredResult & x2 = 0 all the time no matter what else the set of numbers ...
- 1,813
2
votes
find maximum sum of xors
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 ...
- 269k
2
votes
Coin flipping problem on an $n \times m$ grid
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 ...
- 269k
2
votes
Accepted
Is the bitwise-xor of a Uniform bit string and a non_uniform bit string Uniform?
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 ...
- 1,915
2
votes
Accepted
Where is the theory about "binary toggling games"?
"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} = [...
- 12.3k
1
vote
Accepted
Representing chained XOR operations as linear inequalities
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 ...
- 33k
1
vote
Accepted
Using Yao's principle to find a lower bound
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 ...
- 13.1k
1
vote
How many solutions are there for a XOR-SAT formula?
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.
...
- 1,081
1
vote
NP-complete language as a result of xoring two PTIME languages
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 ...
- 369
1
vote
Find number X by asking Hamming distance between X and Y in binary representation
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 ...
D.W.♦
- 140k
1
vote
XOR two numbers
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 ...
- 11
Only top scored, non community-wiki answers of a minimum length are eligible