Indice
10 relazioni: AC0, Association for Computing Machinery, Complessità dei circuiti, Gruppo risolubile, Invertitore, Monoide, O-grande, Permanente (matematica), Porta AND, Porta OR.
- Classi di complessità
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).
Vedere ACC0 e AC0
Association for Computing Machinery
La Association for Computing Machinery (ACM) è un'associazione internazionale accademica e senza scopo di lucro dedicata a scienziati ed educatori dell'informatica ACM,.
Vedere ACC0 e Association for Computing Machinery
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 ACC0 e Complessità dei circuiti
Gruppo risolubile
In algebra, un gruppo risolubile è un gruppo G che possiede una serie normale abeliana, ovvero tale che esiste una catena di sottogruppi (dove e è l'elemento neutro del gruppo) in cui ogni H_i è normale in H_ e il quoziente H_/H_i è abeliano.
Vedere ACC0 e Gruppo risolubile
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 ACC0 e Invertitore
Monoide
Nell'algebra astratta, una branca della matematica, un monoide è una struttura algebrica dotata dell'operazione binaria associativa e di un elemento neutro.
Vedere ACC0 e Monoide
O-grande
La notazione matematica O-grande è utilizzata per descrivere il comportamento asintotico delle funzioni. Il suo obiettivo è quello di caratterizzare il comportamento di una funzione per argomenti elevati in modo semplice, ma rigoroso, al fine di poter confrontare il comportamento di più funzioni fra loro.
Vedere ACC0 e O-grande
Permanente (matematica)
In matematica, il permanente di una matrice quadrata A di ordine n, di elementi a_ è definito come dove sigma_i rappresenta una permutazione, ovvero un elemento del gruppo simmetrico S_n.
Vedere ACC0 e Permanente (matematica)
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 ACC0 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 ACC0 e Porta OR
Vedi anche
Classi di complessità
- 2-EXPTIME
- AC (complessità)
- AC0
- ACC0
- Classe di complessità
- Co-NP
- Co-NP-completo
- DLOGTIME
- E (complessità)
- EXPSPACE
- EXPTIME
- Gerarchia esponenziale
- L (complessità)
- Lista delle classi di complessità
- NC (complessità)
- NL (complessità)
- NP (complessità)
- NP-Intermedio
- NP-completo
- NP-difficile
- P (complessità)
- PSPACE
- PSPACE-completo
- Schema di approssimazione in tempo polinomiale
- Tempo pseudopolinomiale