Numero di porte non XOR necessarie per implementare una funzione booleana N-bit

Question

Ci sono $ 2^{2^n} $ possibili funzioni che hanno input booleani $ n $ e un singolo output booleano. Alcune di queste funzioni hanno circuiti logici booleani molto brevi. Alcuni hanno circuiti più lunghi.

UN Risultato classico nella complessità del circuito è quello, se si contano il numero totale di porte necessarie per implementare $ f $, la maggior parte di $ f $ s prende $ theta (2^n/n) $ 2 a 1 porte booleane. Sono interessato a una metrica leggermente diversa, dove Puoi usare tutte le porte XOR che vuoi ma non le conti (Idem per non cancelli, che sono solo un XOR con una costante di input). Quindi il tuo circuito potrebbe avere $ n $ e gate più $ 2^n $ xor Gates, e lo definirei un circuito di $ n $ n $.

Ho capito che è possibile implementare qualsiasi funzione $ n $ -input $ f $ utilizzando al massimo $ 2^{n/2+1} $ gate che non sono xor o no. La strategia funziona utilizzando $ 2^{n/2} $ e gates (con xor gates intervallati) per preparare un set di bit indicatore $ 2^{n/2} $ che possono essere xor'd insieme per fare qualsiasi funzione di $ n /2 $ bit. Quindi pretengo che i top $ n/2 $ bit del registro dell'indice di input sono "scegliendo" la sotto-funzione da applicare con i bit in basso $ n/2 $ e utilizzare i miei bit indicatore per preparare $ 2^{n/2 } $ possibili output di sottofunzione. Quindi utilizzo $ 2^{n/2} $ e gates per subire l'output di sotto-funzione desiderato (selezionato dai top $ n/2 $ bit del registro dell'indice di input).

Mi interessa sapere È possibile fare meglio di $ 2^{n/2+1} $ e Gates, o è così asintoticamente ottimale.