World's most popular travel blog for travel bloggers.

[Solved]: If P = NP, then is NP = FNP?

, , No Comments
Problem Detail: 

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.

Asked By : Ashara

Answered By : D.W.

No, it doesn't mean that FNP = NP. NP is a class of decision problems; FNP is a class of function problems. See the definition of FNP (e.g., on Wikipedia, or in any textbook). Therefore, the elements of NP have a different type than the elements of FNP.

It's like asking whether the set of tart apples is equal to the set of seedless oranges; one is a set of apples, the other is a set of oranges, so they're certainly not equal, and you don't need to know anything about exactly which apples are tart or which oranges are seedless to know that.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback