2

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?

  • 1
    I am not sure about your notion of FNP-hardness. By standard definition, The search version of Satisfiability is FNP-complete. Hence, the NP-hardness of a decision problem implies the FNP-hardness of the corresponding search problem. – Mohammad Al-Turkistany Jan 15 '16 at 16:50
  • "The search version of Satisfiability is" also FNP-complete by my definition. ​ What is the standard definition of FNP-hardness? ​ ​ ​ ​ –  Jan 15 '16 at 16:53
  • See this: http://cstheory.stackexchange.com/a/1126/495 and this https://en.wikipedia.org/wiki/FNP_(complexity). "the FNP version of every NP-complete problem is NP-hard". – Mohammad Al-Turkistany Jan 15 '16 at 16:56
  • Those two links only show NP-hardness, not FNP-hardness. ​ (I also don't see a definition of the latter concept in either of those links.) ​ ​ ​ ​ –  Jan 15 '16 at 17:08
  • Aha, I got you. Under Karp reduction it is unknown. But, if you consider ASP-reductions (which require a bijection between solutions spaces of the two problems) then the answer is No to your question. – Mohammad Al-Turkistany Jan 15 '16 at 17:08
  • I'm not restricting to ASP reductions (unless your description is much stronger than their actual definition. ​ For example, SAT can easily have a unique solution, but NAE-SAT is NP-hard and can only have an even number of solutions.) ​ ​ ​ ​ –  Jan 15 '16 at 17:11
  • Here you find the definition of ASP reductions. http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/MasterThesis.pdf – Mohammad Al-Turkistany Jan 15 '16 at 17:18
  • I'm not sure, but this paper may be relevant http://eccc.hpi-web.de/report/2014/110/ – Igor Shinkar Feb 05 '16 at 21:38

1 Answers1

2

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.