Open questions in the theory of semifeasible computation

ABSTRACT

The study of semifeasible algorithms was initiated by Selman's work a quarter of century ago [Sel79,Sel81,Sel82]. Informally put, this research stream studies the power of those sets L for which there is a deterministic (or in some cases, the function may belong to one of various nondeterministic function classes) polynomial-time function f such that when at least one of x and y belongs to L, then f(x, y) ∈ L ∩ {x, y}. The intuition here is that it is saying: "Regarding membership in L, if you put a gun to my head and forced me to bet on one of x or y as belonging to L, my money would be on f(x, y) ."In this article, we present a number of open problems from the theory of semifeasible algorithms. For each we present its background and review what partial results, if any, are known.

REFERENCES

• 1: M. Agrawal , V. Arvind, Quasi-linear truth-table reductions to p-selective sets, Theoretical Computer Science, v.158 n.1-2, p.361-370, May 20, 1996 [doi>10.1016/0304-3975(95)00167-0 ]
• 2: {ABG90} A. Amir, R. Beigel, and W. Gasarch. Some connections between bounded query classes and non-uniform complexity. In Proceedings of the 5th Structure in Complexity Theory Conference, pages 232--243. IEEE Computer Society Press, July 1990.
• 3: M. Abadi , J. Feigenbaum , J Kilian, On hiding information form an oracle, Journal of Computer and System Sciences, v.39 n.1, p.21-50, Aug. 1989 [doi>10.1016/0022-0000(89)90018-4]
• 4: Eric Allender , Lane A. Hemachandra, Lower bounds for the low hierarchy, Journal of the ACM (JACM), v.39 n.1, p.234-251, Jan. 1992 [doi>10.1145/147508.147546]
• 5: J L Balcázar , R V Book, Sets with small generalized Kolmogorov complexity, Acta Informatica, v.23 n.6, p.679-688, Nov. 1986 [doi>10.1007/BF00264313]
• 6: José Balcázar , Ronald V Book , Uwe Schöning, Sparse sets lowness and highness, SIAM Journal on Computing, v.15 n.3, p.739-747, August 1986 [doi>10.1137/0215053]
• 7: {Bei88} R. Beigel. NP-hard sets are P-superterse unless R=NP. Technical Report 88-04, Department of Computer Science, Johns Hopkins University, August 1988.
• 8: Richard Beigel , Martin Kummer , Frank Stephan, Approximable sets, Information and Computation, v.120 n.2, p.304-314, Aug. 1, 1995 [doi>10.1006/inco.1995.1115 ]
• 9: Ronald V. Book , Timothy J. Long , Alan L. Selman, Quantitative relativizations of complexity classes, SIAM Journal on Computing, v.13 n.3, p.461-487, August 1984 [doi>10.1137/0213030]
• 10: {BLS85} R. Book, T. Long, and A. Selman. Qualitative relativizations of complexity classes. Journal of Computer and System Sciences, 30(3):395--413, 1985.
• 11: {Cai01} J. Cai. Sp2 ⊆ ZPPNP. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, 2001.
• 12: Ran Canetti, More on BPP and the polynomial-time hierarchy, Information Processing Letters, v.57 n.5, p.237-241, March 11, 1996 [doi>10.1016/0020-0190(96)00016-6 ]
• 13: Jin-Yi Cai , Venkatesan T. Chakaravarthy , Lane A. Hemaspaandra , Mitsunori Ogihara, Competing provers yield improved Karp-Lipton collapse results, Information and Computation, v.198 n.1, p.1-23, April 10, 2005 [doi>10.1016/j.ic.2005.01.002]
• 14: Derek Denny-Brown , Yenjo Han , Lane A. Hemaspaandra , Leen Torenvliet, Semi-membership algorithms: some recent advances, ACM SIGACT News, v.25 n.3, p.12-23, Sept. 1994 [doi>10.1145/193820.193828]
• 15: {FH05} P. Faliszewski and L. Hemaspaandra. Advice for semifeasible sets and the complexity-theoretic cost(lessness) of algebraic properties. International Journal of Foundations of Computer Science, 16(5):913--928, 2005.
• 16: Lane A. Hemaspaandra, Lowness: a yardstick for NP-P, ACM SIGACT News, v.24 n.2, p.10-14, Spring 1993 [doi>10.1145/156063.156064]
• 17: {HHN+95} L. Hemaspaandra, A. Hoene, A. Naik, M. Ogiwara, A. Selman, T. Thierauf, and J. Wang. Nondeterministically selective sets. International Journal of Foundations of Computer Science, 6(4):403--416, 1995.
• 18: Lane A. Hemaspaandra , Harald Hempel , Arfst Nickelsen, Algebraic Properties for Selector Functions, SIAM Journal on Computing, v.33 n.6, p.1309-1337, 2004 [doi>10.1137/S0097539703427550]
• 19: {HHW05} E. Hemaspaandra, L. Hemaspaandra, and O. Watanabe. The complexity of kings. Technical Report TR-870, Department of Computer Science, University of Rochester, Rochester, NY, June 2005.
• 20: Edith Hemaspaandra , Ashish V. Naik , Mitsunori Ogihara , Alan L. Selman, P-selective sets and reducing search to decision vs. self-reducibility, Journal of Computer and System Sciences, v.53 n.2, p.194-209, Oct. 1996 [doi>10.1006/jcss.1996.0061 ]
• 21: Lane A. Hemaspaandra , Ashish V. Naik , Mitsunori Ogihara , Alan L. Selman, Computing Solutions Uniquely Collapses the Polynomial Hierarchy, SIAM Journal on Computing, v.25 n.4, p.697-708, Aug. 1996 [doi>10.1137/S0097539794268315]
• 22: {HNP98} L. Hemaspaandra, C. Nasipak, and K. Parkins. A note on linear-nondeterminism, linear-sized, Karp-Lipton advice for the P-selective sets. Journal of Universal Computer Science, 4(8):670--674, 1998.
• 23: John E. Hopcroft, Recent Directions in Algorithmic Research, Proceedings of the 5th GI-Conference on Theoretical Computer Science, p.123-134, March 23-25, 1981
• 24: Lane A. Hemaspaandra , Mitsunori Ogihara , Gerd Wechsung, Reducing the number of solutions of NP functions, Journal of Computer and System Sciences, v.64 n.2, p.311-328, March 2002 [doi>10.1006/jcss.2001.1815 ]
• 25: {HOZZ} L. Hemaspaandra, M. Ogihara, M. Zaki, and M. Zimand. The complexity of finding top-Tada-equivalence-class members. Theory of Computing Systems. To appear.
• 26: Lane A. Hemaspaandra , Leen Torenvliet, Optimal advice, Theoretical Computer Science, v.154 n.2, p.367-377, Feb. 5, 1996 [doi>10.1016/0304-3975(95)00076-3 ]
• 27: Lane A. Hemaspaandra , Leen Torenvliet , L. Torenvliet, Theory of Semi-Feasible Algorithms, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 28: {HT06} Hemaspaandra and L. Torenvliet. P-selectivity, immunity, and the power of one bit. In Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science. Springer-Verlag Lecture Notes in Computer Science, January 2006. To appear.
• 29: {Joc68} C. Jockusch. Semirecursive sets and positive reducibility. Transactions of the AMS, 131(2):420--436, 1968.
• 30: Jürgen Kämper, Nonuniform proof systems: a new framework to describe nonuniform and probabilistic complexity classes, Theoretical Computer Science, v.85 n.2, p.305-331, Aug. 12, 1991 [doi>10.1016/0304-3975(91)90185-5 ]
• 31: Richard M. Karp , Richard J. Lipton, Some connections between nonuniform and uniform complexity classes, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.302-309, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804678]
• 32: {Ko83} K. Ko. On self-reducibility and weak P-selectivity. Journal of Computer and System Sciences, 26:209--221, 1983.
• 33: J. Kobler, On the structure of low sets [complexity classes], Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), p.246, June 19-22, 1995
• 34: {KS85} K. Ko and U. Schöning. On circuit-size complexity and the low hierarchy in NP. SIAM Journal on Computing, 14(1):41--51, 1985.
• 35: Johannes Köbler , Osamu Watanabe, New Collapse Consequences of NP Having Small Circuits, Proceedings of the 22nd International Colloquium on Automata, Languages and Programming, p.196-207, July 10-14, 1995
• 36: Johannes Köbler , Osamu Watanabe, New Collapse Consequences of NP Having Small Circuits, SIAM Journal on Computing, v.28 n.1, p.311-324, Feb. 1999 [doi>10.1137/S0097539795296206]
• 37: {Lan53} H. Landau. On dominance relations and the structure of animal societies, III: The condition for score structure. Bulletin of Mathematical Biophysics, 15:1--148, 1953.
• 38: {LLS75} R. Ladner, N. Lynch, and A. Selman. A comparison of polynomial time reducibilities. Theoretical Computer Science, 1(2):103--124, 1975.
• 39: {LS95} T. Long and M. Sheu. A refinement of the low and high hierarchies. Mathematical Systems Theory, 28:299--327, 1995.
• 40: Ashish V. Naik , John D. Rogers , James S. Royer , Alan L. Selman, A hierarchy based on output multiplicity, Theoretical Computer Science, v.207 n.1, p.131-157, Oct. 28, 1998 [doi>10.1016/S0304-3975(98)00060-7 ]
• 41: Ashish V. Naik , Alan L. Selman, Adaptive versus nonadaptive queries to NP and P-selective sets, Computational Complexity, v.8 n.2, p.169-187, Nov. 1999 [doi>10.1007/s000370050026 ]
• 42: Arfst Nickelsen , Till Tantau, Partial information classes, ACM SIGACT News, v.34 n.1, March 2003 [doi>10.1145/637437.637445]
• 43: Arfst Nickelsen , Till Tantau, The Complexity of Finding Paths in Graphs with Bounded Independence Number, SIAM Journal on Computing, v.34 n.5, p.1176-1195, 2005 [doi>10.1137/S0097539704441642]
• 44: Mitsunori Ogihara, Polynomial-time Membership Comparable Sets, SIAM Journal on Computing, v.24 n.5, p.1068-1081, Oct. 1995 [doi>10.1137/S0097539793258131]
• 45: Mitsunori Ogihara, Functions computable with limited access to NP, Information Processing Letters, v.58 n.1, p.35-38, April 8, 1996 [doi>10.1016/0020-0190(96)00030-0 ]
• 46: Alexander Russell , Ravi Sundaram, Symmetric alternation captures BPP, Computational Complexity, v.7 n.2, p.152-162, Nov. 1998 [doi>10.1007/s000370050007 ]
• 47: {Sch83} U. Schöning. A low and a high hierarchy within NP. Journal of Computer and System Sciences, 27:14--28, 1983.
• 48: {Sel79} A. Selman. P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. Mathematical Systems Theory, 13:55--65, 1979.
• 49: {Sel81} A. Selman. Some observations on NP real numbers and P-selective sets. Journal of Computer and System Sciences, 23:326--332, 1981.
• 50: {Sel82} A. Selman. Analogues of semirecursive sets and effective reducibilities to the study of NP complexity. Information and Control, 52:36--51, 1982.
• 51: Alan L. Selman, A taxonomy of complexity classes of functions, Journal of Computer and System Sciences, v.48 n.2, p.357-381, April 1994 [doi>10.1016/S0022-0000(05)80009-1]
• 52: D. Sivakumar, On membership comparable sets, Journal of Computer and System Sciences, v.59 n.2, p.270-280, Oct. 1999 [doi>10.1006/jcss.1999.1653 ]
• 53: Ming-Jye Sheu , Timothy J. Long, The Extended Low Hierarchy Is an Infinite Hierarchy, SIAM Journal on Computing, v.23 n.3, p.488-509, June 1994 [doi>10.1137/S0097539791218640]
• 54: {Tha03} M. Thakur. On optimal advice for P-selective sets. Technical Report TR-819, Department of Computer Science, University of Rochester, Rochester, NY, November 2003.
• 55: {Tod91} S. Toda. On polynomial-time truth-table reducibilities of intractable sets to P-selective sets. Mathematical Systems Theory, 24(2):69--82, 1991.
• 56: {Ver94} N. Vereshchagin, January 1994. Personal Communication.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Alternation and nondeterminism

Additional Classification:
  F. Theory of Computation
  F.0 GENERAL
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  G. Mathematics of Computing
  G.0 GENERAL

General Terms:
Algorithms