There are no p-complete families of symmetric Boolean functions
type: Item
instance of: scholarly article
title: There are no p-complete families of symmetric Boolean functions
zbMATH Open document ID: 0662.94023
DOI: 10.1016/0020-0190(89)90174-9
author: Mihály Geréb-Graus
author: Ramamohan Paturi
author: Endre Szemerédi
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 4083548
zbMATH Keywords: p-projection
zbMATH Keywords: completeness
zbMATH Keywords: symmetric Boolean functions
zbMATH Keywords: p-complete family
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90174-9
OpenAlex ID: W2002125674
cites work: A complexity theory based on Boolean algebra
cites work: Q3929052
description: scientific article; zbMATH DE number 4083548