Is there a FNP problem that's NP-hard but not FNP-hard? For the reductions, choose a class C such that [it's clear what FC means]

and FC is not known to be able to solve the satisfaction search problem,

and assume that FC indeed can't solve that search problem.



With the following definitions of hardness for FNP problems R,

NP-hard ​ ​ - ​ ​ The corresponding decision problem is NP-hard (with respect to C reductions).

FNP-hard ​ ​ - ​ ​ There is a C reduction f from satisfiability to the corresponding decision problem

and a function g in FC such that for all instances x of the satisfiability problem,

for all strings y, if ​ f(x) R y ​ then g(x,y) is a satisfying assignment to x.

is there a FNP problem that's NP-hard but not FNP-hard?
I'm going to argue that the answer is probably "Yes", i.e.,

there probably are FNP problems that are NP-hard but not FNP-hard.

Warmup: ​ With respect to polynomially-closed reduction classes that can't solve all of FNPSPACE, FNPSPACE-hardness is different from NPSPACE-hardness.

Proof: ​ ​ ​ ​ ​ ​ ​ Let R be the relation given by xRy if and only if [x$\in$QBF$\hspace{.02 in}$ and y is the empty string].

QBF $\in$ PSPACE-complete $=$ NPSPACE-complete , ​ so R is in FNPSPACE and NPSPACE-hard.

Let f and g form an arbitrary reduction from an arbitrary

relation S to R, and let x be an arbitrary instance of S.

x has an S-witness ​ $\implies$ ​ f(x) has an R-witness ​ $\implies$

f(x) R empty_string ​ $\implies$ ​ x S g(x,empty_string) ​ .

In other words, an arbitrary reduction from a search problem to R can be used

to solve the search problem. ​ ​ ​ Therefore R is not FNPSPACE-hard with respect

to polynomially-closed reduction classes that can't solve all of FNPSPACE.

Cryptographic Assumptions and sub-P reductions:

For each positive integer j, let R$\hspace{.02 in}$j be the relation given by ​ x R (C,v) ​ if and only if C is a circuit

and x is a CNF-SAT instace and ​ size(C) ≤ (number_of_variables_in_(x))$\hspace{.03 in}$j ​ and C(v) satisfies x. ​ ​ ​ Obviously, each R$\hspace{.02 in}$j is in FNP and NP-hard. ​ ​ ​ If they are all FNP-hard under non-uniform parallelizable reductions, then there can't even be a version of time-lock puzzles against

non-uniform adversaries that is otherwise very weak, namely, ones in which [the size of the

puzzle can be polynomial in the time for an honest user to solve it] and [there is no restriction

on the resources needed to create the puzzle] and [security only needs to hold infinitely often]. ​ Furthermore, if there are efficiently-computable functions that are one-way against probabilistic

parallel adversaries then one can replace both instances of "non-uniform" with "probabilistic". 

Probabilistic Polynomial-Time Reductions and handwaving:

(This is essentially tautological, but) If all NP-hard FNP problems are FNP-hard, then all

proof systems for SAT are "somewhat constructive", in the sense that any original instance can

be efficiently turned an equisatisfiable instance so that one will be able to go from any proof of

satisfiability of the equisatisfiable instance to a satisfying assignment of the original instance.

Non-interactive zaps are certainly not obviously "somewhat constructive" in that sense.