Free Access

Parameterized Complexity Classes Defined by Threshold Circuits and Their Connection with Sorting Networks

Raffael Muralha Paranhos

Instituto de Computação, Universidade Federal Fluminense, Niterói, Rio de Janeiro, Brazil

E-mail Address: raffaelmp@id.uff.br

Search for more papers by this author

Janio Carlos Nascimento Silva

Instituto Federal do Tocantins, Campus Porto Nacional, Porto Nacional, Tocantins, Brazil

E-mail Address: janio.carlos@ifto.edu.br

Corresponding author.

Search for more papers by this author

, and

Uéverton dos Santos Souza

Instituto de Computação, Universidade Federal Fluminense, Niterói, Rio de Janeiro, Brazil

E-mail Address: ueverton@ic.uff.br

Search for more papers by this author

https://doi.org/10.1142/S0129054123410046Cited by:0 (Source: Crossref)

This article is part of the issue:

Special Issue: Research in Combinatorial Optimization and Applications of COCOA 2021
Guest Editors: Donglei Du (University of New Brunswick, Canada), Lu Han (Beijing University of Posts and Telecommunications, P. R. China), Rolf H. Möhring (Technical University Berlin, Germany) and Chenchen Wu (Tianjin University of Technology, P. R. China)

Abstract

The main complexity classes of the Parameterized Intractability Theory are based on weighted Boolean circuit satisfiability problems and organized into a hierarchy so-called W-hierarchy. The W-hierarchy enables fine-grained complexity analyses of parameterized problems that are unlikely to belong to the FPT class. In this paper, we introduce the Th-hierarchy, a natural generalization of the W-hierarchy defined by unweighted threshold circuit satisfiability problems. Investigating the relationship between Th-hierarchy and W-hierarchy, we discuss the complexity of transforming Threshold circuits into Boolean circuits, and observe that sorting networks are powerful tools to handle such transformations. First, we show that these hierarchies collapse at the last level (W[P] $=$ Th[P]). After that, we present a time complexity analysis of an AKS sorting network construction, which supports some of our results. Finally, we prove that Th[ $t$ ] $\subseteq$ W[SAT] for every $t \in ℕ$ . As a by-product, our studies suggest that it is relevant to consider a new class based on logarithmic depth circuits in the W-hierarchy.

Communicated by Chenchen Wu

Keywords:

References

1. M. Ajtai, J. Komlós and E. Szemerédi , An 0 $(n log n)$ sorting network, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (1983), pp. 1–9. Google Scholar
2. N. Alon , Eigenvalues and expanders, Combinatorica 6(2) (1986) 83–96. Crossref, Web of Science, Google Scholar
3. S. Arora and B. Barak , Computational Complexity (Cambridge University Press, New York, NY, 2009). Crossref, Google Scholar
4. S. W. A.-H. Baddar and K. E. Batcher , The aks sorting network, Designing Sorting Networks, eds. S. W. A.-H. Baddar and K. E. Batcher (Springer, 2011), pp. 73–80. Crossref, Google Scholar
5. K. E. Batcher , Sorting networks and their applications, Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference (1968), pp. 307–314. Crossref, Google Scholar
6. R. G. Downey and M. R. Fellows , Parameterized Complexity (Springer Science & Business Media, 2012). Google Scholar
7. M. Fellows, J. Flum, D. Hermelin, M. Müller and F. Rosamond , W-hierarchies defined by symmetric gates, Theory of Computing Systems 46(2) (2010) 311–339. Crossref, Web of Science, Google Scholar
8. M. Furst, J. B. Saxe and M. Sipser , Parity, circuits, and the polynomial-time hierarchy, Mathematical Systems Theory 17 (1984) 13–27. Crossref, Google Scholar
9. A. Hajnal, W. Maass, P. Pudlák, M. Szegedy and G. Turán , Threshold circuits of bounded depth, Journal of Computer and System Sciences 46(2) (1993) 129–154. Crossref, Web of Science, Google Scholar
10. A. Lubotzky, R. Phillips and P. Sarnak , Explicit expanders and the Ramanujan conjectures, Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986), pp. 240–246. Crossref, Google Scholar
11. A. Lubotzky, R. Phillips and P. Sarnak , Ramanujan graphs, Combinatorica 8(3) (1988) 261–277. Crossref, Web of Science, Google Scholar
12. D. G. O’connor and R. J. Nelson, Sorting system with nu-line sorting switch (April 10, 1962), US Patent 3,029,413. Google Scholar
13. M. S. Paterson , Improved sorting networks with $o (log n)$ depth, Algorithmica 5(1) (1990) 75–92. Crossref, Google Scholar
14. A. A. Razborov , Lower bounds on the size of bounded depth circuits over a complete basis with logical addition, Mathematical Notes 41 (1987) 333–338. Crossref, Web of Science, Google Scholar
15. R. Smolensky , Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (1987), pp. 77–82. Crossref, Google Scholar
16. R. M. Tanner , Explicit concentrators from generalized n-gons, SIAM Journal on Algebraic Discrete Methods 5(3) (1984) 287–293. Crossref, Google Scholar
17. H. Xie, Studies on sorting networks and expanders, PhD thesis, Ohio University (1998). Google Scholar