More Web Proxy on the site http://driver.im/

article

Free access

Semi-membership algorithms: some recent advances

Authors:

Derek Denny-Brown,

Lane A. Hemaspaandra,

Leen TorenvlietAuthors Info & Claims

ACM SIGACT News, Volume 25, Issue 3

Pages 12 - 23

https://doi.org/10.1145/193820.193828

Published: 01 September 1994 Publication History

Abstract

A semi-membership algorithm for a set A is, informally, a program that when given any two strings determines which is logically more likely to be in A. A flurry of interest in this topic in the late seventies and early eighties was followed by a relatively quiescent half-decade. However, in the 1990s there has been a resurgence of interest in this topic. We survey recent work on the theory of semi-membership algorithms.

References

[1]

{AA94} M. Agrawal and V. Arvind. Polynomial time truth-table reductions to P-selective sets. In Proceedings of the 9th Structure in Complexity Theory Conference, pages 24-30. IEEE Computer Society Press, June/July 1994.

[2]

{AH92} E. Allender and L. Hemachandra. Lower bounds for the low hierarchy. Journal of the ACM, 39(1):234-250, 1992.

Digital Library

[3]

{AHH⁺93} V. Arvind, Y. Han, L. Hemachandra, J. Köbler, A. Lozano, M. Mundhenk, M. Ogiwara, U. Schöning, R. Silvestri, and T. Thierauf. Reductions to sets of low information content. In K. Ambos-Spies, S. Homer, and U. Schöning, editors, Complexity Theory, pages 1-45. Cambridge University Press, 1993.

Digital Library

[4]

{AHOW92} E. Allender, L. Hemachandra, M. Ogiwara, and O. Watanabe. Relating equivalence and reducibility to sparse sets. SIAM Journal on Computing, 21(3):521-539, 1992.

Digital Library

[5]

{BBS86} J. Balcázar, R. Book, and U. Schöning. Sparse sets, lowness and highness. SIAM Journal on Computing, 15(3):739-746, 1986.

Digital Library

[6]

{BK88} R. Book and K. Ko. On sets truth-table reducible to sparse sets. SIAM Journal on Computing, 17(5):903-919, 1988.

Digital Library

[7]

{BKS94} R. Beigel, M. Kummer, and F. Stephan. Approximable sets. In Proceedings of the 9th Structure in Complexity Theory Conference, pages 12-23. IEEE Computer Society Press, June/July 1994.

[8]

{BL93} H. Burtschick and W. Lindner. On sets Turing reducible to P-selective sets. Technical Report 1993-38, TU-Berlin, Fachbereich Informatik, 1993.

[9]

{BLS84} R. Book, T. Long, and A. Selman. Quantitative relativizations of complexity classes. SIAM Journal on Computing, 13(3):461-487, 1984.

Digital Library

[10]

{BTvEB93} H. Buhrman, L. Torenvliet, and P. van Emde Boas. Twenty questions to a P-selector Information Processing Letters, 48(4), 1993.

Digital Library

[11]

{Buh93} H. Buhrman. Resource Bounded Reductions. PhD thesis, University of Amsterdam, Amsterdam, The Netherlands, June 1993.

[12]

{BvHT93} H. Buhrman, P. van Helden, and L. Torenvliet. P-selective self-reducible sets: A new characterization of P. In Proceedings of the 8th Structure in Complexity Theory Conference, pages 44-51. IEEE Computer Society Press, May 1993.

[13]

{CNS94} J. Cai, A. Naik, and A. Selman. A note on P-selective sets and on adaptive versus nonadaptive queries to NP. Technical Report 94-02, State University of New York at Buffalo, Department of Computer Science, Buffalo, NY, 1994.

[14]

{FL93} B. Fu and H. Li. On symmetric differences of NP-hard sets with weakly P-selective sets. Theoretical Computer Science, 120(2):279-291, 1993.

Digital Library

[15]

{HHO⁺ 93} L. Hemaspaandra, A. Hoene, M. Ogiwara, A. Selman, T. Thierauf, and J. Wang. Selectivity. In Proceedings of the 5th International Conference on Computing and Information, pages 55-59. IEEE Computer Society Press, 1993.

Digital Library

[16]

{HHO94} L. Hemaspaandra, A. Hoene, and M. Ogihara. Reducibility classes of P-selective sets. Technical Report TR-524, University of Rochester, Department of Computer Science, Rochester, NY, July 1994.

Digital Library

[17]

{HJ} L. Hemaspaandra and Z. Jiang. P-selectivity: Intersections and indices. In Journal of Computing and Information, 1(1), Special Issue: Proceedings of the 6th International Conference on Computing and Information. To appear.

[18]

{HJRW} L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe. Multiselectivity. In preparation.

[19]

{HNOS93} E. Hemaspaandra, A. Naik, M. Ogiwara, and A. Selman. P-selective sets, and reducing search to decision vs. self-reducibility. Technical Report 93-21, State University of New York at Buffalo, Department of Computer Science, Buffalo, NY, 1993.

[20]

{HNOS94} L. Hemaspaandra, A. Naik, M. Ogiwara, and A. Selman. Computing solutions uniquely collapses the polynomial hierarchy. In Proceedings of the 5th International Symposium on Algorithms and Computation. Springer-Verlag Lecture Notes in Computer Science, August 1994. To appear.

Digital Library

[21]

{HOW92} L. Hemachandra, M. Ogiwara, and O. Watanabe. How hard are sparse sets? In Proceedings of the 7th Structure in Complexity Theory Conference, pages 222-238. IEEE Computer Society Press, June 1992.

[22]

{HT94} L. Hemaspaandra and L. Torenvliet. Optimal advice. Manuscript, July 1994.

[23]

{Joc79} C. Jockusch. Recursion theory: Its generalizations and applications. In Proceedings of the Logic Colloquium, Leeds, pages 140-157. Cambridge University Press, 1979.

[24]

{Joh90} D. Johnson. A catalog of complexity classes. In J. Van Leeuwen, editor, Handbook of Theoretical Computer Science, chapter 2, pages 67-161. MIT Press/Elsevier, 1990.

Digital Library

[25]

{JT93} B. Jenner and J. Torán. Computing functions with parallel queries to NP. In Proceedings of the 8th Structure in Complexity Theory Conference, pages 280-291. IEEE Computer Society Press, May 1993.

[26]

{KL80} R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th ACM Symposium on Theory of Computing, pages 302-309, April 1980. An extended version has also appeared as: Turing machines that take advice, L 'Enseignement Mathématique, 2nd series 28, 1982, pages 191-209.

Digital Library

[27]

{Ko83} K. Ko. On self-reducibility and weak P-selectivity. Journal of Computer and System Sciences, 26:209-221, 1983.

[28]

{Köb93} J. Köbler. Locating P/poly optimally in the extended low hierarchy. In Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, pages 28-37. Springer-Verlag Lecture Notes in Computer Science #665, February 1993.

Digital Library

[29]

{Ogi94} M. Ogihara. Polynomial-time membership comparable sets. In Proceedings of the 9th Structure in Complexity Theory Conference, pages 2-11. IEEE Computer Society Press, June/July 1994.

[30]

{OW91} M. Ogiwara and O. Watanabe. On polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing, 20(3):471-483, June 1991.

Digital Library

[31]

{Rao94} R. Rao. On P-selectivity and closeness. Technical Report TR-499, University of Rochester, Department of Computer Science, Rochester, NY, 1994.

Digital Library

[32]

{Sel79} A. Selman. P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. Mathematical Systems Theory, 13:55-65, 1979.

[33]

{Sel82} A. Selman. Analogues of semirecursive sets and effective reducibilities to the study of NP complexity. Information and Control, 52:36-51, 1982.

[34]

{Sel94} A. Selman. A taxonomy of complexity classes of functions. Journal of Computer and System Sciences, 48(2):357-381, 1994.

Digital Library

[35]

{Tod91} S. Toda. On polynomial-time truth-table reducibilities of intractable sets to P-selective sets. Mathematical Systems Theory, 24:69-82, 1991.

[36]

{Ver94} N. Vereshchagin, January 1994. Personal Communication.

[37]

{Wan} J. Wang. Selectivity and self-reducibility: New characterizations of complexity classes. In Journal of Computing and Information, 1(1), Special Issue: Proceedings of the 6th International Conference on Computing and Information. To appear.

[38]

{Wat94} O. Watanabe, May 1994. Personal Communication.

[39]

{You92} P. Young. How reductions to sparse sets collapse the polynomial-time hierarchy: A primer. SIGACT News, 1992. Part I (#3, pages 107-117), Part II (#4, pages 83-94), and Corrigendum to Part I (#4, page 94).

Digital Library

Cited By

Burtschick HLindner W(2007)On sets turing reducible to p-selective setsTheory of Computing Systems10.1007/BF0267944530:2(135-143)Online publication date: 30-Jul-2007
https://doi.org/10.1007/BF02679445
Faliszewski PHemaspaandra L(2006)Open questions in the theory of semifeasible computationACM SIGACT News10.1145/1122480.112249537:1(47-65)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.1145/1122480.1122495
Hemaspaandra LOgihara MZaki MZimand M(2004)The Complexity of Finding Top-Toda-Equivalence-Class MembersLATIN 2004: Theoretical Informatics10.1007/978-3-540-24698-5_13(90-99)Online publication date: 2004
https://doi.org/10.1007/978-3-540-24698-5_13
Show More Cited By

Index Terms

Semi-membership algorithms: some recent advances
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical software

Recommendations

Semi-Membership Algorithms: Some Recent Advances
Algorithms for Next Generation Networks
Semi-Regular Triangle Remeshing: A Comprehensive Study

Semi-regular triangle remeshing algorithms convert irregular surface meshes into semi-regular ones. Especially in the field of computer graphics, semi-regularity is an interesting property because it makes meshes highly suitable for multi-resolution ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGACT News

ACM SIGACT News Volume 25, Issue 3

Sept. 1994

49 pages

ISSN:0163-5700

DOI:10.1145/193820

Editor:
Ian Parberry
Univ. of North Texas, Denton

Issue’s Table of Contents

Copyright © 1994 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1994

Published in SIGACT Volume 25, Issue 3

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
161
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)1

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Burtschick HLindner W(2007)On sets turing reducible to p-selective setsTheory of Computing Systems10.1007/BF0267944530:2(135-143)Online publication date: 30-Jul-2007
https://doi.org/10.1007/BF02679445
Faliszewski PHemaspaandra L(2006)Open questions in the theory of semifeasible computationACM SIGACT News10.1145/1122480.112249537:1(47-65)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.1145/1122480.1122495
Hemaspaandra LOgihara MZaki MZimand M(2004)The Complexity of Finding Top-Toda-Equivalence-Class MembersLATIN 2004: Theoretical Informatics10.1007/978-3-540-24698-5_13(90-99)Online publication date: 2004
https://doi.org/10.1007/978-3-540-24698-5_13
Zimand M(1998)On the size of classes with weak membership propertiesTheoretical Computer Science10.1016/S0304-3975(97)00114-X209:1-2(225-235)Online publication date: 6-Dec-1998
https://dl.acm.org/doi/10.1016/S0304-3975%2897%2900114-X
Hemaspaandra LNaik AOgihara MSelman A(1996)Computing Solutions Uniquely Collapses the Polynomial HierarchySIAM Journal on Computing10.1137/S009753979426831525:4(697-708)Online publication date: 1-Aug-1996
https://dl.acm.org/doi/10.1137/S0097539794268315
Hemaspaandra LTorenvliet L(1996)Optimal adviceTheoretical Computer Science10.1016/0304-3975(95)00076-3154:2(367-377)Online publication date: 5-Feb-1996
https://dl.acm.org/doi/10.1016/0304-3975%2895%2900076-3
Kobler J(1995)On the structure of low sets [complexity classes]Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference10.1109/SCT.1995.514863(246-261)Online publication date: 1995
https://doi.org/10.1109/SCT.1995.514863
Hemaspaandra LJiang Z(1995)P-selectivityTheoretical Computer Science10.1016/0304-3975(94)00290-Y145:1-2(371-380)Online publication date: 10-Jul-1995
https://dl.acm.org/doi/10.1016/0304-3975%2894%2900290-Y

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents