8
$\begingroup$

Let $L$ be an NP complete language. My loose intuition for completeness suggests that, at any point in a computation tableau for $L$, either the computation has "already done an NP complete amount of work" or else it "has an NP complete amount of work left to go."

To formalize this intuition, we can imagine a function $f(x)$ representing the information gathered at an intermediate point in the computation on input $x$, and then say that either computing $f$ is NP complete, or else $L$ remains NP complete even when $f(x)$ is provided as a helpful extra part of the input. More concretely:

Conjecture: Let $f$ be any function such that, on input $(x, y)$, one can check whether $f(x) = y$ in polynomial time. Then one of the following holds:

  1. Computing $f(x)$ is FNP complete, or
  2. The following language $L'$ is NP complete: an input $(x, y)$ is a YES instance for $L'$ if $f(x)=y$ and also $x$ is a YES instance for $L$; otherwise $(x, y)$ is a NO instance for $x'$.

Is this known to be true or false? I would also be interested if it were known to be true or false in a certain relativized world.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ It seems like the answer should be no as stated, for the boring intuitive reason that you can hash the input to a bit and then either do useful computation in the first half or the second half, but I haven’t gone from there to a full argument. $\endgroup$
    – Geoffrey Irving
    Jun 6, 2022 at 19:48
  • 4
    $\begingroup$ Do you want an NP function f here, or an NP relation? There could be multiple accepting tableaus, of course. Also in the formal definition I'm not quite sure how L and f relate... L is an arbitrary NP problem? $\endgroup$
    – Ryan Williams
    Jun 7, 2022 at 0:20
  • $\begingroup$ I somehow missed these comments, apologies. I had not imagined a forced relationship between $L$ and $f$: I was thinking $L$ was an arbitrary NP complete language, and $f$ was an arbitrary function, and the stuff about the computation tableau was just motivation for why I thought this might be true. $\endgroup$
    – GMB
    Jun 11, 2022 at 15:08
  • $\begingroup$ I don't see the intution in the hashing example yet -- if $f$ is an NP intermediate inverted hash function, then my intuition is that its output is necessarily useless for $L$, and so $L$ would remain NP hard even when $f(x)$ is provided as "advice" as in the second suggested problem. $\endgroup$
    – GMB
    Jun 11, 2022 at 15:10
  • $\begingroup$ This feels similar to old concept of progress in circuit complexity and probably runs into similar issues (I guess that is what Geoffrey was referring to as well): if a circuit computes a difficult function, either left input comes from a difficult function or right one does, and repeating this we would think at some point we would find a gate which computes a difficult function but its children do not (since the input gates are easy). $\endgroup$
    – Kaveh
    Jun 26, 2022 at 23:07

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.