Skip to main content
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Source Link
aksd
  • 3
  • 1

If P = NP, then is NP = FNP?

I read

FP = FNP iff P = NP

which makes sense.

But if P = NP, does it mean FNP = NP?

Intuitively, I think no because P = NP would mean that decision problems in NP would become decision problems in P. But I don't see how that would reduce search problems to decision problems.