There are no p-complete families of symmetric Boolean functions (Q1114662)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4083548
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | There are no p-complete families of symmetric Boolean functions |
scientific article; zbMATH DE number 4083548 |
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
0.7801963090896606
0 references
0.7570095658302307
0 references
