<p>Suppose you have <span class="math-container">$n$</span> switches lined up on a wall, labeled left to right from <span class="math-container">$1$</span> to <span class="math-container">$n$</span>. The switches are either <strong>on</strong> or <strong>off</strong>.<br />
You get a list of <span class="math-container">$q$</span> choices that must be made. A choice consist of two indices <span class="math-container">$i$</span> and <span class="math-container">$j$</span> and you must choose to flip either the switch labeled <span class="math-container">$i$</span> or <span class="math-container">$j$</span> but <strong>not</strong> both.<br />
The goal of the game is to have all switches turned off <strong>after all choices have been made</strong>, if possible.</p>
<p>I don't know if this game is already studied but I wrote an algorithm that solves it and it feels oddly familiar to 2SAT, so I was wondering if it is 2SAT in disguise or something else.</p>

CC BY-SA 4.0
2021-08-29T02:32:21.453Z
Seems to me that it reduces easily to solving a system of linear equations over Z mod 2.  Represent the $\ell$th choice as a pair $(i_\ell, j_\ell)$, with variables $X_\ell$ and $Y_\ell$, with equation $X_\ell + Y_\ell = 1$.  Then have a constraint for each switch $k$ that says $\sum_{\ell : i_\ell = k} X_\ell + \sum_{\ell : j_\ell=k} Y_\ell = 0$.  Then use, say, Gaussian elimination to solve the equations.  Perhaps you can also solve 2-SAT this way, although not in linear time as the standard algorithm does.  Is your algorithm a linear-time algorithm?
Neal Young
CC BY-SA 4.0
2021-08-29T05:13:18.263Z
@Neal Young yes my algorithm solves this in linear time.
Marc Grec
CC BY-SA 4.0
2021-08-29T12:26:05.380Z
How does it work?  Knowing that might help answer the question.
Neal Young
CC BY-SA 4.0
2021-08-29T15:27:45.803Z
@NealYoung To solve this problem you will need an undirected graph in which nodes and edges can store a bit. The nodes will represent switches and the bit stored in them will represent the state of the switch. The edges will represent choices and the bit stored in them will represent the state of the choice, the state of the choice is the conclusion of the choice, e.g. given the choice $(i, j)$ if $i$ is chosen then the bit is set to $0$, else it is set to $1$ . By flipping the state of a choice both switches change their states.
Marc Grec
CC BY-SA 4.0
2021-08-29T15:35:46.690Z
@NealYoung If we have two neighboring nodes with their bits set to $1$ then by flipping the state of the choice between them both of their bits get set to $0$. If we have two neighboring nodes one with the bit set to $0$ and the other with the bit set to $1$ then flipping the state of the choice between them will swap their bits. To finish solving this problem you can use a $BFS$ to get rid of all of the bits set to $1$, if there is an even number of such bits. After all bits are set to $0$ you can extract the state of the choices from the edges and there's the answer.
Marc Grec
CC BY-SA 4.0
2021-08-30T12:11:56.530Z
As Neal said, it looks more like XOR-SAT than 2-SAT: for each pair $p=(i,j)$, you have two variables $x_i^p$ and $x_j^p$ and a constraint $x_i^p \oplus y_j^p$. Moreover, for each switch $i$, you have a variable $s_i$ describing the state of the switch and the constraint $s_i = k_i \oplus \bigoplus_{p: i \in p} x_i^p$ where $k_i$ is the original state of the switch. And finally, constraint $\neg s_i$ for every $i$, saying that $s_i$ is turned off. As you can see, some clauses have more than 2 literals in it. They cannot be encoded with polysize 2-clauses, one should try another reduction.
holf
CC BY-SA 4.0
2021-08-30T13:00:30.673Z
Now if you consider a problem with pairs $(i,j_1) \dots (i, j_p)$, and switch $i$ is turned off. It can be turned off iff the number of switches $j_k$ turned off in the beginning is even (you cannot choose these switches so you have to choose $i$ and you need to switch it an even number of time to have it off in the end).  Thus, you need to encode a parity constraint. This is not possible with a polysize circuit of bounded depth. If you allow extra variables, this is not possible with a $2$-CNF (you could existentially eliminate the extra variables using Davis Putnam resolution).
holf
<gt.game-theory>
Is this "choose and switch" game just 2SAT in disguise?
Marc Grec
# Is this "choose and switch" game just 2SAT in disguise?

(Asked by: username_0 on 2021-08-28)

Suppose you have $n$ switches lined up on a wall, labeled left to right from $1$ to $n$. The switches are either **on** or **off**.  
You get a list of $q$ choices that must be made. A choice consist of two indices $i$ and $j$ and you must choose to flip either the switch labeled $i$ or $j$ but **not** both.  
The goal of the game is to have all switches turned off **after all choices have been made**, if possible.

I don't know if this game is already studied but I wrote an algorithm that solves it and it feels oddly familiar to 2SAT, so I was wondering if it is 2SAT in disguise or something else.

**Tags:** gt.game-theory

> **Comments:**
> **username_1**: Seems to me that it reduces easily to solving a system of linear equations over Z mod 2.  Represent the $\ell$th choice as a pair $(i_\ell, j_\ell)$, with variables $X_\ell$ and $Y_\ell$, with equation $X_\ell + Y_\ell = 1$.  Then have a constraint for each switch $k$ that says $\sum_{\ell : i_\ell = k} X_\ell + \sum_{\ell : j_\ell=k} Y_\ell = 0$.  Then use, say, Gaussian elimination to solve the equations.  Perhaps you can also solve 2-SAT this way, although not in linear time as the standard algorithm does.  Is your algorithm a linear-time algorithm?  
> **username_0**: @username_1 yes my algorithm solves this in linear time.  
> **username_1**: How does it work?  Knowing that might help answer the question.  
> **username_0**: @NealYoung To solve this problem you will need an undirected graph in which nodes and edges can store a bit. The nodes will represent switches and the bit stored in them will represent the state of the switch. The edges will represent choices and the bit stored in them will represent the state of the choice, the state of the choice is the conclusion of the choice, e.g. given the choice $(i, j)$ if $i$ is chosen then the bit is set to $0$, else it is set to $1$ . By flipping the state of a choice both switches change their states.  
> **username_0**: @NealYoung If we have two neighboring nodes with their bits set to $1$ then by flipping the state of the choice between them both of their bits get set to $0$. If we have two neighboring nodes one with the bit set to $0$ and the other with the bit set to $1$ then flipping the state of the choice between them will swap their bits. To finish solving this problem you can use a $BFS$ to get rid of all of the bits set to $1$, if there is an even number of such bits. After all bits are set to $0$ you can extract the state of the choices from the edges and there's the answer.  
> **username_2**: As Neal said, it looks more like XOR-SAT than 2-SAT: for each pair $p=(i,j)$, you have two variables $x_i^p$ and $x_j^p$ and a constraint $x_i^p \oplus y_j^p$. Moreover, for each switch $i$, you have a variable $s_i$ describing the state of the switch and the constraint $s_i = k_i \oplus \bigoplus_{p: i \in p} x_i^p$ where $k_i$ is the original state of the switch. And finally, constraint $\neg s_i$ for every $i$, saying that $s_i$ is turned off. As you can see, some clauses have more than 2 literals in it. They cannot be encoded with polysize 2-clauses, one should try another reduction.  
> **username_2**: Now if you consider a problem with pairs $(i,j_1) \dots (i, j_p)$, and switch $i$ is turned off. It can be turned off iff the number of switches $j_k$ turned off in the beginning is even (you cannot choose these switches so you have to choose $i$ and you need to switch it an even number of time to have it off in the end).  Thus, you need to encode a parity constraint. This is not possible with a polysize circuit of bounded depth. If you allow extra variables, this is not possible with a $2$-CNF (you could existentially eliminate the extra variables using Davis Putnam resolution).  

---

## 0 answers

