Some consequences of non-uniform conditions on uniform classes. (English) Zbl 0541.68017

Non-uniform complexity classes appear from the circuit complexity. It is proved that if non-uniform classes \(\Sigma_ i/poly=\Pi_ i/poly,\) then \(\Sigma_{i+2}=\Pi_{i+2}\) in the Meyer-Stockmeyer hierarchy. Apart that, some connections between coincidence of complexity classes and sparse complete sets are ascertained. If there exists a sparse set which is complete for co-NP relatively to conjunctive reducibility then \(P=NP\). Besides that, if NP is conjunctively and disjunctively reducible to a sparse NP-complete set then also \(P=NP\).
Reviewer: D.Yu Grigorev


68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI


[1] Adleman, L.; Manders, K., Reducibility, randomness and intractibility, Proc. 9th ACM STOC, 151-163 (1977)
[2] Berman, P., Relationship between density and deterministic complexity of NP-complete languages, (5th Internat. Coll. on Automata, Languages and Programming. 5th Internat. Coll. on Automata, Languages and Programming, Lecture Notes in Comput. Sci., 62 (1978), Springer: Springer Berlin), Udine · Zbl 0382.68068
[3] Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. Comput., 6, 2, 305-322 (1977) · Zbl 0356.68059
[4] Fortune, S., A note on sparse complete sets, SIAM J. Comput., 8, 431-433 (1979) · Zbl 0415.68006
[5] Hong, Jia-Wei, On similarity and duality of computation, 21st Symp. FOCS, 348-359 (1980)
[6] Immerman, N., Upper and lower bounds for first order expressibility, 21st Symp. FOCS, 74-82 (1980)
[7] Jefferson, D. R., Type reduction and program verification, CMU Ph.D. Thesis (1980)
[8] Karp, K. M.; Lipton, R. J., Some connections between non-uniform and uniform complexity classes, Proc. 12th Ann. ACM STOC, 302-309 (1980)
[9] Ladner, R. E.; Lynch, N. A.; Selman, A. L., A comparison of polynomial time reducibilities, Theoret. Comput. Sci., 1, 103-123 (1975) · Zbl 0321.68039
[10] Long, T. J., A note on co-sparse polynomial time turing complete sets for NP, J. Comput. Systems Sci. (1980), submitted.
[11] Manhaney, S. R., Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis, Proc. 21st Ann. Symp. FOCS, 54-60 (1980)
[12] Meyer, A. R.; Paterson, M. S., With what frequency are apparently intractable problems difficult, MIT Tech. Memo. 126 (1979), Theoret. Comput. Sci. to appear.
[13] Stockmeyer, I. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[14] E. Ukkonen, Two results on polynomial time Turing reductions to sparse sets, SIAM J. Comput.; E. Ukkonen, Two results on polynomial time Turing reductions to sparse sets, SIAM J. Comput. · Zbl 0532.68051
[15] Yesha, Y., On certain polynomial-time truth table reducibilities of complete sets to sparse sets, (Tech. Rept. 152/81 (1981), Department of Computer Science, Univ. of Toronto: Department of Computer Science, Univ. of Toronto Canada) · Zbl 0545.03023
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.