Combined complexity classes for finite functions

Y. Breitbart; F. D. Lewis

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1979)

  • Volume: 13, Issue: 1, page 87-97
  • ISSN: 0988-3754

How to cite

top

Breitbart, Y., and Lewis, F. D.. "Combined complexity classes for finite functions." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 13.1 (1979): 87-97. <http://eudml.org/doc/92092>.

@article{Breitbart1979,
author = {Breitbart, Y., Lewis, F. D.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {complexity classes of finite functions; representations of Boolean functions by tables; computational complexity},
language = {eng},
number = {1},
pages = {87-97},
publisher = {EDP-Sciences},
title = {Combined complexity classes for finite functions},
url = {http://eudml.org/doc/92092},
volume = {13},
year = {1979},
}

TY - JOUR
AU - Breitbart, Y.
AU - Lewis, F. D.
TI - Combined complexity classes for finite functions
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1979
PB - EDP-Sciences
VL - 13
IS - 1
SP - 87
EP - 97
LA - eng
KW - complexity classes of finite functions; representations of Boolean functions by tables; computational complexity
UR - http://eudml.org/doc/92092
ER -

References

top
  1. 1. Ya. M. BARZDIN, The Complexity of Programs Recongizing Finite Subsets of Recursively Enumerable Sets, Doklady Akad. Nauk, Vol. 182, 1968, pp. 1249-1252 (in Russian). Zbl0193.31601MR236009
  2. 2. Y. BREITBART, Tape Complexity of the Predicate to be a Complex Boolean Function, in preparation. 
  3. 3. J. HARTMANIS and R. E. STEARNS, On the Computational Complexity of Algorithms, Trans. Amer. Math. Soc., 117, 1965, pp. 285-306. Zbl0131.15404MR170805
  4. 4. J. E. HOPCROFT and J. D. ULLMAN, Formal Languages and their Relation to Automata, Addison-Wesley, 1969. Zbl0196.01701MR237243
  5. 5. M. I. KANOVICH and N. V. PETRISome Theorems About Complexity of Normal Algorithms and Computations, Dokl. Akad Nauk, S.S.S.R., Vol. 184, No. 6, 1969, pp. 1275-1276 (in Russian). Zbl0181.31303MR242676
  6. 6. V. KUZMIN, Evaluation of Boolean Functions by Finite Automata, Normal Algorithms, and Turing Machines, Prob. of Cybernetics, Vol. 13, 1965, pp. 75-96. MR199062
  7. 7. F. D. LEWIS, Classes of Recursive Functions and Their Index Sets, Zeit. f. Math. Logiku. Grund. d. Math., Vol. 17, 1971. Zbl0229.02035MR294130
  8. 8. F. D. LEWIS, The Enumerability and Invariance of Complexity Classes, J. Comp. System Sc., Vol. 5, 1971, pp. 286-303. Zbl0215.04701MR278951
  9. 9. O. B. LUPANOV, Ob odnom Methode Syntesa Schm, Izv. VUS'ov Radiofizika, Vol. 1, 1958, pp. 120-140. 
  10. 10. O. B. LUPANOV, One Approach to Synthesis of Control Systems-Principle of Local Coding, Prob. of Cybernetics, Vol. 14, 1965, pp. 31-110. Zbl0256.94043MR201219
  11. 11. A. A. MARKOV, Normal Algorithms for Computation of Boolean Functions, Izv. Akad.Nauk, S.S.S.R., Vol. 31, 1967, pp. 161 (in Russian). Zbl0148.24803MR210587
  12. 12. N. V. PETRI, On Algorithms Related to Predicate and Boolean Functions, Dokl. Akad Nauk, S.S.S.R., Vol. 185, No. 1, 1969, pp. 37-39 (in Russian). Zbl0193.31501MR250881
  13. 13. N. PIPPENGER, The Realization of Monotone Boolean Functions, A.C.M. Sym. on Theory of Comp., 1976, pp. 204-211. Zbl0366.94050MR434654
  14. 14. H. Jr. ROGERS, Theory of Recursive Functions and Effective Computability, McGraw-Hill, NY, 1967. Zbl0183.01401MR224462
  15. 15. J. SAVAGE, The Complexity of Computing, 1976, Wiley and Sons, NY. Zbl0391.68025MR495205
  16. 16. C. P. SCHNORR, The Network Complexity and the Turing Machine Complexity of Finite Functions, Acta Infor., Vol. 7, 1976, pp. 95-107. Zbl0338.02019MR421889
  17. 17. L. A. SHOLOMOV, Information Complexity Problems of Minimal Realization of Boolean Functions by Combinational Schemas, Prob. of Cybernetics, Vol. 26, 1973, pp. 207-256. 
  18. 18. B. A. TRACHTENBROT, On Problems Solvable by Successive Trials, Math. Found. of Comp. Sc., 1975 (Lect. Notes in Comp. Science n° 32, Springer-Verlag, pp. 125-137). Zbl0357.68060MR395329
  19. 19. S. V. YABLONSKI, On Algorithmic Difficulties in Synthesis of Minimal Schemas, Prob. of Cybernetics, Vol. 2, 1959, pp. 75-121. MR129088

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.