Psedu-Polinomiale Tempo: conflitto con la definizione di dimensione input

Question

Da Wikipedia

Nella teoria della complessità computazionale, un algoritmo numerico è in corso pseudo-polinomiale Tempo se il suo tempo di esecuzione è un polinomio nella lunghezza dell'input (il numero di bit richiesti per rappresentarlo) e il valore numerico dell'input (il numero intero più grande presente nell'ingresso). In generale, il valore numerico dell'input è esponenziale nella lunghezza dell'input, motivo per cui a pseudo-polinomiale L'algoritmo temporale non funziona necessariamente in tempo polinomiale rispetto alla lunghezza di input.

Da questo Quindi post È stato molto utile.

Un algoritmo è in funzione pseudo-polinomiale Tempo se il runtime è un po 'polinomio nel valore numerico dell'input, piuttosto che nel numero di bit richiesti per rappresentarlo.

E questo Lezione MIT OCW Sul tempo di esecuzione DP e della definizione di tempo pseudo-polinomiale.

Stanno tutti parlando della stessa cosa in quanto un tempo di esecuzione è pseudo-polinomi quando è un polinomio multivariato di $ (x, k) $ dove $ x $ indica le dimensioni dell'input e $ k $ è un numero intero (numerico valore) coinvolto. Poiché $ k $ è spesso esponenziale in $ x $, il tempo pseudo-polinomiale non è necessariamente il tempo polinomiale in $ x $, il numero di bit necessari per rappresentare l'input. Matematicamente, $ k = theta (2^{x}) $, 2 è sostituibile da una costante.

Funziona assolutamente bene quando abbiamo un valore numerico $ k $ come input con tempo di esecuzione $ theta (k) $. Quindi $ x = theta ( log k) $ e abbiamo tempo di esecuzione $ theta (2^{x}) $. Tutto è pulito.

E poi inizio a vedere problemi più complicati in altri algoritmi. Ad esempio, nel caso dello zaino, lascia che $ n $ indichi il numero di cose o oggetti nell'input. Come descritto in Video MIT, l'input è $ x = theta (nlogs) $ e il tempo di esecuzione è $ theta (ns) $. L'istruttore descrive che poiché $ s $ è esponenziale nel Dimensione dell'input $ log s $ (il numero di bit necessari per rappresentare il valore numerico), possiamo vedere come il tempo di esecuzione dello zaino non è tempo polinomiale. $ log s $ fa solo una parte di $ x $, quindi non vedo come $ theta (n CDOT 2^{ log s}) $ è esponenziale in $ theta (n log s) $ . Come viene espresso il tempo di esecuzione nel modulo $ o (c^{x}) $ dove $ c $ è una costante?

Qualcosa di simile accade per il conteggio del tempo di esecuzione dell'ordinamento. Il Quindi post Dà tempo di esecuzione $ o (n + k) $. Dà la stessa logica di sopra per dire che il tempo di esecuzione è esponenziale nella dimensione input $ log k $. Ma per me sembra $ x = theta (n log k) $ poiché l'input è un elenco di $ n $ cose con il valore massimo $ k $. Non vedo davvero come $ o (n + k) $ possa essere esponenziale in $ x $ solo perché $ k $ è esponenziale nel numero di bit necessari per rappresentarlo, poiché $ log k $ non è sicuramente $ x $, solo una parte di esso. Stessa cosa: il tempo di esecuzione non sembra esponenziale in $ x $, piuttosto solo in $ log s $.

Quindi o non sto ancora ottenendo ciò che significa avere esponenziali "Lunghezza dell'input" è o c'è qualche conflitto con il modo in cui le persone definiscono Lunghezza dell'input. Il video MIT definisce la dimensione dell'input simile a come penso a $ x $ mentre molte altre fonti hanno un'opinione diversa. Lo vedo come il Numero totale di bit necessari per rappresentare l'intero input, ma alcune analisi lo vedono solo come il numero di bit necessari per rappresentare un valore numerico che è solo una parte dell'intero input. Il tempo di esecuzione è esponenziale nella dimensione dell'input se è esponenziale nella dimensione di una parte dell'input o del tutto ?? Si prega di precisare!!