Return to Answer

No, your argument is not correct. A possible value of $s$ is $0^n$ (indeed, the decision version of Simon's problem is to distinguish $s=0^n$ from $s\ne0^n$, hence thus value is important).

Thus, your algorithm must be ready to guess $0^n$ as a potential value of $s$. But as you can see, whenever the algorithm guesses $0^n$, it will always accept and output this value as $f(x)=f(x\oplus0^n)$ no matter what, even if the actual value of $s$ is different!

In order to positively verify the $s=0^n$ case, an NP machine has to certify that the function is one-to-one rather than two-to-one. It needs an exponential number of queries to do that.

More precisely, any NP machine solving the problem, or even just its decision version (with $s=0^n$ being the YES instances, and $s\ne0^n$ the NO instances), must make at least $2^{n/2}$ oracle queries. This can be proved by a simple adversary argument:

First, set the oracle to the identity function $f(x)=x$. Then the NP machine much accept and output $s=0^n$ on some computation path $P$.

Let $X\subseteq\{0,1\}^n$ be the set of oracle calls made on $P$, and assume for contradiction that $|X|<2^{n/2}$. Since there are $<2^n$ elements in the set $\{x\oplus y:x,y\in X\}$, we can choose $s\in\{0,1\}^n\smallsetminus X$. We define a new oracle $g$ as follows: for each pair of elements $\{x,x\oplus s\}$, we define $f(x)=f(x\oplus s)\in\{x,x\oplus s\}$ in some way, making sure that $f(x)=x$ for $x\in X$. (We can do that because by the choice of $s$, it cannot happen that both $x$ and $x\oplus s$ belong to $X$.)

Then if we run the machine with oracle $g$, $P$ is still an accepting path that outputs “$s=0^n$”, as $g\supseteq f\restriction X$; but this value is different from the actual $s$.

No, your argument is not correct. A possible value of $s$ is $0^n$ (indeed, the decision version of Simon's problem is to distinguish $s=0^n$ from $s\ne0^n$, hence thus value is important).

Thus, your algorithm must be ready to guess $0^n$ as a potential value of $s$. But as you can see, whenever the algorithm guesses $0^n$, it will always accept and output this value as $f(x)=f(x\oplus0^n)$ no matter what, even if the actual value of $s$ is different!

In order to positively verify the $s=0^n$ case, an NP machine has to certify that the function is one-to-one rather than two-to-one. It needs an exponential number of queries to do that.

More precisely, any nondeterministic machine solving the problem, or even just its decision version (with $s=0^n$ being the YES instances, and $s\ne0^n$ the NO instances), must make at least $2^{(n+1)/2}$ oracle queries. This can be proved by a simple adversary argument:

First, set the oracle to the identity function $f(x)=x$. Then the NP machine much accept and output $s=0^n$ on some computation path $P$.

Let $X\subseteq\{0,1\}^n$ be the set of oracle calls made on $P$, and assume for contradiction that $|X|<2^{(n+1)/2}$. Since there are $\le\binom{|X|}2+1\le|X|^2/2<2^n$ elements in the set $\{x\oplus y:x,y\in X\}$, we can choose $s\in\{0,1\}^n\smallsetminus X$. We define a new oracle $g$ as follows: for each pair of elements $\{x,x\oplus s\}$, we define $f(x)=f(x\oplus s)\in\{x,x\oplus s\}$ in some way, making sure that $f(x)=x$ for $x\in X$. (We can do that because by the choice of $s$, it cannot happen that both $x$ and $x\oplus s$ belong to $X$.)

Then if we run the machine with oracle $g$, $P$ is still an accepting path that outputs “$s=0^n$”, as $g\supseteq f\restriction X$; but this value is different from the actual $s$.

On the other hand, it is possible to solve the problem even deterministically using $O(2^{n/2})$ oracle queries (and overall running time $2^{n/2}n^{O(1)}$). The algorithm is as follows:

• Query $f(x)$ for all $x$ in the sets $X=\{0,1\}^{\lfloor n/2\rfloor}\times\{0\}^{\lceil n/2\rceil}$ and $Y=\{0\}^{\lfloor n/2\rfloor}\times\{0,1\}^{\lceil n/2\rceil}$.

• If $f(x)=f(y)$ for some $x\in X$ and $y\in Y$ other than $x=y=0^n$, then output $s=x\oplus y\ne0^n$.

• Otherwise, output $s=0^n$.

No, your argument is not correct. A possible value of $s$ is $0^n$ (indeed, the decision version of Simon's problem is to distinguish $s=0^n$ from $s\ne0^n$, hence thus value is important).

Thus, your algorithm must be ready to guess $0^n$ as a potential value of $s$. But as you can see, whenever the algorithm guesses $0^n$, it will always accept and output this value as $f(x)=f(x\oplus0^n)$ no matter what, even if the actual value of $s$ is different!

In order to positively verify the $s=0^n$ case, an NP machine has to certify that the function is one-to-one rather than two-to-one. It needs an exponential number of queries to do that.

More precisely, any NP machine solving the problem, or even just its decision version, must make at least $2^{n/2}$ oracle queries. This can be proved by a simple adversary argument:

First, set the oracle to the identity function $f(x)=x$. Then the NP machine much accept and output $s=0^n$ on some computation path $P$.

Let $X\subseteq\{0,1\}^n$ be the set of oracle calls made on $P$, and assume for contradiction that $|X|<2^{n/2}$. Since there are $<2^n$ elements in the set $\{x\oplus y:x,y\in X\}$, we can choose $s\in\{0,1\}^n\smallsetminus X$. We define a new oracle $g$ as follows: for each pair of elements $\{x,x\oplus s\}$, we define $f(x)=f(x\oplus s)\in\{x,x\oplus s\}$ in some way, making sure that $f(x)=x$ for $x\in X$. (We can do that because by the choice of $s$, it cannot happen that both $x$ and $x\oplus s$ belong to $X$.)

Then if we run the machine with oracle $g$, $P$ is still an accepting path that outputs “$s=0^n$”, as $g\supseteq f\restriction X$; but this value is different from the actual $s$.

No, your argument is not correct. A possible value of $s$ is $0^n$ (indeed, the decision version of Simon's problem is to distinguish $s=0^n$ from $s\ne0^n$, hence thus value is important).

Thus, your algorithm must be ready to guess $0^n$ as a potential value of $s$. But as you can see, whenever the algorithm guesses $0^n$, it will always accept and output this value as $f(x)=f(x\oplus0^n)$ no matter what, even if the actual value of $s$ is different!

In order to positively verify the $s=0^n$ case, an NP machine has to certify that the function is one-to-one rather than two-to-one. It needs an exponential number of queries to do that.

More precisely, any NP machine solving the problem, or even just its decision version (with $s=0^n$ being the YES instances, and $s\ne0^n$ the NO instances), must make at least $2^{n/2}$ oracle queries. This can be proved by a simple adversary argument:

First, set the oracle to the identity function $f(x)=x$. Then the NP machine much accept and output $s=0^n$ on some computation path $P$.

Let $X\subseteq\{0,1\}^n$ be the set of oracle calls made on $P$, and assume for contradiction that $|X|<2^{n/2}$. Since there are $<2^n$ elements in the set $\{x\oplus y:x,y\in X\}$, we can choose $s\in\{0,1\}^n\smallsetminus X$. We define a new oracle $g$ as follows: for each pair of elements $\{x,x\oplus s\}$, we define $f(x)=f(x\oplus s)\in\{x,x\oplus s\}$ in some way, making sure that $f(x)=x$ for $x\in X$. (We can do that because by the choice of $s$, it cannot happen that both $x$ and $x\oplus s$ belong to $X$.)

Then if we run the machine with oracle $g$, $P$ is still an accepting path that outputs “$s=0^n$”, as $g\supseteq f\restriction X$; but this value is different from the actual $s$.

No, your argument is not correct. A possible value of $s$ is $0^n$ (indeed, the decision version of Simon's problem is to distinguish $s=0^n$ from $s\ne0^n$, hence thus value is important).

Thus, your algorithm must be ready to guess $0^n$ as a potential value of $s$. But as you can see, whenever the algorithm guesses $0^n$, it will always accept and output this value as $f(x)=f(x\oplus0^n)$ no matter what, even if the actual value of $s$ is different!

In order to positively verify the $s=0^n$ case, an NP machine has to certify that the function is one-to-one rather than two-to-one. I'm pretty sure it needs an exponential number of queries to do that.

No, your argument is not correct. A possible value of $s$ is $0^n$ (indeed, the decision version of Simon's problem is to distinguish $s=0^n$ from $s\ne0^n$, hence thus value is important).

Thus, your algorithm must be ready to guess $0^n$ as a potential value of $s$. But as you can see, whenever the algorithm guesses $0^n$, it will always accept and output this value as $f(x)=f(x\oplus0^n)$ no matter what, even if the actual value of $s$ is different!

In order to positively verify the $s=0^n$ case, an NP machine has to certify that the function is one-to-one rather than two-to-one. It needs an exponential number of queries to do that.

More precisely, any NP machine solving the problem, or even just its decision version, must make at least $2^{n/2}$ oracle queries. This can be proved by a simple adversary argument:

First, set the oracle to the identity function $f(x)=x$. Then the NP machine much accept and output $s=0^n$ on some computation path $P$.

Let $X\subseteq\{0,1\}^n$ be the set of oracle calls made on $P$, and assume for contradiction that $|X|<2^{n/2}$. Since there are $<2^n$ elements in the set $\{x\oplus y:x,y\in X\}$, we can choose $s\in\{0,1\}^n\smallsetminus X$. We define a new oracle $g$ as follows: for each pair of elements $\{x,x\oplus s\}$, we define $f(x)=f(x\oplus s)\in\{x,x\oplus s\}$ in some way, making sure that $f(x)=x$ for $x\in X$. (We can do that because by the choice of $s$, it cannot happen that both $x$ and $x\oplus s$ belong to $X$.)

Then if we run the machine with oracle $g$, $P$ is still an accepting path that outputs “$s=0^n$”, as $g\supseteq f\restriction X$; but this value is different from the actual $s$.