Se un problema decisionale è in $ P $, deve trovare la soluzione essere possibile in tempo polinomiale?

Question

Problema della funzione che trova la soluzione

.

• Dato Integer per $ N $ .

• Trova $ 2 $ I numeri interi distinti da $ N $ .(Ma, meno di $ N $ )

• che ha un prodotto uguale a $ N $ .

significa che dobbiamo escludere numeri interi $ 1 $ e $ n $ .

Un algoritmo che è pseudo-polinomiale

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

.

Uscita

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

.

L'algoritmo che risolve il problema decisione

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

.

domanda

Poiché il problema decisionale è in $ p $ deve trovare anche una soluzione essere solvibile anche in tempo polinomiale?

Answer 1

No, e l'esempio che elenchi è un classico esempio: per quanto ne sappiamo, il factoring non sembra essere in $ p $ , ma determinare se aIl numero è il primo è sicuramente in $ p $ .

Un altro esempio: considera il gioco hex .Considera il problema decisionale: data $ N $ , determinare se il primo giocatore ha una strategia vincente per esagono su un $ n \volte n $ scheda.Esiste un problema di funzione corrispondente: data $ N $ , trova una strategia così vincente.Bene, il problema decisionale è banale (è noto che la risposta è sempre "sì"), ma si ritiene che il problema della funzione sia molto difficile (per quanto ne sappiamo).