×

Parameterized complexity classes defined by threshold circuits and their connection with sorting networks. (English) Zbl 07918137

Summary: 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 \((\mathrm{W}[\mathrm{P}]=\mathrm{Th}[\mathrm{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 \(\mathrm{Th}[\mathrm{t}]\subseteq\mathrm{W}[\mathrm{SAT}]\) for every \(t\in\mathbb{N}\). 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.

MSC:

68Qxx Theory of computing
05Cxx Graph theory
68-XX Computer science
Full Text: DOI

References:

[1] Ajtai, M., Komlós, J. and Szemerédi, E., An \(0 (n\logn)\) sorting network, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (1983), pp. 1-9. · Zbl 0523.68048
[2] Alon, N., Eigenvalues and expanders, Combinatorica6(2) (1986) 83-96. · Zbl 0661.05053
[3] Arora, S. and Barak, B., Computational Complexity (Cambridge University Press, New York, NY, 2009). · Zbl 1193.68112
[4] Baddar, S. W. A.-H. and Batcher, K. E., The aks sorting network, Designing Sorting Networks, eds. Baddar, S. W. A.-H. and Batcher, K. E. (Springer, 2011), pp. 73-80.
[5] Batcher, K. E., Sorting networks and their applications, Proceedings of the April 30-May 2, 1968, (1968), pp. 307-314.
[6] Downey, R. G. and Fellows, M. R., Parameterized Complexity (Springer Science & Business Media, 2012). · Zbl 0914.68076
[7] Fellows, M., Flum, J., Hermelin, D., Müller, M. and Rosamond, F., W-hierarchies defined by symmetric gates, Theory of Computing Systems46(2) (2010) 311-339. · Zbl 1211.68217
[8] Furst, M., Saxe, J. B. and Sipser, M., Parity, circuits, and the polynomial-time hierarchy, Mathematical Systems Theory17 (1984) 13-27. · Zbl 0534.94008
[9] Hajnal, A., Maass, W., Pudlák, P., Szegedy, M. and Turán, G., Threshold circuits of bounded depth, Journal of Computer and System Sciences46(2) (1993) 129-154. · Zbl 0801.68052
[10] Lubotzky, A., Phillips, R. and Sarnak, P., Explicit expanders and the Ramanujan conjectures, Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (1986), pp. 240-246.
[11] Lubotzky, A., Phillips, R. and Sarnak, P., Ramanujan graphs, Combinatorica8(3) (1988) 261-277. · Zbl 0661.05035
[12] D. G. O’connor and R. J. Nelson, Sorting system with nu-line sorting switch (April 10, 1962), US Patent 3,029,413.
[13] Paterson, M. S., Improved sorting networks with \(o(\logn)\) depth, Algorithmica5(1) (1990) 75-92. · Zbl 0689.68066
[14] Razborov, A. A., Lower bounds on the size of bounded depth circuits over a complete basis with logical addition, Mathematical Notes41 (1987) 333-338. · Zbl 0632.94030
[15] Smolensky, R., 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.
[16] Tanner, R. M., Explicit concentrators from generalized n-gons, SIAM Journal on Algebraic Discrete Methods5(3) (1984) 287-293. · Zbl 0554.05045
[17] H. Xie, Studies on sorting networks and expanders, PhD thesis, Ohio University (1998).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.