6
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ What about NP-complete problems with trivial promises? "SAT where the input isn't all 0s." Conditionally hard, easy promise, right? $\endgroup$
    – Jake
    Commented Sep 27, 2023 at 13:32
  • 2
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Commented Sep 27, 2023 at 14:58
  • 3
    $\begingroup$ 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 ... $\endgroup$
    – Emil Jeřábek
    Commented Sep 27, 2023 at 15:11
  • 3
    $\begingroup$ ... that there do not exist complete disjoint NP-pairs under the natural notion of many-one polynomial-time reduction between such pairs. $\endgroup$
    – Emil Jeřábek
    Commented Sep 27, 2023 at 15:13
  • 3
    $\begingroup$ See arxiv.org/abs/1601.01487 for some connections. $\endgroup$
    – Emil Jeřábek
    Commented Sep 27, 2023 at 15:17

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.