Se um problema de decisão está em $P$, encontrar a solução deve ser possível em tempo polinomial?

Question

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?

Answer 1

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).