×
Kosub, Sven

A note on unambiguous function classes. (English) Zbl 1005.68523

Inf. Process. Lett. 72, No. 5-6, 197-203 (1999).

Cited in 2 Documents

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Cite Review PDF
Full Text: DOI

References:

[1] Grollmann, J.; Selman, A. L., Complexity measures for public-key cryptosystems, SIAM J. Comput., 17, 2, 309-335 (1988) · Zbl 0644.94016
[2] Gupta, S., Closure properties and witness reduction, J. Comput. System Sci., 50, 3, 412-432 (1995) · Zbl 0838.68035
[3] Hertrampf, U.; Vollmer, H.; Wagner, K. W., On the power of number-theoretic operations with respect to counting, (Proc. 10th Structure in Complexity Theory Conference, Los Alamitos (1995), IEEE Computer Society Press), 299-314
[4] Hempel, H.; Wechsung, G., The operators min and max on the polynomial hierarchy, (Proc. 14th Symposium on Theoretical Aspects of Computer Science. Proc. 14th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Sci., 1200 (1997), Springer: Springer Berlin), 93-104 · Zbl 1499.68126
[5] Johnson, D. S., A catalog of complexity classes, (van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. A (1990), Elsevier: Elsevier Amsterdam), 67-161 · Zbl 0900.68246
[6] Köbler, J.; Schöning, U.; Torán, J., On counting and approximation, Acta Inform., 26, 363-379 (1989) · Zbl 0663.03025
[7] Kosub, S., Clustermaschinen (1996), Friedrich-Schiller-Universität Jena, Fakultät für Mathematik und Informatik, Diplomarbeit
[8] Ogiwara, M.; Hemachandra, L., A complexity theory of feasible closure properties, J. Comput. System Sci., 46, 295-325 (1993) · Zbl 0798.68060
[9] Papadimitriou, C. H., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0557.68033
[10] Sheu, M.-J.; Long, T. J., UP and the low and high hierarchies: A relativized separation, Math. Systems Theory, 29, 423-449 (1996) · Zbl 0858.68040
[11] Toda, S., Computational complexity of counting complexity classes (1990), Tokyo Institute of Technology, Department of Computer Science: Tokyo Institute of Technology, Department of Computer Science Tokyo, Ph.D. Thesis
[12] Vollmer, H.; Wagner, K. W., The complexity of finding middle elements, Internat. J. Foundations Computer Sci., 4, 293-307 (1993) · Zbl 0804.68052
[13] Vollmer, H.; Wagner, K. W., Complexity classes of optimization functions, Inform. and Comput., 120, 198-219 (1995) · Zbl 0835.68048
[14] Wagner, K. W., Bounded query classes, SIAM J. Comput., 19, 833-846 (1990) · Zbl 0711.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.