Que eu possa verificar soluções para o meu problema em tempo polinomial, como um não-determinístico algoritmo de chegar a uma solução, se ela sempre leva us $2^n$ bits?

Question

Problema De Decisão:Dado inteiros como insumos para $K$ e $M$.É a soma de $2^k$ + $M$ um $primeiro -$?

O verificador de

m = int(input('Enter integer for M: '))
sum_of_2**K+M=int(input('enter the sum of 2^k+m: '))

if AKS.sum_of_2**K+M == True:

  # Powers of 2 can be verified in O(N) time
  # make sure there is all 0-bits after the 1st ONE-bit
  
  # Use difference to verify problem

  if sum_of_2**K+M - (M) is a power_of_2:
    OUTPUT Solution Verified

As potências de 2 aproximadamente $2^n$ dígitos.Considere $2^k$ onde $K$ = 100000.Comparar a quantidade de dígitos $K$ para a quantidade de dígitos é a solução! Também tome nota de que a potências de 2 tem $2^n$ bits como o seu 0 bit Unário essencialmente para o expoente $n$.

Pergunta

Como seria um não-determinista da máquina de resolver este problema em tempo polinomial?

Answer 1

O verificador polinomial em K e M.É mesmo polinˆ omio em K e o tamanho M.Mas isso não é o que contam como "P".Ele teria que ser polinomial no tamanho de K e o tamanho M.Se K = 100,000 em seguida, o tamanho de K é de apenas 17 bits.É altamente improvável que qualquer algoritmo pode verificar a primalidade em tempo polinomial neste número, nem mesmo se M=-1, onde temos muito mais rápido do polinˆ omio em K algoritmo.

Não é provado ser impossível, mas muito, muito improvável.Mesmo se eu lhe dei um 50.000 pouco divisor de seu 100,000 número de bits, você não pôde verificar de que forma suficientemente rápida.

Answer 2

A meu ver, este problema de decisão é, obviamente, P.Portanto, não há nada para máquina de Turing não determinística para adivinhar.Máquina de Turing não determinística seria chamada verificador polinomial para um problema dado instância e que o problema seria resolvido em tempo polinomial.