Formularless Logic Function

DOI: 10.4236/ojdm.2013.31005   PDF   HTML   XML   3,587 Downloads   5,570 Views  

Abstract

The concept of computability is defined more exactly and illustrated as an example of Boolean functions and cryptanalysis. To define a Boolean function is not necessary to record its formula. To do that the reduced (compact) description of values is determined in the truth table or in the statement of the problem. We obtain estimates of computation time, the volume of a compact descriptions and the range of variables under which it takes the value 0 or 1, depending polynomially on the number of arguments.

Share and Cite:

A. Teterin, "Formularless Logic Function," Open Journal of Discrete Mathematics, Vol. 3 No. 1, 2013, pp. 21-24. doi: 10.4236/ojdm.2013.31005.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] A. N. Teterin, “Classification on Bounded Sets,” Pattern Recognition and Image Analysis, Vol. 20, No. 4, 2010, pp. 564-572. doi:10.1134/S1054661810040188
[2] A. N. Teterin, “А Geometric Approach to Classification: New Model of the Operation of a Neuron,” Computational Mathematics and Mathematical Physics, Vol. 32, No. 12, 1992, pp. 1797-1805.
[3] E. M. Gold, “Language Identification in the Limit,” Information and Control, Vol. 10, No. 5, 1967, pp. 447-474. doi:10.1016/S0019-9958(67)91165-5
[4] M. Burgin, A. Klinger, Experience, “Generations, and Limits in Machine Learning,” Theoretical Computer Science, Vol. 317, No. 1-3, 2004, pp. 71-91. doi:10.1016/j.tcs.2003.12.005
[5] P. Orponen, “A Survey of Continuous-Time Computation Theory,” In: D.-Z. Du and K.-I. Ko, Eds., Advances in Algorithms, Languages, and Complexity, Springer, Berlin, 1997, рp. 209-224.
[6] C. Moore, “Recursion Theory on the Reals and Continuous-Time Computation,” Theoretical Computer Science, Vol. 162, No. 1, 1996, pp. 23-44. doi:10.1016/0304-3975(95)00248-0

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.