Esercizi per le vacanze aiutatemi
Inviato: 20/06/2017, 12:08
1) dimostra con le equazione che 1+1=X e 2=X hanno lo stesso risultato
2) la somma di due numeri è tre, il rapporto è due. quali sono questi due numeri?
3)A livello informale, esso richiede di determinare se ogni problema per il quale un computer è in grado di verificare la correttezza di una soluzione positiva, in un tempo accettabile, sia anche un problema che può essere risolto dal computer in un tempo accettabile (ovvero se il computer sia in grado di trovare da solo una soluzione positiva in un tempo accettabile).
Se la risposta è no, allora esistono problemi per i quali è più complesso calcolare una certa soluzione che verificarla.
Una definizione formale fa uso delle classi di complessità P e NP. La prima consiste di tutti quei problemi di decisione che possono essere risolti con una macchina di Turing deterministica in un tempo che è polinomiale rispetto alla dimensione dei dati di ingresso; la seconda consiste di tutti quei problemi di decisione le cui soluzioni positive possono essere verificate in tempo polinomiale avendo le giuste informazioni, o, equivalentemente, la cui soluzione può essere trovata in tempo polinomiale con una macchina di Turing non deterministica. Il problema delle classi P e NP si risolve quindi nella seguente domanda:
P è uguale a NP?
ù
EDIT
0POLLOO
2) la somma di due numeri è tre, il rapporto è due. quali sono questi due numeri?
3)A livello informale, esso richiede di determinare se ogni problema per il quale un computer è in grado di verificare la correttezza di una soluzione positiva, in un tempo accettabile, sia anche un problema che può essere risolto dal computer in un tempo accettabile (ovvero se il computer sia in grado di trovare da solo una soluzione positiva in un tempo accettabile).
Se la risposta è no, allora esistono problemi per i quali è più complesso calcolare una certa soluzione che verificarla.
Una definizione formale fa uso delle classi di complessità P e NP. La prima consiste di tutti quei problemi di decisione che possono essere risolti con una macchina di Turing deterministica in un tempo che è polinomiale rispetto alla dimensione dei dati di ingresso; la seconda consiste di tutti quei problemi di decisione le cui soluzioni positive possono essere verificate in tempo polinomiale avendo le giuste informazioni, o, equivalentemente, la cui soluzione può essere trovata in tempo polinomiale con una macchina di Turing non deterministica. Il problema delle classi P e NP si risolve quindi nella seguente domanda:
P è uguale a NP?
ù
EDIT
0POLLOO