Se um problema de decisão está em $P$, encontrar a solução deve ser possível em tempo polinomial?
-
29-09-2020 - |
Pergunta
Função Problema que encontra a solução
Dado um número inteiro para $N$.
Encontrar $2$ inteiros distintos de $N$.(Mas, menos de $N$)
Que têm um produto igual a $N$.
Isso significa que devemos excluir inteiros $1$ e $N$.
Um algoritmo que é pseudo-polinomial
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
Saída
Soltuion Verified: 5 x 2 = N and N=10
O algoritmo que resolve o problema de decisão
if AKS-primality(N) == False:
OUTPUT YES
Pergunta
Como o problema de decisão está em $P$ encontrar uma solução também pode ser resolvido em tempo polinomial?
Solução
Não, e o exemplo que você lista é um exemplo clássico:tanto quanto sabemos, o factoring não parece estar em $P$, mas determinar se um número é primo está definitivamente em $P$.
Outro exemplo:Considere o jogo Feitiço.Considere o problema de decisão:dado $n$, determine se o primeiro jogador tem uma estratégia vencedora para Hex em um $n \vezes n$ quadro.Existe um problema de função correspondente:dado $n$, encontre essa estratégia vencedora.Bem, o problema de decisão é trivial (sabe-se que a resposta é sempre “sim”), mas acredita-se que o problema da função seja muito difícil (até onde sabemos).