In this paper, we define and study the k-approximating circuits. A circuit accepting a given set of inputs A is k-approximated by accepting inputs that differ from one of A by at most k bits. We show that the existence of polynomial-size k-approximating circuits depends on the relation between k and the number of inputs.
k-approximating circuits / Cadoli, Marco; Francesco, Donini; Liberatore, Paolo; Schaerf, Marco. - In: IEEE TRANSACTIONS ON COMPUTERS. - ISSN 0018-9340. - 55:7(2006), pp. 913-917. [10.1109/tc.2006.105]
k-approximating circuits
CADOLI, Marco;LIBERATORE, Paolo;SCHAERF, Marco
2006
Abstract
In this paper, we define and study the k-approximating circuits. A circuit accepting a given set of inputs A is k-approximated by accepting inputs that differ from one of A by at most k bits. We show that the existence of polynomial-size k-approximating circuits depends on the relation between k and the number of inputs.File allegati a questo prodotto
| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2006_11573-231453.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
176.99 kB
Formato
Adobe PDF
|
176.99 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
