@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},
pages = {155--179},
publisher = {EDP-Sciences},
volume = {30},
number = {2},
year = {1996},
mrnumber = {1420689},
zbl = {0860.68051},
language = {en},
url = {http://archive.numdam.org/item/ITA_1996__30_2_155_0/}
}
TY - JOUR AU - Arvind, V. AU - Köbler, J. AU - Mundhenk, M. TI - Monotonous and randomized reductions to sparse sets JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 1996 SP - 155 EP - 179 VL - 30 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/item/ITA_1996__30_2_155_0/ LA - en ID - ITA_1996__30_2_155_0 ER -
%0 Journal Article %A Arvind, V. %A Köbler, J. %A Mundhenk, M. %T Monotonous and randomized reductions to sparse sets %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1996 %P 155-179 %V 30 %N 2 %I EDP-Sciences %U http://archive.numdam.org/item/ITA_1996__30_2_155_0/ %G en %F 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) no. 2, pp. 155-179. http://archive.numdam.org/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 | Zbl
3. , , , , , , , and , Reductions to sets of low information content, In Complexity Theory, Current Research, Cambridge University Press, 1993, pp. 1-45. | MR | Zbl
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 | Zbl
5. , and , Upper bounds on the complexity of sparse and tally descriptions, Mathematical Systems Theory, to appear. | MR | Zbl
6. , Self-reducibility, Journal of Computer and System Sciences, 1990, 41, pp. 367-388. | MR | Zbl
7. , and , Structural Complexity I, II. EATCS Monographs on Theoretical Computer Science, Springer Verlag, 1988. | MR | Zbl
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 | Zbl
9. and , On isomorphisms and density of NP and other complete sets, SIAM Journal on Computing, 1977, 6 (2), pp. 305-322. | MR | Zbl
10. and , On sets truth-table reducible to sparse sets, SIAM Journal on Computing, 1988, 17 (5), pp. 903-919. | MR | Zbl
11. , and , Sparse reduces conjunctively to tally, Proceedings of the 8th Structure in Complexity Theory Conference, IEEE Computer Society Press, 1993. | MR
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 | Zbl
14. , A note on sparse complete sets, SIAM Journal on Computing, 1979, 8 (3), pp. 431-433. | MR | Zbl
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
16. , Computational complexity of probabilistic complexity classes, SIAM Journal on Computing, 1977, 6, pp. 675-695. | MR | Zbl
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
19. and , Relativizing relativized computations, Theoretical Computer Science, 1989, 68, pp. 267-276. | MR | Zbl
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
21. , PNP[log n] and sparse Turing-complete sets for NP, Journal of Computer and System Sciences, 1989, 39 (3) pp. 282-298. | MR | Zbl
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 | Zbl
24. , On self-reducibility and weak p-selectivity, Journal of Computer and system Sciences, 1983, 26, pp. 209-221. | MR | Zbl
25. , Distinguishing conjunctive and disjunctive reducibilities by sparse sets, Information and Computation, 1989, 81 (1) pp. 62-87. | MR | Zbl
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 | Zbl
27. , and , A comparison of polynomial time reducibilities, Theoretical Computer Science, 1975, 1 (2), pp. 103-124. | MR | Zbl
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 | Zbl
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
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 | Zbl
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
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
35. , Reductions on NP and p-selective sets, Theoretical Computer Science, 1982, 19, pp. 287-304. | MR | Zbl
36. and , Reducibilities on tally and sparse sets, Theoretical Informatics and Applications, 1991, 25, pp. 293-302. | Numdam | MR | Zbl
37. , On polynomial time truth-table reducibilities of intractable sets to P-selective sets, Mathematical Systems Theory, 1991, 24 (2), pp. 69-82. | MR | Zbl
38. , TWO results on polynomial time truth-table reductions to sparse sets, SIAM Journal on Computing, 1983, 12 (3), pp. 580-587. | MR | Zbl
39. and , NP is as easy as detecting unique solutions, Theoretical Computer Science, 1986 47, pp. 85-93. | MR | Zbl
40. , More complicated questions about maxima and minima, and some closures of NP, Theoretical Computer Science, 1987, 57, pp. 53-80. | MR | Zbl
41. , Some consequences of non-uniform conditions on uniform classes, Theoretical Computer Science, 1983, 26, pp. 287-300. | MR | Zbl
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 | Zbl
