×

Positive and negative proofs for circuits and branching programs. (English) Zbl 1347.68158

The authors think that the negative proofs are a neglected aspect of counting. They introduce the notion of negative proof tree. Based on some complexity class C, Zap-C is the class of functions counting positive and negative proofs.
They prove that Zap-BWBP \(\subseteq\) Zap-NC\(_1\) \(\subseteq\) Zap-PBP.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allender, Eric, Arithmetic circuits and counting complexity classes, (Krajíček, J., Complexity of Computations and Proofs (2004), Quaderni di Matematica) · Zbl 1098.68049
[2] Mix Barrington, David A., Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^1\), J. Comput. System Sci., 38, 1, 150-164 (1989) · Zbl 0667.68059
[3] Beigel, Richard, The polynomial method in circuit complexity, (Structure in Complexity Theory Conference (1993), IEEE Computer Society), 82-95
[4] Mix Barrington, David A.; Lu, Chi-Jen; Bro Miltersen, Peter; Skyum, Sven, Searching constant width mazes captures the \(AC^0\) hierarchy, (Morvan, Michel; Meinel, Christoph; Krob, Daniel, STACS. STACS, Lecture Notes in Comput. Sci., vol. 1373 (1998), Springer), 73-83
[5] Caussinus, Hervé; McKenzie, Pierre; Thérien, Denis; Vollmer, Heribert, Nondeterministic \(NC^1\) computation, J. Comput. System Sci., 57, 2, 200-212 (1998) · Zbl 0921.68029
[6] Dorzweiler, Olga, Zap-Klassen für Schaltkreise und Branching Programs (2013), Universität Tübingen, Master thesis
[7] Fenner, Stephen A.; Fortnow, Lance; Kurtz, Stuart A., Gap-definable counting classes, J. Comput. System Sci., 48, 1, 116-148 (1994) · Zbl 0802.68051
[8] Flamm, Thomas, Zap-C Schaltkreise (2012), Universität Tübingen, Diploma thesis
[9] Hansen, Kristoffer Arnsfelt, Constant width planar branching programs characterize \(ACC^0\) in quasipolynomial size, (IEEE Conference on Computational Complexity (2008), IEEE Computer Society), 92-99 · Zbl 1103.68094
[10] Immerman, Neil, Nondeterministic space is closed under complementation, SIAM J. Comput., 17, 5, 935-938 (1988) · Zbl 0668.68056
[11] Jung, Hermann, Depth efficient transformations of arithmetic into Boolean circuits, (Budach, Lothar, FCT. FCT, Lecture Notes in Comput. Sci., vol. 199 (1985), Springer), 167-174 · Zbl 0573.94016
[12] Lange, Klaus-Jörn, Unambiguity of circuits, Theoret. Comput. Sci., 107, 1, 77-94 (1993) · Zbl 0774.68047
[13] Papadimitriou, Christos H., Computational Complexity (1994), Addison-Wesley · Zbl 0833.68049
[14] Reinhardt, Klaus; Allender, Eric, Making nondeterminism unambiguous, (FOCS (1997), IEEE Computer Society), 244-253 · Zbl 0947.68063
[15] Szelepcsényi, Róbert, The method of forced enumeration for nondeterministic automata, Acta Inform., 26, 3, 279-284 (1988) · Zbl 0638.68046
[16] Venkateswaran, H., Circuit definitions of nondeterministic complexity classes, SIAM J. Comput., 21, 4, 655-670 (1992) · Zbl 0749.68039
[17] Vollmer, Heribert, Introduction to Circuit Complexity - A Uniform Approach, Texts Theoret. Comput. Sci. (1999), Springer · Zbl 0931.68055
[18] Venkateswaran, H.; Tompa, Martin, A new pebble game that characterizes parallel complexity classes, SIAM J. Comput., 18, 3, 533-549 (1989) · Zbl 0678.68047
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.