Newsgroup: it.scienza.informatica
Titolo: Tempo polinomiale

Scusate la mia profonda ignoranza...
In un articolo ho trovato la seguente frase:
La casualità di una sequenza binaria soddisfa la condizione di
impredicibilità se e solo se nessun
[...]
POLYNOMIAL TIME ALGORITHM (IN SIZE OF THE SEQUENCE)
[...]
è capace di prevedere il bit successivo della sequenza, una volta noto
il suo presente ed il suo passato, non meglio dell'algoritmo
decisionale costituito dal lancio di una moneta. (ovvero se il
risultato dell'argoritmo è esatto non più del 50% dei casi...)
Mi potreste ricordare cosa significava più precisamente di quanto mi
ricordo (cioè poco...) un "polynomial time algorithm"?
Grazie 1000 mi sareste di grande aiuto!
ciao
tommaso

 tommaso
Detto in soldoni vuol dire che il tempo speso per risolvere il problema con
l'algoritmo in questione, cresce all'aumentare della dimensione del problema
con andamento polinomiale.
Esempio: la ricerca lineare di un valore in un vettore di n elementi si
risolve in tempo polinomiale, la legge di crescita del tempo speso e'
infatti:
T(n) = n
NB: l'ugualianza non e' esatta, ma la si puo' rendere tale con un opportuno
coefficiente moltiplicativo, a partire da un certo valore n' che si puo'
determinare.
Ciao. Federico.


In aggiunta alle cose dette da "mfede".....In pratica può esistere un
algoritmo che in tempo polinomiale riesce a computare il problema.
Questi problemi P,  si contrappongono ai famosi problemi NP (non
polinomiali) il cui comportamento è al centro degli studi di molti
ricercatori , data l'intrattabilità.
Considera , per capire , come polinomiale un algoritmo che si può in un
certo modo controllare in senso temporale , non polinomiale altrimenti.
ciao
Sotomajor

 ricercatori , data l'intrattabilità.
Errore!! NP = Nondeterministic Polinomial: un problema risolvibile da una
macchina di Turing non deterministica in un numero di passi che è una
funzione polinomiale della dimensione dell'input.
E' assai sbagliato dire non polinomial, poiché in realtà la questione se
P=NP o no è aperta.


Per favore, potreste essere più chiari? :-)
Come può essere una macchina di Turing non deterministica?
io avevo capito che un algoritmo a tempo polinomiale è un algoritmo il cui
tempo di esecuzione *nel caso peggiore* è esprimibile come funzione
polinomiale della lunghezza del dato in ingresso...
NP invece ??!?
Mi pare di ricordare un esempio di NP come quello di un algoritmo di cui non
si è in grado di capire a priori quando sarebbe cessata la sua esecuzione,
ad esempio trovare i primi 100000 numeri primi (ovviamente senza conoscerli
già)...
Ciao
tommaso


E' difficile riassumere in due parole quello che si studia a informatica ...
provo a essere divulgativo, per cui chi, come me, si è laureato in
informatica, perdonerà eventuali imprecisioni dovute alla divulgazione:
Le Macchine di Turing non deterministiche sono in grado di eseguire in
parallelo molti percorsi di computazione (senza comunicare fra di loro). In
alternativa, si può dire che la MdT non deterministica dato un problema
"indovina" una soluzione, che necessita di essere poi verificata. Sarò più
chiaro in seguito.
Consideriamo i problemi decisionali, quelli la cui risposta è SI o NO.
Ci sono problemi decisionali risolvibili con algoritmi polinomiali (P), e
altri (NP) invece di cui non si conoscono algoritmi polinomiali ma invece
esistono algoritmi polinomiali che, dato l'input e una stringa di dimensioni
polinomiali rispetto all'input, sono in grado di verificare una eventuale
soluzione in tempo polinomiale.
Esempio:
Sapere se un numero è divisibile per due: => problema di classe P; la
divisione per due si può fare in tempo polinomiale.
Sapere se un numero non è primo: => problema decisionale NP
infatti possiamo definire una funzione f(n,d) dove n è l'input e d è un
fattore di n: verificando se d divide n (la divisione è polinomiale)
sappiamo se n non è primo.
Una eventuale macchina di Turing non deterministica potrebbe in parallelo
verificare tutti gli interi da 1 a n e scoprire se un numero ha dei
divisori. Ovviamente per farlo dovrebbe usare la funzione polinomiale f(n,d)
appena definita.
In altre parole: la MdT ci indica un divisore d per n, ma poi dobbiamo
verificarlo con la funzione f.
Quindi i problemi NP sono risolvibili in tempo polinomiale nella dimensione
dell'input da una MdT non deterministica.

 ha scritto nel messaggio
news:Lhy7a.162482$YG2.4...@twister1.libero.it...

[CUT]
Quello che ha scritto RDA_dinoxpc non è del tutto sbagliato ...e solo che si
è spinto un pò troppo in là rispetto a quello che era l'origine di questo
messaggio e alla domanda originaria.
E' vero esiste una questione aperta P=NP ma è uno di quei problemi ancora
irrisolti , sai quei classici problemi per cui  hanno messo in palio 1000000
di dollari al genio che riuscirà a dimostrarlo e conseguente premio nobel .
ciao
Soto

 già)...
No, si sa quanto "costa", in termini di tempo, la sua esecuzione

 già)...
Questo problema si chiama Halting Problem e non è calcolabile (altro che 
NP :-))
-- 
Facciamo tesoro di sentimenti cari e soavi
i quali ci ridestino per tutti gli anni,
che ancora tristi e perseguitati ci avanzano,
la memoria che non siamo sempre vissuti nel dolore.

 tommaso
Cerco di spiegare in soldoni cos'e' un problema NP. I "puristi" mi perdonino
se uso termini impropri.
Supponiamo di voler risolvere il "problema delle 8 regine", cioe' piazzare 8
regine su una scacchiera in modo che nussuna tenga in scacco l'altra. Un
metodo e' quello di procedere "per tentativi", infatti il problema e' un
tipico problema combinatorio. Posso piazzare la prima regina su una
qualunque delle 8 colonne della prima riga (ho 8 scelte). Per ogni scelta
fatta al primo passo, potro' al secondo passo scegliere una posizione delle
seconda regina nella seconda riga in modo da evitare uno scacco con la
seconda, e cosi' via per la terza regina, per la quarta regina, ecc...
Di fatto questo metodo origina un albero delle possibili soluzioni, in cui
ad ogni livello di profondita' viene aggiunta una regina.
La chiave e' qui: si immagini di avere a disposizione un meccanismo per far
proseguire parallelamente l'elaborazione ogni volta che facciamo una scelta
in uno qualunque dei livelli, e dare risposta positiva se almeno una delle
scelte fatte porta alla soluzione. Avendo un meccanismo di questo tipo, se
riusciamo a dare una risposta al problema in tempo polinomiale, allora il
problema e' NP.
Non so se ti ho aiutato, spero di si'!
Ciao. Federico.

 NP :-))
???? Da quando il test di primalità (trovare se un numero è primo oppure no)
corrisponde all'Halting Problem????
Hanno trovato che non è nemmeno NP, ma P...

 Hanno trovato che non è nemmeno NP, ma P...
I tre indiani :-)
Infatti è l'esempio che è scorretto: trovare i primi 100000 numeri primi non
vuol dire capire quando l'algoritmo si fermerà.
--------------------------------
Inviato via 
http://usenet.libero.it

 esiste già in alcuni linguaggi, pensa ad esempio il prolog. 
Eh?!?
Il Prolog non deterministico? In che senso, scusa?
Basandosi su una architettura prettamente deterministica (elaboratori
quantistici non ne abbiamo ancora) come potrebbe non esserlo?
Ma senza andare così nel dettaglio, il motore di inferenza del Prolog è
non solo deterministico ma anche concettualmente abbastanza "stupido" -
non per niente in molti casi si fa metaprogrammazione, ovvero si modifica
il motore stesso.
Una inferenza non deterministica è data avendo la 'preveggenza' (euristica
perfetta), ovvero potendo ad ogni bivio fare la scelta giusta. Nel caso in
questione, un problema NP è tale se, avendo tale 'preveggenza', la
complessità diviene polinomiale in funzione della dimensione del problema.
Vi dirò che la questione dei "fiumi che sfociano" non mi torna, perchè la
complessità computa *non* solo il *tempo* ma anche lo *spazio*, ed un
algoritmo NP che ad ogni passo si espanda in parallelo avrà sì tempo P ma
spazio NP - e dunque NP risulterà.
saluti,
   debrando
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

    debrando
Allora, ti do la definizione che sapevo io di NP così forse ci capiamo, che
magari per NP non intendi ciò che intendo io:
NP è l'unione, per k >=0, di NTIME[Pk(n)]
Quindi nella definizione di NP che so io, non si fa nessun accenno allo
spazio.

 spazio.
In quella che ho io si computa in egual modo tanto il tempo che lo spazio,
forse perchč piů indirizzata al ramo 'ricerca operativa'.


 forse perchè più indirizzata al ramo 'ricerca operativa'.
Buh, probabilmente dovrei riguardarmi un po' la teoria, sono arruginito...

 saranno invocate
Ordine testuale delle clausole definite.
 
-- 
"difficilmente riusciremo ad arginare la diffusione dei virus finche' 
 esisteranno programmi come  u(z1...zn)=sel1(u z1...zn)=u" - Kleene

 realizzazione del Prolog segue ben definite regole.
Se ho ben capito quello che intendeva, l'implementazione è deterministica
(per ovvi motivi) ma il linguaggio di per sé non lo è; ovvero avendo a
disposizione una macchina non deterministica, non sarebbe necessario
modificare il linguaggio per sfruttarla, ma basterebbe agire sul
compilatore/interprete.
Saluti.
--
\/   | |         Wilmer Ricciotti - ICQ UIN: 3233084
/\ e | | o s s   
wi...@libero.it
HiT - EdenGames: 
http://hit.edengames.net
sito  personale: 
http://www.cs.unibo.it/~ricciott/
 (non attivo)