<p>Do we happen to know of any promise problems where the problem is both conditionally hard (say, NP-hard) while simultaneously being able to certify that the instance satisfies the given promise?</p>
<p>For example, in the case of Unique-SAT, we have some form of NP-hardness under randomized reductions (by the Valiant-Vazirani theorem), but there does not seem to be a way or certifying the promise of the instance (namely, that the input formula has at most one satisfying assignment). I have heard that some promise problems in lattice-based cryptography admit certificates that guarantee the promise holds, but NP-hardness of the problem is not known.</p>
<p>Is there any problem satisfying these two conditions? Is there a good reason why these should not exist? I could imagine that, in the presence of the certificate that guarantees the promise, the problem might no longer be hard because we can extract some valuable information from the certificate, but note that I don’t want the certificate to be handed in together with the instance, I just want the certificate to exist.</p>
<p><strong>EDIT</strong>: Thanks to the comment below I realized that in fact my question was imprecise. It forgot to add that both sides of the promise should themselves be certifiable.</p>
<p>That is, I am interested in NP problems <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, possibly with <span class="math-container">$A \cap B \neq \emptyset$</span>, but where the promise guarantees that an instance <span class="math-container">$x$</span> does not belong to both at the same time, and the task is to decide whether <span class="math-container">$x$</span> is in <span class="math-container">$A$</span> or in <span class="math-container">$B$</span>. So there should be three types of certificates:</p>
<ol>
<li>for a given promise instance <span class="math-container">$x$</span>, it must be possible to certify that <span class="math-container">$x$</span> does not belong to both <span class="math-container">$A$</span> and <span class="math-container">$B$</span> simultaneously; this certificate should be some additional object, possibly hard to find;</li>
<li>if <span class="math-container">$x$</span> is in <span class="math-container">$A
$</span>, this is certifiable because <span class="math-container">$A$</span> is in NP;</li>
<li>similarly, if <span class="math-container">$x$</span> is in <span class="math-container">$B$</span>, this is again certifiable because <span class="math-container">$B$</span> is in NP.</li>
</ol>
<p>And, on top of this, the promise problem of distinguishing <span class="math-container">$A$</span> from <span class="math-container">$B$</span> under the disjointness promise should still be hard. So, in particular, one cannot take <span class="math-container">$A$</span> and <span class="math-container">$\bar A$</span>, because then <span class="math-container">$A$</span> is both in NP and coNP and thus it's unlikely to be NP-hard.</p>

CC BY-SA 4.0
2023-09-27T13:32:01.633Z
What about NP-complete problems with trivial promises? "SAT where the input isn't all 0s." Conditionally hard, easy promise, right?
Jake
CC BY-SA 4.0
2023-09-27T14:58:30.650Z
If the promise is poly-time verifiable, then the promise problem is equivalent to an ordinary decision problem (that is, you no longer need it to be a promise problem). That decision problem could still be hard ofc. Eg even normal 3SAT can be viewed this way, w the easily verifiable promise that the input is a well-formed 3cnf formula. We talk about promise problems in the first place precisely bc the promises are hard to verify.
Joshua Grochow
CC BY-SA 4.0
2023-09-27T15:01:32.250Z
@Jake My question was incomplete, your comment made me realize it. Your example does answer my original post, but it's not what I was interested in, sorry for the confusion :) I edited it now.
Noel Arteche
CC BY-SA 4.0
2023-09-27T15:05:30.407Z
@JoshuaGrochow I only require the promise to be poly-time verifiable in the presence of some additional certificate. I basically want some short certificate that, together with the input, can be checked easily to confirm the promise holds. This certificate itself might be hard to find, and I don't expect the promise instance to come with the certificate.
Noel Arteche
CC BY-SA 4.0
2023-09-27T15:11:42.220Z
In the formulation after the edit, the promise problem is actually $(A\let\bez\smallsetminus\bez B,B\bez A)$. Since the assumptions ensure that $A\bez B=A\bez(A\cap B)$ is in NP, and likewise for $B\bez A$, you might as well replace $A$ and $B$ with $A\bez B$ and $B\bez A$, i.e., assume that $A$ and $B$ are disjoint. So, you are really asking if there exists “hard” disjoint NP-pairs. We expect that they do, in the sense that e.g. there should exist disjoint NP-pairs that cannot be separated by subexponential-size circuits, but there likely do not exist *NP-hard* pairs. In fact, it seems  ...
Emil Jeřábek
CC BY-SA 4.0
2023-09-27T15:13:01.267Z
... that there do not exist complete disjoint NP-pairs under the natural notion of many-one polynomial-time reduction between such pairs.
Emil Jeřábek
CC BY-SA 4.0
2023-09-27T15:17:40.547Z
See https://arxiv.org/abs/1601.01487 for some connections.
Emil Jeřábek
CC BY-SA 4.0
2023-09-27T15:27:13.417Z
Thanks @EmilJeřábek, this is very helpful! I think this is exactly what I was looking for (though I hope the answer would be positive...) I will have a look at the paper.
Noel Arteche
<np-hardness><sat><lattice><unique-solution>
Certifying the promise in hard promise problems
Noel Arteche
# Certifying the promise in hard promise problems

(Asked by: username_0 on 2023-09-27)

Do we happen to know of any promise problems where the problem is both conditionally hard (say, NP-hard) while simultaneously being able to certify that the instance satisfies the given promise?

For example, in the case of Unique-SAT, we have some form of NP-hardness under randomized reductions (by the Valiant-Vazirani theorem), but there does not seem to be a way or certifying the promise of the instance (namely, that the input formula has at most one satisfying assignment). I have heard that some promise problems in lattice-based cryptography admit certificates that guarantee the promise holds, but NP-hardness of the problem is not known.

Is there any problem satisfying these two conditions? Is there a good reason why these should not exist? I could imagine that, in the presence of the certificate that guarantees the promise, the problem might no longer be hard because we can extract some valuable information from the certificate, but note that I don’t want the certificate to be handed in together with the instance, I just want the certificate to exist.

**EDIT**: Thanks to the comment below I realized that in fact my question was imprecise. It forgot to add that both sides of the promise should themselves be certifiable.

That is, I am interested in NP problems $A$ and $B$, possibly with $A \cap B \neq \emptyset$, but where the promise guarantees that an instance $x$ does not belong to both at the same time, and the task is to decide whether $x$ is in $A$ or in $B$. So there should be three types of certificates:

1. for a given promise instance $x$, it must be possible to certify that $x$ does not belong to both $A$ and $B$ simultaneously; this certificate should be some additional object, possibly hard to find;
2. if $x$ is in $A
   $, this is certifiable because $A$ is in NP;
3. similarly, if $x$ is in $B$, this is again certifiable because $B$ is in NP.

And, on top of this, the promise problem of distinguishing $A$ from $B$ under the disjointness promise should still be hard. So, in particular, one cannot take $A$ and $\bar A$, because then $A$ is both in NP and coNP and thus it's unlikely to be NP-hard.

**Tags:** np-hardness, sat, lattice, unique-solution
> **Comments:**
> **username_1**: What about NP-complete problems with trivial promises? "SAT where the input isn't all 0s." Conditionally hard, easy promise, right?  
> **username_2**: If the promise is poly-time verifiable, then the promise problem is equivalent to an ordinary decision problem (that is, you no longer need it to be a promise problem). That decision problem could still be hard ofc. Eg even normal 3SAT can be viewed this way, w the easily verifiable promise that the input is a well-formed 3cnf formula. We talk about promise problems in the first place precisely bc the promises are hard to verify.  
> **username_0**: @Jake My question was incomplete, your comment made me realize it. Your example does answer my original post, but it's not what I was interested in, sorry for the confusion :) I edited it now.  
> **username_0**: @JoshuaGrochow I only require the promise to be poly-time verifiable in the presence of some additional certificate. I basically want some short certificate that, together with the input, can be checked easily to confirm the promise holds. This certificate itself might be hard to find, and I don't expect the promise instance to come with the certificate.  
> **username_3**: In the formulation after the edit, the promise problem is actually $(A\let\bez\smallsetminus\bez B,B\bez A)$. Since the assumptions ensure that $A\bez B=A\bez(A\cap B)$ is in NP, and likewise for $B\bez A$, you might as well replace $A$ and $B$ with $A\bez B$ and $B\bez A$, i.e., assume that $A$ and $B$ are disjoint. So, you are really asking if there exists “hard” disjoint NP-pairs. We expect that they do, in the sense that e.g. there should exist disjoint NP-pairs that cannot be separated by subexponential-size circuits, but there likely do not exist *NP-hard* pairs. In fact, it seems  ...  
> **username_3**: ... that there do not exist complete disjoint NP-pairs under the natural notion of many-one polynomial-time reduction between such pairs.  
> **username_3**: See https://arxiv.org/abs/1601.01487 for some connections.  
> **username_0**: Thanks @EmilJeřábek, this is very helpful! I think this is exactly what I was looking for (though I hope the answer would be positive...) I will have a look at the paper.  

---

## 0 answers

