Carregant...
Carregant...

Vés al contingut (premeu Retorn)

The parallel approximability of the true and false gates problems for NOR-circuits

Autor
Serna, M.; Xhafa, F.
Tipus d'activitat
Article en revista
Revista
Parallel processing letters
Data de publicació
2002-03
Volum
12
Número
1
Pàgina inicial
127
Pàgina final
136
DOI
https://doi.org/10.1142/S0129626402000872 Obrir en finestra nova
URL
http://www.worldscientific.com/doi/abs/10.1142/S0129626402000872 Obrir en finestra nova
Resum
We study the parallel approximability of computing the number of true gates and false gates for circuits with only NOR gates; we refer to these problems as NOR-false gates and NOR-true gates problems, respectively. We show that the parallel approximability of these problems depends on restrictions on the topology of the circuit. More precisely, for circuits with fan-in and fan-out bounded by a constant and having a constant number of output gates both problems exhibit a threshold behavior in the...
Paraules clau
Circuit value problem, Log-space reductions, Nor-Gates, Number of false/true gates, Parallel approximation
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants