Si un problema de decisión está en $ P $, ¿debe encontrar la solución posibles en el tiempo de polinomio?

Question

problema de función que encuentra la solución

• Dado entero para $ n $ .

• Encuentre $ 2 $ enteros distintos de $ n $ .(Pero, menos de $ n $ )

• que tienen un producto igual a $ n $ .

Esto significa que debemos excluir los enteros $ 1 $ y $ n $ .

un algoritmo que es pseudo-polinomio

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

Salida

Soltuion Verified: 5 x 2 = N and N=10

El algoritmo que resuelve el problema de la decisión

if AKS-primality(N) == False:
  OUTPUT YES

Pregunta

Dado que el problema de la decisión está en $ p $ debe encontrar una solución también resolvible en polinomial-tiempo?

Answer 1

No, y el ejemplo que enumere es un ejemplo clásico: por lo que sabemos, la factorización no parece estar en $ p $ , pero determinar si unEl número es Prime está definitivamente en $ P $ .

Otro ejemplo: considere el juego hexagonal .Considere el problema de la decisión: Dado $ n $ , determine si el primer jugador tiene una estrategia ganadora para Hex en un $ n \veces n $ tablero.Hay un problema de función correspondiente: dado $ n $ , encuentra una estrategia tan ganadora.Bueno, el problema de la decisión es trivial (se sabe que la respuesta es siempre "Sí"), pero se cree que el problema de la función es muy difícil (por lo que sabemos).