There are no p-complete families of symmetric Boolean functions (Q1114662)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | There are no p-complete families of symmetric Boolean functions |
scientific article |
Statements
There are no p-complete families of symmetric Boolean functions (English)
0 references
1989
0 references
We present a proof of a negative answer to the question raised by \textit{S. Skyum} and \textit{L. G. Valiant} [22nd Ann. IEEE Symp. on Foundations of Computer Science, New York, 244-253 (1981)], namely, whether the class of symmetric Boolean functions has a p-complete family.
0 references
p-projection
0 references
completeness
0 references
symmetric Boolean functions
0 references
p-complete family
0 references
