The complexity of central slice functions
type: Item
instance of: scholarly article
title: The complexity of central slice functions
zbMATH Open document ID: 0605.94010
DOI: 10.1016/0304-3975(86)90122-2
author: Paul E. Dunne
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: The k-slice of a Boolean function \(f(x_ 1,...,x_ n)\) is the function \(f_ k=(f\wedge T^ n_ k)\vee T^ n_{k+1}\), where \(T^ n_ k\) is the k-th threshold function. Berkowitz has shown that the nonmonotone combinational and monotone circuit complexities of any k-slice function differ by at most an additive term of O(n log\({}^ 2 n)\). In addition, the fact that \(f=\bigvee^{n}_{k=1}(E^ n_ k\wedge f_ k)\), where \(E^ n_ k=\neg T^ n_{k+1}\wedge T^ n_ k\), implies that if f is ''hard'' then some slice of f must have large monotone complexity. However, this latter result does not specify any particular slice and it is known that some (nontrivial) slices of NP-complete Boolean functions have linear complexity. In this paper three basic NP-complete monotone Boolean functions are examined: n/2-cliques, Hamiltonian circuits, and satisfiability. It is proved that the N/2-slice (called central slice) is NP-complete for each of these functions, where N is the total number of variables \((N=n(n-1)/2\) for the first two functions).
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 06E30
zbMATH DE Number: 3978980
zbMATH Keywords: combinational complexity
zbMATH Keywords: monotone circuit complexity
zbMATH Keywords: NP-completeness
zbMATH Keywords: k-slice of a Boolean function
reviewed by: Stasys Jukna
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90122-2
OpenAlex ID: W2051306408
cites work: Q3941433
cites work: A Boolean function requiring 3n network size
cites work: On monotone simulations on nonmonotone networks
cites work: Q3758729
cites work: Lower bounds on monotone complexity of the logical permanent
cites work: Negation is Powerless for Boolean Slice Functions
cites work: Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
cites work: On the complexity of slice functions
cites work: More on the complexity of slice functions
description: scientific article; zbMATH DE number 3978980