News for hackers. Stuff that matters.
Re:Introduction to P vs. NP by thelastquestion on Friday March 24, 2023 @11:44AM (#35290603)
They can always be reduced, but sometimes with an unacceptably large (e.g., non-polynomial) increase in time complexity.

These are the complexity classes of Function P (FP) and Function NP (FNP), which are the function problem extensions of the decision problem classes, and require finding the value, not just answering yes or no.

A simple example of a decision problem in P but whose search problem is not known to be in FP: For a given integer x, “does there exist a non-trivial prime factor of x?” vs. “find a non-trivial prime factor of x”.

There are no comments on this comment yet.