The complexity of central slice functions

DOI10.1016/0304-3975(86)90122-2MaRDI QIDQ1084375zbMATH OpenOpenAlexFDO

Authors Paul E. Dunne

Publication date 1986

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(86)90122-2

zbMATH Keywords

combinational complexityk-slice of a Boolean functionmonotone circuit complexityNP-completeness

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25)

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).

Recommendations

• More on the complexity of slice functions
• scientific article; zbMATH DE number 3889430
• Negation is Powerless for Boolean Slice Functions
• On the complexity of slice functions
• On monotone simulations on nonmonotone networks

Cites work

• A Boolean function requiring 3n network size
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• Lower bounds on monotone complexity of the logical permanent
• More on the complexity of slice functions
• Negation is Powerless for Boolean Slice Functions
• On monotone simulations on nonmonotone networks
• On the complexity of slice functions

Cited in

(8)

• On the complexity of slice functions
• More on the complexity of slice functions
• On monotone simulations on nonmonotone networks
• \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice
• scientific article; zbMATH DE number 3889430 (Why is no real title available?)
• Negation is Powerless for Boolean Slice Functions
• Query complexity of Boolean functions on slices
• Query complexity of Boolean functions on the middle slice of the cube

This page was built for publication: The complexity of central slice functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1084375)