Ho un problema decisionale con certificati di $ 2 ^ N $ bit, come verificare il problema della mia decisione in modo efficiente se è in $ NP $?

Question

Problema decisionale: $ 2 ^ k $ + $ m $ un primo?

Gli ingressi per entrambi $ k $ e $ m $ sono solo numeri interi. La soluzione è la somma di $ 2 ^ k $ + $ m $ . ( Usa AKS per decidere Prime )

I poteri di 2 hanno circa $ 2 ^ n $ cifre. Considerare $ 2 ^ k $ dove $ k $ = 100000. Confronta la quantità di cifre in $ k $ alla quantità di cifre nella sua soluzione!

domanda

Vedere che il certificato del problema della decisione può essere $ 2 ^ N $ dimensionato, come verificare il problema della decisione in tempo polinomiale, considerando che posso solo guardare il Transizione afferma come un certificato in sé?

In altre parole, quale fosse un verificatore di tempo polinomiale per questo problema di decisione?

Answer 1

Un problema di decisione ha una risposta Sì / NO, quindi non può avere "dimensione esponenziale".Stai chiedendo problemi di ricerca, quelli possono certamente avere dimensioni esponenziali.E sì, se la dimensione della soluzione (scritta in un formato adeguatamente compatto, cioè) è esponenziale nella dimensione del problema originale, è chiaramente impossibile anche scrivere la risposta in tempo polinomiale.

In ogni caso, P e NP si applicano rigorosamente solo ai problemi decisionali.Ma dai un'occhiata a Berere's "Decisione vs Search" per arelazione tra entrambi.