# 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?