Si un problema de decisión está en $ P $, ¿debe encontrar la solución posibles en el tiempo de polinomio?
-
29-09-2020 - |
Pregunta
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?
Solución
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).