Limited nondeterminism

ABSTRACT

Yes, the lucky 13th column is here, and it is a guest column written by J. Goldsmith, M. Levy, and M. Mundhenk on the topic of limited nondeterminism---classes and hierarchies derived when nondeterminism itself is viewed as a quantifiable resource (as it indeed is!).Coming up in the Complexity Theory Column in the very special 100th issue of SIGACT News: A forum on the future of complexity theory. Many of the field's leading lights share their exciting insights on what lies ahead, so please be there in three!

REFERENCES

• 1: [1] K.R. Abrahamson, J.A. Ellis, M.R. Fellows, and M.E. Mata. Completeness for families of fixed parameter problems. Technical Report DCS-141-IR, U. Victoria (Canada), 1990.
• 2: Carme Àlvarez , Josep Díaz , Jacobo Torán, Complexity Classes with Complete Problems Between P and NP-C, Proceedings of the International Conference on Fundamentals of Computation Theory, p.13-24, August 21-25, 1989
• 3: Vikraman Arvind , Johannes Köbler , Martin Mundhenk, On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets, Proceedings of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science, p.140-151, December 18-20, 1992
• 4: [4] R. Beigel and J. Goldsmith. Downward separation fails catastrophically for limited nondeterminism classes. Submitted, ftp://ftp.cs.yale.edu/pub/beigel/bg-beta-draft.PS.gz.
• 5: [5] S.A. Bloch, J.F. Buss, and J. Goldsmith. Sharply bounded alternation within P. Submitted, http://www.cs.engr.uky.edu/~goldsmit/main.ps.
• 6: Stephen A. Bloch , Jonathan F. Buss , Judy Goldsmith, How hard are n2-hard problems?, ACM SIGACT News, v.25 n.2, p.83-85, June 1994 [doi>10.1145/181462.181465]
• 7: [7] R. Book. Tally languages and complexity classes. Information and Control, 26:186-193, 1974.
• 8: [8] R. Book and S. Greibach. Quasi-realtime languages. Mathematical Systems Theory, 4:97-111, 1970.
• 9: Jonathan F. Buss , Judy Goldsmith, Nondeterminism within P, SIAM Journal on Computing, v.22 n.3, p.560-572, June 1993 [doi>10.1137/0222038]
• 10: [10] S.R. Buss. Personal communication. See [9].
• 11: Liming Cai , Jianer Chen, On fixed-parameter tractability and approximability of NP optimization problems, Journal of Computer and System Sciences, v.54 n.3, p.465-474, June 1997 [doi>10.1006/jcss.1997.1490]
• 12: Liming Cai , Jianer Chen, On the Amount of Nondeterminism and the Power of Verifying, SIAM Journal on Computing, v.26 n.3, p.733-750, June 1997 [doi>10.1137/S0097539793258295]
• 13: [13] L. Cai, J. Chen, R.G. Downey, and M.R. Fellows. On the structure of parameterized problems in NP. submitted.
• 14: [14] J. Díaz and J. Torán. Classes of bounded nondeterminism. Mathematical Systems Theory, 23:21-32, 1990. Journal version of parts of [2].
• 15: [15] R.G. Downey and M.R. Fellows. Fixed-parameter intractability. In Proceedings 7th Structure in Complexity Theory Conference, pages 36-49. IEEE, 1992.
• 16: [16] R.G. Downey and M.R. Fellows. Parameterized Computational Feasibility, pages 219-244. Birkhäuser, 1995.
• 17: [17] G. Farr. On problems with short certificates. Acta Informatica, 31:479-502, 1994.
• 18: [18] P. Fischer and C.M.R. Kintala. Real-time computations with restricted nondeterminism. Mathematical Systems Theory, 12:219-231, 1979.
• 19: Jonathan Goldstine , C. M. R. Kintala , Detlef Wotschke, On measuring nondeterminism in regular languages, Information and Computation, v.86 n.2, p.179-194, June 1990 [doi>10.1016/0890-5401(90)90053-K]
• 20: Jonathan Goldstine , Hing Leung , Detlef Wotschke, On the relation between ambiguity and nondeterminism in finite automata, Information and Computation, v.100 n.2, p.261-270, Oct. 1992 [doi>10.1016/0890-5401(92)90014-7]
• 21: [21] J. Hartmanis and R.E. Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285-306, 1965.
• 22: Lane A. Hemaspaandra , Sudhir K. Jha, Defying upward and downward separation, Information and Computation, v.121 n.1, p.1-13, Aug. 15, 1995 [doi>10.1006/inco.1995.1119]
• 23: [23] R. Impagliazzo and M. Naor. Decision trees and downward closures. In Proceedings 3rd Structure in Complexity Theory Conference, pages 29-38. IEEE, 1988.
• 24: Chandra Mohan Rao Kintala, Computations with a restricted number of nondeterministic steps., The Pennsylvania State University, 1977
• 25: [25] C.M.R. Kintala and P. Fischer. Refining nondeterminism in relativized complexity classes. SIAM Journal on Computing, 13:329-337, 1984.
• 26: [26] C.M.R. Kintala and D. Wotschke. Amounts of nondeterminism in finite automata. Acta Informatica, 13:199-204, 1980.
• 27: Ker-I Ko, On helping by robust oracle machines, Theoretical Computer Science, v.52 n.1-2, p.15-36, May 1987 [doi>10.1016/0304-3975(87)90078-8]
• 28: Hing Leung, On Finite Automata with Limited Nondeterminism, Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science, p.355-363, August 24-28, 1992
• 29: [29] A. Meyer and M. Fischer. Economics of description by automata, grammars and formal systems. In Proceedings of 12th SWAT Symposium, pages 188-191, 1988.
• 30: [30] C.H. Papadimitriou and M. Yannakakis. On limited nondeterminism and the complexity of the V-C dimension. In Proceedings 8th Structure in Complexity Theory Conference, pages 12-18. IEEE, 1993.
• 31: [31] V.R. Pratt. Every prime has a succinct certificate. SIAM J. Comp., 4:214-220, 1975.
• 32: Kai Salomaa , Sheng Yu, Degrees of Nondeterminism for Pushdown Automata, Proceedings of the 8th International Symposium on Fundamentals of Computation Theory, p.380-389, September 09-13, 1991
• 33: [33] K. Salomaa and S. Yu. Limited nondeterminism for pushdown automata. Bulletin of the EATCS, 50, 1993.
• 34: [34] L. Sanchis. Constructing language instances based on partial information. Int. Journal of Foundations of Computer Science, 5, 1994.
• 35: [35] I. Simon. The nondeterministic complexity of a finite automaton. In M. Lothaire, editor, Mots - mélanges offerts à M.P. Schützenberger, pages 384-400. Hermes, Paris, 1990.
• 36: Robert Szelepcs\{e}nyi, \beta_k-Complete Problems and Greediness, University of Rochester, Rochester, NY, 1993
• 37: [37] D. Vermeir and W. Savitch. On the amount of nondeterminism in pushdown automata. Fundamenta Informaticae, 4:401-418, 1981.
• 38: Marty J. Wolf, Nondeterministic circuits, space complexity and quasigroups, Theoretical Computer Science, v.125 n.2, p.295-313, March 28, 1994 [doi>10.1016/0304-3975(92)00014-I]

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:
  G. Mathematics of Computing

General Terms:
Algorithms, Theory