Problema NP

[pnp1]

Salve a tutti!

Su wikipedia, in questo articolo:
http://it.wikipedia.org/wiki/Classi_di_complessit%C3%A0_P_e_NP

è presente un esempio di problema che è NP, e di cui non si sa se sia in P.

Cito la fonte:

Dati due numeri grandi X e Y, potremmo chiederci se Y sia multiplo di un intero tra 1 e X, estremi esclusi. Per esempio potremmo chiederci se 69799 sia multiplo di un qualche intero tra 1 e 250. La risposta è SÌ, sebbene sia necessaria una discreta quantità di lavoro per scoprirlo a mano. D'altra parte, se qualcuno ci dicesse che la risposta è "SÌ, perché 223 è un divisore di 69799", allora potremo velocemente verificare questo fatto con un'unica divisione. Verificare che un numero è un divisore di un altro è molto più semplice che trovare il divisore stesso partendo da zero. L'informazione necessaria a verificare una risposta positiva è anche chiamata certificato. Concludiamo così che dati i certificati giusti, le risposte positive ai nostri problemi possono essere verificate velocemente (cioè in tempo polinomiale) e questo è il motivo per cui il problema è in NP. Non è noto se questo problema è in P. Il caso particolare in cui X=Y è stato dimostrato essere in P nel 2002.

Ora, io non sono un grande esperto di complessità e probabilmente sbaglio io, ma a me sembra proprio che il problema descritto sia in P.

Infatti questo semplice algoritmo mi pare lo risolva:

alg(X, Y):
	for i = 2 to X - 1 do
		if Y mod i = 0 then return Yes
	end for
	return No
end

la complessità di questo algoritmo dovrebbe essere O(X) * (complessita di Y mod i).
la complessità di Y mod i dovrebbe essere quadratica nella dimensione di Y e i, quindi complessivamente l'algoritmo dovrebbe avere costo polinomiale.

Sbaglio io o è sbagliato l'articolo di wikipedia?

[Deckard1]

Se n è la dimensione dell'input in binario, X-1 è un valore numerico dell'ordine di $O(2^n)$ e quindi il ciclo può venir eseguito un numero esponenziale di volte. Quindi il tuo algoritmo ha complessità esponenziale.

[Rggb1]

Effettivamente è spiegato in modo un po' approssimativo. E' anzitutto necessario sapere cosa si intende: parliamo del modello normalmente usato, ovvero le macchine di Turing, e stabiliamo di usare una rappresentazione dei numeri in base due.

Diciamo che dato un numero rappresentato in una certa base $b>1$ - usualmente ci può andare bene la base due del modello - non sono noti algoritmi che eseguono la sua fattorizzazione con complessità temporale $t$ inclusa in $O(b^k)$ per qualche $k$ positivo.

[pnp1]

@Deckard in effetti hai ragione.

@Rggb hai detto che il modello usato è quello delle macchine di Turing, e qui mi hai fatto sorgere un dubbio atroce:
La complessità di un problema non dovrebbe essere indipendente dal modello di calcolo usato?

[Rggb1]

Ho detto che il modello è quello delle MdT PIU' la rappresentazione dei numeri in base $b>1$. Ma il dubbio legittimo, e si può anche capire perché ti sia venuto.

Deckard ed io abbiamo dato due risposte che si completano a vicenda; tu stesso hai notato che aveva ragione. Calcolavi la complessità temporale $t$ del tuo semplice algoritmo sulla base del numero di passi necessari rispetto al numero in esame $n$, e quindi ne concludevi che la complessità era lineare ovvero $t in O(n)$. Invece non è questo che si deve considerare - come ti ho detto sopra e come Deckard ti ha fatto vedere.

Inoltre è vero che la complessità è indipendente dal modello di calcolo, sempre che sia equivalente a quello delle MdT: i calcolatori reali lavorano con un modello che è ad esso equivalente, e che - ovviamente - è equivalente ad un linguaggio di programmazione di alto livello, che può essere quindi implementato praticamente.

[ Altri modelli puramente teorici (es. i cd. Quantum Computer) sono strettamente più potenti, ma non sono utilizzabili poiché non ne esiste un corrispondente reale. C'è da dire che ai QC ci stanno dietro da pazzi, spendendo anche un sacco di soldi, ma secondo me non ne vengono a capo ]

[hamming_burst]

OT

"Rggb":C'è da dire che ai QC ci stanno dietro da pazzi

io direi che ci stanno dietro dei pazzi

/OT

[pnp1]

Ok, bene mi hai chiarito la cosa.

Lo so che i calcolatori reali lavorano con un modello che è equivalente a quello delle macchine di Turing, ma sono equivalenti nel senso che hanno lo stesso potere computazionale (inteso come possibilità di calcolare le stesse cose), ma ovviamente non sono equivalenti dal punto di vista della potenza (intesa come numero di operazioni eseguite nell'unità di tempo) e quindi mi era sorto il dubbio che i due modelli potessero essere differenti dal punto di vista della complessità, ma ora mi è tutto più chiaro, non ragionavo correttamente.

Un'ultima cosa, spesso nei corsi di programmazione quando si calcola il costo di un algoritmo si tende a considerare i costi di alcune operazioni come costanti, quando in realtà costanti non sono.
Però, visto che in un calcolatore le variabili intere hanno una lughezza fissa dovuta ai limiti dell'hardware (almeno in linguaggi come il c) è possibile dire che il costo ad esempio di un prodotto è costante (nella dimensione dell'input), dato che di fatto sono costanti le dimensioni degli input?

[Rggb1]

Esatto. Una moltiplicazione fra numeri di lunghezza fissata, di fatto, su un computer è costante.