Perché P e P/Poly non è lo stesso?
-
05-11-2019 - |
Domanda
La definizione di P è una lingua che può essere decisa da un algoritmo di tempo polinomiale. La definizione di p/poli può essere considerata una lingua che può essere decisa da un circuito di dimensioni polinomiali (vedi http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf). Ora, perché un circuito di dimensioni polinomiali non può essere simulata nel tempo polinomiale?
Nessuna soluzione corretta
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange