Se un problema decisionale è in $ P $, deve trovare la soluzione essere possibile in tempo polinomiale?
-
29-09-2020 - |
Domanda
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?
Soluzione
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).