<p>Let <span class="math-container">$L$</span> be an NP complete language.  My loose intuition for completeness suggests that, at any point in a computation tableau for <span class="math-container">$L$</span>, either the computation has &quot;already done an NP complete amount of work&quot; or else it &quot;has an NP complete amount of work left to go.&quot;</p>
<p>To formalize this intuition, we can imagine a function <span class="math-container">$f(x)$</span> representing the information gathered at an intermediate point in the computation on input <span class="math-container">$x$</span>, and then say that either computing <span class="math-container">$f$</span> is NP complete, or else <span class="math-container">$L$</span> remains NP complete even when <span class="math-container">$f(x)$</span> is provided as a helpful extra part of the input.  More concretely:</p>
<blockquote>
<p><strong>Conjecture:</strong> Let <span class="math-container">$f$</span> be any function such that, on input <span class="math-container">$(x, y)$</span>, one can check whether <span class="math-container">$f(x) = y$</span> in polynomial time.  Then one of the following holds:</p>
<ol>
<li>Computing <span class="math-container">$f(x)$</span> is FNP complete, or</li>
<li>The following language <span class="math-container">$L'$</span> is NP complete: an input <span class="math-container">$(x, y)$</span> is a YES instance for <span class="math-container">$L'$</span> if <span class="math-container">$f(x)=y$</span> and also <span class="math-container">$x$</span> is a YES instance for <span class="math-container">$L$</span>; otherwise <span class="math-container">$(x, y)$</span> is a NO instance for <span class="math-container">$x'$</span>.</li>
</ol>
</blockquote>
<p>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.</p>

CC BY-SA 4.0
2022-06-06T19:48:36.497Z
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.
Geoffrey Irving
CC BY-SA 4.0
2022-06-07T00:20:04.590Z
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?
Ryan Williams
CC BY-SA 4.0
2022-06-11T15:08:10.100Z
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.
GMB
CC BY-SA 4.0
2022-06-11T15:10:12.293Z
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.
GMB
CC BY-SA 4.0
2022-06-26T23:07:53.757Z
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).
Kaveh
<cc.complexity-theory><np-complete>
Does NP Completeness always fall on one side or the other of an intermediate computation?
GMB
# Does NP Completeness always fall on one side or the other of an intermediate computation?

(Asked by: username_0 on 2022-06-06)

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.

**Tags:** cc.complexity-theory, np-complete
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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?  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_3**: 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).  

---

## 0 answers

