If a decision problem is in $P$, must finding the solution be possible in polynomial-time?


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?