0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ I got the idea from integer factorization. Finding a solution should run efficiently on a quantum computer. $\endgroup$
    – Dingle Berry
    Commented May 19, 2020 at 1:02
  • $\begingroup$ Suppose $f$ is some really-hard-to-compute total function and consider the decision problem "Is $x$ in the domain of $f$?" This is trivial - since $f$ is total, everything is in the domain of $f$. But actually finding $f(x)$ given $x$ may be extremely hard. $\endgroup$
    – Noah Schweber
    Commented May 19, 2020 at 1:03
  • $\begingroup$ @NoahSchweber Sure is counterintuitive. My intuition tells me that every function-variant of a decision problem (in $P$) must be in $FP$. For example, suppose factorization is in $P$ with a working algorithm, but no one has found out how to provide the factors. Very impractical and counter-intuitive. $\endgroup$
    – Dingle Berry
    Commented May 19, 2020 at 1:05

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$
5
  • $\begingroup$ So giving me the winning strategy would be hard? Then what's the point of "yes"?? Hmmm.. I wonder if I could reduce factorization into my function-problem in polynomial-time. But that would be another question for later. $\endgroup$
    – Dingle Berry
    Commented May 19, 2020 at 1:22
  • 1
    $\begingroup$ @DingleBerry "Then what's the point of "yes"?" Well, this is a situation where the result answers precisely the question that was asked. One can argue - at least in some situations - that the decision problem is not in fact the right thing to focus on. But it is still something we can look at, and is at the very least mathematically interesting. $\endgroup$
    – Noah Schweber
    Commented May 19, 2020 at 1:50
  • $\begingroup$ @NoahSchweber Just like with the example of providing a $P$ algorithm for Factorization that only says "YES" but never provides the factors necessary to beat some encryption scheme. Totally not interesting for cryptographers. $\endgroup$
    – Dingle Berry
    Commented May 19, 2020 at 2:04
  • $\begingroup$ @DingleBerry What's totally not interesting to one person may be extremely interesting to another. $\endgroup$
    – Noah Schweber
    Commented May 19, 2020 at 2:06
  • $\begingroup$ @NoahSchweber Well, at least RSA should be okay if someone ever comes up with $P$ algorithm that can't find the factors for integer factorization. $\endgroup$
    – Dingle Berry
    Commented May 19, 2020 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.