If a decision problem is in $P$, must finding the solution be possible in polynomial-time?
-
29-09-2020 - |
Question
Function Problem that finds the solution
Given integer for $N$.
Find $2$ integers distinct from $N$. (But, less than $N$)
That have a product equal to $N$.
This means we must exclude integers $1$ and $N$.
An algorithm that is pseudo-polynomial
N = 10
numbers = []
for a in range(2, N):
numbers.append(a)
for j in range(length(numbers)):
if N/(numbers[j]) in numbers:
OUTPUT N/(numbers[j]) X numbers[j]
break
Output
Soltuion Verified: 5 x 2 = N and N=10
The algorithm that solves the Decision Problem
if AKS-primality(N) == False:
OUTPUT YES
Question
Since the decision problem is in $P$ must finding a solution also be solvable in polynomial-time?
Solution
No, and the example you list is a classic example: as far as we know, factoring does not appear to be in $P$, but determining whether a number is prime is definitely in $P$.
Another example: Consider the game Hex. Consider the decision problem: given $n$, determine whether the first player has a winning strategy for Hex on a $n \times n$ board. There is a corresponding function problem: given $n$, find such a winning strategy. Well, the decision problem is trivial (it is known that the answer is always "yes"), but the function problem is believed to be very hard (as far as we know).