SACS | Instruction Sequence Based Non-uniform Complexity Classes

Published in Volume XXIV, Issue 1, 2014, pages 47-89, doi: 10.7561/SACS.2014.1.47

Authors: J.A. Bergstra, C.A. Middelburg

Abstract

We present an approach to non-uniform complexity in which single-pass instruction sequences play a key part, and answer various questions that arise from this approach. We introduce several kinds of non-uniform complexity classes. One kind includes a counterpart of the well-known non-uniform complexity class P/poly and another kind includes a counterpart of the well-known non-uniform complexity class NP/poly. Moreover, we introduce a general notion of completeness for the non-uniform complexity classes of the latter kind. We also formulate a counterpart of the well-known complexity theoretic conjecture that NP $notsubseteq$ P/poly. We think that the presented approach opens up an additional way of investigating issues concerning non-uniform complexity.

Full Text (PDF)

References

[1] S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge, 2009.

[2] J. L. Balcázar, J. Díaz, and J. Gabarró. Uniform characterizations of non-uniform complexity measures. Information and Control, 67(1):53– 69, 1985. http://dx.doi.org/10.1016/S0019-9958(85)80026-7 .

[3] J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I, volume 11 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, 1988.

[4] A. M. Ben-Amram, N. D. Jones, and L. Kristiansen. Linear, polynomial or exponential? Complexity inference in polynomial time. In A. Beckmann, C. Dimitracopoulos, and B. Lo¨we, editors, CiE 2008, volume 5028 of Lecture Notes in Computer Science, pages 67–76. Springer-Verlag, 2008. http://dx.doi.org/10.1007/978-3-540-69407-6_7 .

[5] J. A. Bergstra and M. E. Loots. Program algebra for sequential code. Journal of Logic and Algebraic Programming, 51(2):125–156, 2002. http://dx.doi.org/10.1016/S1567-8326(02)00018-8 .

[6] J. A. Bergstra and C. A. Middelburg. Distributed strategic interleaving with load balancing. Future Generation Computer Systems, 24(6):530– 548, 2008. http://dx.doi.org/10.1016/j.future.2007.08.001 .

[7] J. A. Bergstra and C. A. Middelburg. Instruction sequences and non- uniform complexity theory. arXiv:0809.0352v3 [cs.CC], July 2010.

[8] J. A. Bergstra and C. A. Middelburg. Indirect jumps improve instruction sequence performance. Scientific Annals of Computer Science, 22(2):253– 265, 2012. http://dx.doi.org/10.7561/SACS.2012.2.253 .

[9] J. A. Bergstra and C. A. Middelburg. Instruction sequence processing operators. Acta Informatica, 49(3):139–172, 2012. http://dx.doi.org/10.1007/s00236-012-0154-2 .

[10] J. A. Bergstra and C. A. Middelburg. Instruction Sequences for Computer Science, volume 2 of Atlantis Studies in Computing. Atlantis Press, Amsterdam, 2012.

[11] J. A. Bergstra and C. A. Middelburg. On the expressiveness of single- pass instruction sequences. Theory of Computing Systems, 50(2):313– 328, 2012. http://dx.doi.org/10.1007/s00224-010-9301-8 .

[12] J. A. Bergstra and A. Ponse. An instruction sequence semigroup with involutive anti-automorphisms. Scientific Annals of Computer Science, 19:57–92, 2009.

[13] A. Borodin, D. Dolev, F. E. Fich, and W. Paul. Bounds for width two branching programs. SIAM Journal of Computing, 15(2):549–560, 1986. http://dx.doi.org/10.1137/0215040 .

[14] S. A. Cook. The complexity of theorem-proving procedures. In Proceedings of STOC ’71, pages 151–158. ACM Press, 1971. http://dx.doi.org/10.1145/800157.805047 .

[15] O. Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge, 2008.

[16] G. B. Goodrich, R. E. Ladner, and M. J. Fischer. Straight-line programs to compute finite languages. In Conference on Theoretical Computer Science, Waterloo, pages 221–229, 1977.

[17] R. M. Karp and R. J. Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of STOC ’80, pages 302–309. ACM Press, 1980. http://dx.doi.org/10.1145/800141.804678 .

[18] L. Kristiansen and K.-H. Niggl. On the computational complexity of imperative programming languages. Theoretical Computer Science, 318(1–2):139–161, 2004. http://dx.doi.org/10.1016/j.tcs.2003.10.016 .

[19] A. R. Meyer and D. M. Ritchie. The complexity of loop programs. In S. Rosenthal, editor, 22nd ACM National Conference, pages 465–469. ACM Press, 1967. http://dx.doi.org/10.1145/800196.806014 .

[20] K.-H. Niggl and H. Wunderlich. Certifying polynomial time and linear/polynomial space for imperative programs. SIAM Journal of Computing, 35(5):1122–1147, 2006. http://dx.doi.org/10.1137/S0097539704445597 .

[21] A. Ponse and M. B. van der Zwaag. An introduction to program and thread algebra. In A. Beckmann et al., editors, CiE 2006, volume 3988 of Lecture Notes in Computer Science, pages 445–458. Springer-Verlag, 2006. http://dx.doi.org/10.1007/11780342_46 .

[22] S. Skyum and L. G. Valiant. A complexity theory based on boolean algebra. Journal of the ACM, 32(2):484–502, 1985. http://dx.doi.org/10.1145/3149.3158 .

[23] T. Thierauf. The Computational Complexity of Equivalence and Isomorphism Problems, volume 1852 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2000.

[24] I. Wegener. Branching Programs and Binary Decision Diagrams – Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications. SIAM, 2000. http://dx.doi.org/10.1137/1.9780898719789 .

[25] C. K. Yap. Some consequences of non-uniform conditions on uniform classes. Theoretical Computer Science, 26(3):287–300, 1983. http://dx.doi.org/10.1016/0304-3975(83)90020-8 .

Bibtex

@article{sacscuza:bergstra2014isbncc,
  title={Instruction Sequence Based Non-uniform Complexity Classes},
  author={J.A. Bergstra and C.A. Middelburg},
  journal={Scientific Annals of Computer Science},
  volume={24},
  number={1},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2014},
  pages={47--89},
  doi={10.7561/SACS.2014.1.47},
  publisher={``A.I. Cuza'' University Press}
}