<p>Given a random two-to-one function <span class="math-container">$f(x)$</span> from <span class="math-container">$n$</span> bits to <span class="math-container">$n$</span> bits, consider the following search problem:</p>
<ul>
<li>Find a polynomial number of pairs <span class="math-container">$(d,y)\in \{0,1\}^n\times\{0,1\}^n$</span> with <span class="math-container">$d\ne \bf 0$</span> such that, for each such pair, there exist preimages <span class="math-container">$(x_1,x_2)$</span> with <span class="math-container">$f(x_1)=f(x_2)=y$</span>, and also that <span class="math-container">$d\cdot(x_1\oplus x_2)=0$</span>.</li>
</ul>
<p>That is, <span class="math-container">$d$</span> encodes some information about the <span class="math-container">$\mathsf{XOR}$</span> of the two preimages of <span class="math-container">$y$</span>.  This is a search problem (the decision variant is always trivially true).  Randomly guessing a string <span class="math-container">$d$</span> without knowledge of <span class="math-container">$(x_1,x_2)$</span> succeeds generically only 50% of the time.</p>
<p>We may require an exponential number of queries to find colliding pairs <span class="math-container">$(x_1,x_2)$</span> in order to come up with a string <span class="math-container">$d$</span> orthogonal to the <span class="math-container">$\mathsf{XOR}$</span> of these preimages.  Furthermore a quantum computer can find such pairs <span class="math-container">$(d,y)$</span> easily with measurements in the Hadamard and computational bases (but the quantum computer cannot efficiently find <span class="math-container">$(x_1,x_2)$</span>, as this would violate the <a href="https://arxiv.org/abs/quant-ph/0111102" rel="nofollow noreferrer">collision lower bound</a>).</p>
<p>Efficient classical verification can be done with knowledge of <span class="math-container">$(x_1,x_2,d,y)$</span> but the problem as framed only asks for <span class="math-container">$(d,y)$</span>.  My question is, as framed, is this a proper <strong>NP-search</strong> problem?</p>
<p><strong>QUESTION</strong>  Is NP-search defined non-constructively?  That is, does the definition of NP-search merely require that there <em>exists</em> a witness that could efficiently verify the solution?  If so is the problem above a proper oracle separation for NP-search problems between BQP and BPP?  Or must an NP-search problem be defined to require actually finding the specific witness - e.g., all of <span class="math-container">$(x_1,x_2,d,y)$</span> and not just <span class="math-container">$(d,y)$</span> in the above problem?</p>

CC BY-SA 4.0
2022-09-26T04:16:56.530Z
https://en.wikipedia.org/wiki/NP_(complexity)#Verifier-based_definition, https://en.wikipedia.org/wiki/Search_problem, https://cs.stackexchange.com/q/105760/755
D.W.
CC BY-SA 4.0
2022-09-26T06:07:22.557Z
The definition of NP-search problems (https://en.wikipedia.org/wiki/FNP_(complexity)) requires that the solution can be verified in P, so no, what you wrote is not an NP-search problem.
Emil Jeřábek
CC BY-SA 4.0
2022-09-26T12:04:23.243Z
@EmilJeřábek thank you for your comment, and I believe you, but it’s not so clear in the links yet. At any rate *what kind of problem* is it to find $(d,y)$ without necessarily finding $(x_1,x_2)$ as well, if it’s not an NP-search problem?
Mark S
CC BY-SA 4.0
2022-09-26T12:42:56.227Z
It’s a projection of an NP-search problem. This class of problems does not have a generally accepted succinct name.
Emil Jeřábek
CC BY-SA 4.0
2022-09-26T13:13:03.260Z
@EmilJeřábek thanks! I understand and like that phrase. The NP certificate is all of $(x_1,x_2,d,y)$ but the problem only projects on to the last two coordinates $(d,y)$.
Mark S
<quantum-computing><np><search-problem><definitions>
Can an NP-search problem be defined non-constructively?
Mark S
# Can an NP-search problem be defined non-constructively?

(Asked by: username_0 on 2022-09-25)

Given a random two-to-one function $f(x)$ from $n$ bits to $n$ bits, consider the following search problem:

* Find a polynomial number of pairs $(d,y)\in \{0,1\}^n\times\{0,1\}^n$ with $d\ne \bf 0$ such that, for each such pair, there exist preimages $(x\_1,x\_2)$ with $f(x\_1)=f(x\_2)=y$, and also that $d\cdot(x\_1\oplus x\_2)=0$.

That is, $d$ encodes some information about the $\mathsf{XOR}$ of the two preimages of $y$. This is a search problem (the decision variant is always trivially true). Randomly guessing a string $d$ without knowledge of $(x\_1,x\_2)$ succeeds generically only 50% of the time.

We may require an exponential number of queries to find colliding pairs $(x\_1,x\_2)$ in order to come up with a string $d$ orthogonal to the $\mathsf{XOR}$ of these preimages. Furthermore a quantum computer can find such pairs $(d,y)$ easily with measurements in the Hadamard and computational bases (but the quantum computer cannot efficiently find $(x\_1,x\_2)$, as this would violate the [collision lower bound](https://arxiv.org/abs/quant-ph/0111102)).

Efficient classical verification can be done with knowledge of $(x\_1,x\_2,d,y)$ but the problem as framed only asks for $(d,y)$. My question is, as framed, is this a proper **NP-search** problem?

**QUESTION** Is NP-search defined non-constructively? That is, does the definition of NP-search merely require that there *exists* a witness that could efficiently verify the solution? If so is the problem above a proper oracle separation for NP-search problems between BQP and BPP? Or must an NP-search problem be defined to require actually finding the specific witness - e.g., all of $(x\_1,x\_2,d,y)$ and not just $(d,y)$ in the above problem?

**Tags:** quantum-computing, np, search-problem, definitions

> **Comments:**
> **username_1**: https://en.wikipedia.org/wiki/NP_(complexity)#Verifier-based_definition, https://en.wikipedia.org/wiki/Search_problem, https://cs.stackexchange.com/q/105760/755  
> **username_2**: The definition of NP-search problems (https://en.wikipedia.org/wiki/FNP_(complexity)) requires that the solution can be verified in P, so no, what you wrote is not an NP-search problem.  
> **username_0**: @EmilJeřábek thank you for your comment, and I believe you, but it’s not so clear in the links yet. At any rate *what kind of problem* is it to find $(d,y)$ without necessarily finding $(x_1,x_2)$ as well, if it’s not an NP-search problem?  
> **username_2**: It’s a projection of an NP-search problem. This class of problems does not have a generally accepted succinct name.  
> **username_0**: @EmilJeřábek thanks! I understand and like that phrase. The NP certificate is all of $(x_1,x_2,d,y)$ but the problem only projects on to the last two coordinates $(d,y)$.  

---

## 0 answers

