jops:
> On 4/5/19 1:03 AM, nctli wrote:
>> (in particolare ci si concentrera` sulle
>> classi P. NP, NP-Complete, Co-NP e #P). Poi verranno introdotti dei
>> nuovi modelli di calcolatori che vanno ben oltre le macchine di von
>> neumann. Spieghero` poi come fanno questi calcolatori a membrana ad
>> essere in grado di svolgere computazionalmente dei problemi appartenenti
>> alle classi sopraelencate in tempo lineare
>
> eh?????? In tempo lineare???
>
Si`, e` possibile. Poi dipende molto dal modello usato e dal tipo di
problema. Comunque fattibile in tempo polinomiale.
Esempio con un NP-Completo (dovrebbe essere l'articolo giusto):
https://idus.us.es/xmlui/handle/11441/52810
Il tutto chiaramente ha un prezzo: lo spazio.
--
GPG fingerprint: D9A2 2326 4DBF F909 AC1B E798 3E83 08E5 DBA9 FE87
