Stiamo lavorando per ripristinare l'app di Unionpedia nel Google Play Store
UscenteArrivo
🌟Abbiamo semplificato il nostro design per una migliore navigazione!
Instagram Facebook X LinkedIn

AC0

Indice AC0

AC0 è una classe di complessità usata nella complessità dei circuiti. È la classe più piccola della gerarchia AC, e consiste di tutte le famiglie di circuiti che hanno profondità O(1) e dimensione polinomiale, con porte AND e porte OR con numero massimo di linee d'ingresso illimitato (fan-in) (ammettiamo le porte NOT soltanto alle entrate).

Indice

  1. 9 relazioni: AC (complessità), Classe di complessità, Complessità dei circuiti, DLOGTIME, Invertitore, Porta AND, Porta OR, PSPACE, Teoria del primo ordine.

  2. Classi di complessità

AC (complessità)

Nella complessità dei circuiti, AC è una gerarchia di classi di complessità. Ciascuna classe, ACi, consiste dei linguaggi riconosciuti dai circuiti booleani con profondità O(log^i n) e un numero polinomiale di porte AND e OR, con un numero massimo di linee d'ingresso (fan-in) illimitato.

Vedere AC0 e AC (complessità)

Classe di complessità

Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità. Un esempio tipico di definizione di classe di complessità ha la forma: Ad esempio, la classe NP è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing non deterministica in tempo polinomiale, mentre la classe P è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing deterministica in tempo polinomiale.

Vedere AC0 e Classe di complessità

Complessità dei circuiti

In informatica teorica, la complessità dei circuiti è un ramo della teoria della complessità computazionale nel quale le funzioni booleane sono classificate secondo la dimensione o la profondità dei circuiti booleani che le computano.

Vedere AC0 e Complessità dei circuiti

DLOGTIME

Nella teoria della complessità computazionale DLOGTIME è la classe di complessità di tutti i problemi computazionali risolvibili in una quantità logaritmica di tempo computazionale da una macchina di Turing deterministica.

Vedere AC0 e DLOGTIME

Invertitore

Nell'elettronica digitale, un invertitore (o porta NOT) è una porta logica che implementa la negazione logica. La sua tabella di verità è la seguente: Tale dispositivo restituisce dunque il valore negato del livello logico in ingresso.

Vedere AC0 e Invertitore

Porta AND

La porta AND è una porta logica digitale che implementa la congiunzione logica e porta la sigla 7408. Essa si comporta secondo la tabella di verità a destra.

Vedere AC0 e Porta AND

Porta OR

La porta OR (dalla congiunzione inglese or, "o") è una porta logica digitale che implementa la disgiunzione logica: essa si comporta come la tabella di verità a destra.

Vedere AC0 e Porta OR

PSPACE

Nella teoria della complessità computazionale, la classe di problemi PSPACE, che sta per polynomial space, è l'insieme di tutti i problemi che possono essere risolti da una macchina di Turing deterministica usando una quantità di memoria di O(n^k), dove n è la dimensione dei dati di input e k è un qualsiasi valore finito.

Vedere AC0 e PSPACE

Teoria del primo ordine

Nella logica matematica, una teoria del primo ordine (o calcolo dei predicati) è un particolare sistema formale, cioè una teoria formale, in cui è possibile esprimere enunciati e dedurre le loro conseguenze logiche in modo del tutto formale e meccanico.

Vedere AC0 e Teoria del primo ordine

Vedi anche

Classi di complessità

Conosciuto come AC⁰.