Le prove NP sono limitate alla lunghezza polinomiale?

Question

.

Nella teoria della complessità computazionale, NP (tempo polinomiale nonerministico) è una classe di complessità utilizzata per classificare i problemi decisionali.NP è l'insieme dei problemi decisionali per i quali le istanze del problema, in cui la risposta è "sì", avere prove verificabili in tempo polinomiale da una macchina deterministica di Turing.

Le prove per un problema decisionale NP sono verificate in tempo polinomiale.

implica che le prove sono alla maggior parte della lunghezza polinomiale?

"Bene, devi leggere l'intero ingresso. Se l'ingresso è più lungo del polinomiale, allora il tempo è maggiore del polinomio."

Il problema decisionale "è il primo bit dell'ingresso A 0?"può essere risolto in tempo e spazio costante - senza leggere l'intero ingresso.

Pertanto, forse un problema NP ha prove candidate che sono più lunghe della lunghezza polinomiale ma controllate in tempo polinomiale.

Answer 1

.

Il problema decisionale "è il primo bit dell'ingresso A 0?"può essere risolto in tempo e spazio costante - senza leggere l'intero ingresso.

Dato che una testa di macchina di Turing si muove a destra un passo in un momento, una testa della macchina di Turing può solo leggere una quantità polinomiale della prova in tempo polinomiale.

Mentre è possibile definire le prove per superare una lunghezza polinomiale, solo un prefisso polinomiale della prova potrebbe essere letta in tempo polinomiale, supponendo che la testa avvia alla cella 0 e può muoversi a max una cella a destra in un'unità di tempo.

Answer 2

Una prova di istanza "sì" significa fornire una soluzione.Fornire una soluzione fornisce un input valido.Per definizione, può essere verificato in tempo e spazio polinomiale relativamente all'ingresso, oppure non è un problema in NP.

Non è noto se tutte le prove di "no" istanze siano verificabili in tempo e spazio polinomiale (la differenza tra NP e Co-NP).

Per rispondere alla domanda con precisione, la prova di un'istanza "sì" è il valore di input.Non è possibile dire che l'ingresso ha una lunghezza polinomiale perché il polinomio viene utilizzato quando si confronta con la dimensione di ingresso.Quindi la domanda è priva di significato a causa della parola "polinomiale".Se vuoi veramente un polinomio da qualche parte, la dimensione della prova relativamente all'ingresso può essere definita come una funzione lineare f (x)= AX + B dove A= 1 e B= 0, che può essere semplificato su f (x)= x perché la dimensione dell'input è uguale a se stessa.