Hot answers tagged

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 $...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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}, \...
user avatar
  • 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-...
user avatar
  • 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, ...
user avatar
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'...
user avatar
  • 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 $\...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
  • 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\,.$$
user avatar
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} ...
user avatar
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 ...
user avatar
  • 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$$ $$...
user avatar
  • 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$...
user avatar
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.
user avatar
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: $$ \...
user avatar
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$;...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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} = [...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible