Si un problème de décision est en $ P $, il faut trouver la solution en polynôme?

Question

Problème de fonction qui trouve la solution

• donné entier pour N $ N $ .

• Recherche $ 2 $ nombres entiers distincts de $ n $ .(Mais, moins que $ n $ )

• qui a un produit égal à $ n $ .

Cela signifie que nous devons exclure les entiers 1 $ et $ n $

.

.

Un algorithme qui est 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

Sortie

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

L'algorithme qui résout le problème de décision

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

Question

Puisque le problème de décision est dans $ p $ doit trouver une solution également être solvable en polynôme-time?

Answer 1

non, et l'exemple que vous listez est un exemple classique: autant que nous sachons, l'affacturage ne semble pas être dans $ p $ , mais déterminer si unLe numéro est préféré est définitivement dans $ p $ .

Un autre exemple: Considérez le jeu HEX .Considérez le problème de décision: donné $ N $ , déterminez si le premier joueur a une stratégie gagnante pour hexagonale sur un $ N \Times N $ Board.Il existe un problème de fonction correspondant: donné $ N $ , trouve une stratégie gagnante.Eh bien, le problème de décision est trivial (on sait que la réponse est toujours "oui"), mais le problème de la fonction est considéré comme très difficile (autant que nous sachions).