@article{ITA_1996__30_2_155_0,
author = {Arvind, V. and K\"obler, J. and Mundhenk, M.},
title = {Monotonous and randomized reductions to sparse sets},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {30},
year = {1996},
pages = {155-179},
mrnumber = {1420689},
zbl = {0860.68051},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_1996__30_2_155_0}
}
Arvind, V.; Köbler, J.; Mundhenk, M. Monotonous and randomized reductions to sparse sets. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) pp. 155-179. http://gdmltest.u-ga.fr/item/ITA_1996__30_2_155_0/
1. and , Reducibility, randomness, and intractability, Proc. 9th ACM Symp. on Theory of Computing, 1977, pp. 151-163.
2. , , and , Relating equivalence and reducibility to sparse sets, SIAM Journal on Computing 1992, 21 (3), pp. 529-539. | MR 1163344 | Zbl 0761.68039
3. , , , , , , , and , Reductions to sets of low information content, In Complexity Theory, Current Research, Cambridge University Press, 1993, pp. 1-45. | MR 1255339 | Zbl 0794.68058
4. , and , On bounded truth-table, conjunctive, and randomized reductions to sparse sets, Proc. 12th Conf. FST & TCS, Lecture Notes in Computer Science, 52, pp. 140-151, Springer Verlag, 1992. | MR 1229096 | Zbl 0919.03034
5. , and , Upper bounds on the complexity of sparse and tally descriptions, Mathematical Systems Theory, to appear. | MR 1360197 | Zbl 0840.68041
6. , Self-reducibility, Journal of Computer and System Sciences, 1990, 41, pp. 367-388. | MR 1079471 | Zbl 0718.68037
7. , and , Structural Complexity I, II. EATCS Monographs on Theoretical Computer Science, Springer Verlag, 1988. | MR 1047862 | Zbl 0638.68040
8. , Relationship between density and deterministic complexity of NP-complete languages. Proceedings of the 5th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, 62, pp. 63-71, Springer Verlag, 1978. | MR 520839 | Zbl 0382.68068
9. and , On isomorphisms and density of NP and other complete sets, SIAM Journal on Computing, 1977, 6 (2), pp. 305-322. | MR 455536 | Zbl 0356.68059
10. and , On sets truth-table reducible to sparse sets, SIAM Journal on Computing, 1988, 17 (5), pp. 903-919. | MR 961047 | Zbl 0665.68040
11. , and , Sparse reduces conjunctively to tally, Proceedings of the 8th Structure in Complexity Theory Conference, IEEE Computer Society Press, 1993. | MR 1310802
12. , and , Connections between the complexity of unique satisfiability and the threshold behavior of randomized reductions, Proceedings of the 6th Structure in Complexity Theory Conference, pp. 255-269, IEEE Computer Society Press, 1991.
13. , and , The complexity of promise problems with applications to public-key cryptography, Information and Control, 1984, 61, pp. 114-133. | MR 772678 | Zbl 0592.94012
14. , A note on sparse complete sets, SIAM Journal on Computing, 1979, 8 (3), pp. 431-433. | MR 539260 | Zbl 0415.68006
15. and , On the computational complexity of small descritpions, In Proceedings of the 6th Structure in Complexity Theory Conference, pp. 89-101. IEEE Computer Society Press, 1991, The final version is to appear in SIAM Journal on Computing. | Zbl 0799.68085
16. , Computational complexity of probabilistic complexity classes, SIAM Journal on Computing, 1977, 6, pp. 675-695. | MR 464691 | Zbl 0366.02024
17. and , On reductions of NP sets to sparse sets, Proc. 6th Structure in Complexity Theory Conference, pp. 79-88. IEEE Computer Society Press, 1991.
18. , and , How hard are sparse sets? Proc. 7th Structure in Complexity Theory Conference, IEEE Computer Society Press, 1992. | MR 1249979
19. and , Relativizing relativized computations, Theoretical Computer Science, 1989, 68, pp. 267-276. | MR 1031961 | Zbl 0679.68084
20. and , Computing functions with parallel queries to NP, Proceedings of the 8th Structure in Complexity Theory Conference, pp. 280-291, IEEE Computer Society Press; May 1993. | MR 1310807
21. , PNP[log n] and sparse Turing-complete sets for NP, Journal of Computer and System Sciences, 1989, 39 (3) pp. 282-298. | MR 1030658 | Zbl 0693.68027
22. and , Some connections between nonuniform and uniform complexity classes, Proceedings of the 12th ACM Symposium on Theory of Computing, 1980, pp. 302-309.
23. , Some observations on the probabilistic algorithms and NP-hard problems, Information Processing Letters, 1982, 14, pp. 39-43. | MR 654074 | Zbl 0483.68045
24. , On self-reducibility and weak p-selectivity, Journal of Computer and system Sciences, 1983, 26, pp. 209-221. | MR 708837 | Zbl 0519.68062
25. , Distinguishing conjunctive and disjunctive reducibilities by sparse sets, Information and Computation, 1989, 81 (1) pp. 62-87. | MR 992304 | Zbl 0681.68066
26. , , and , Turing machines with few accepting computations and low sets for PP, Journal of Computer and System Sciences, 1992, 44 (2), pp. 272-286. | MR 1160464 | Zbl 0757.68056
27. , and , A comparison of polynomial time reducibilities, Theoretical Computer Science, 1975, 1 (2), pp. 103-124. | MR 395319 | Zbl 0321.68039
28. , Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis, Journal of Computer and System Sciences, 1982, 25 (2), pp. 130-143. | MR 680515 | Zbl 0493.68043
29. , Hausdorff-Reduktionen zu Mengen mit geringem Informationsgehalt, PhD dissertation, Universität Ulm, 1993.
30. and , On one query self-reducible sets, Theoretical Computer Science, 1993, 112, pp. 255-276. | MR 1216322
31. and , On polynomial-time bounded truth-table reducibility of NP sets to sparse sets, SIAM Journal on Computing, 1991, 20(3), pp. 471-483. | MR 1094526 | Zbl 0741.68049
32. and , Randomized reductions to sparse sets, Proceedings of the 7th Structure in Complexity Theory Conference, IEEE Computer Society Press, 1992, pp. 239-242. | MR 1249980
33. , Relativized limitations of the left set technique and closure classes of sparse sets, Proceedings of the 8th Structure in Complexity Theory Conference, pp. 215-222. IEEE Computer Society Press, 1993.
34. , On random reductions from sparse sets to tally sets, Information Processing Letters, 1993, 46, pp. 239-241. | Zbl 0780.68044
35. , Reductions on NP and p-selective sets, Theoretical Computer Science, 1982, 19, pp. 287-304. | MR 671872 | Zbl 0489.03016
36. and , Reducibilities on tally and sparse sets, Theoretical Informatics and Applications, 1991, 25, pp. 293-302. | Numdam | MR 1119046 | Zbl 0731.68039
37. , On polynomial time truth-table reducibilities of intractable sets to P-selective sets, Mathematical Systems Theory, 1991, 24 (2), pp. 69-82. | MR 1096692 | Zbl 0722.68059
38. , TWO results on polynomial time truth-table reductions to sparse sets, SIAM Journal on Computing, 1983, 12 (3), pp. 580-587. | MR 707414 | Zbl 0532.68051
39. and , NP is as easy as detecting unique solutions, Theoretical Computer Science, 1986 47, pp. 85-93. | MR 871466 | Zbl 0621.68030
40. , More complicated questions about maxima and minima, and some closures of NP, Theoretical Computer Science, 1987, 57, pp. 53-80. | MR 908480 | Zbl 0653.03027
41. , Some consequences of non-uniform conditions on uniform classes, Theoretical Computer Science, 1983, 26, pp. 287-300. | MR 726923 | Zbl 0541.68017
42. , On certain polynomial-time truth-table reducibilities of complete sets to sparse sets, SIAM Journal on Computing, 1983, 12 (3), pp. 411-425. | MR 707404 | Zbl 0545.03023