Blum axioms and nondeterministic computation of functions

• Tiago Royer UFSC
• Jerusa Marchi UFSC

Resumo

In his doctoral thesis, Manuel Blum proposed two axioms for complexity measures that allows us to talk about complexity in an axiomatic manner. His axioms does not even specify the machine model — it just requires it to satisfy some properties. Blum axioms, however, are defined in the context of function computation. This restriction is easy to implement with deterministic machines, since there is only one output for a given input, but how can a nondeterministic Turing machine compute a function? This paper surveys techniques to associate nondeterministic machines with functions and analyze how they interact with computational complexity.

Referências

Arora, S. and Barak, B. (2009). Computational Complexity - A Modern Approach. Cambridge University Press.

Blum, M. (1967). A machine-independent theory of the complexity of recursive functions. J. ACM, 14(2):322–336.

Gasarch,W. I. (2012). Guest column: the second P =? NP poll. SIGACT News, 43(2):53–77.

Goldreich, O. (2008). Computational complexity - a conceptual perspective. Cambridge University Press.

Hopcroft, J. E. and Ullman, J. D. (1979). Introduction to Automata Theory, Languages and Computation. Addison-Wesley.

Kozen, D. (2006). Theory of Computation. Texts in Computer Science. Springer.

Krentel, M. W. (1988). The complexity of optimization problems. Journal of Computer and System Sciences, 36(3):490 – 509.

Papadimitriou, C. H. (1994). Computational complexity. Addison-Wesley.

Rogers, Jr., H. (1987). Theory of recursive functions and effective computability (Reprint from 1967). MIT Press, Cambridge, MA, USA.

Selman, A. L. (1994). A taxonomy of complexity classes of functions. Journal of Computer and System Sciences, 48(2):357–381.

Valiant, L. G. (1979). The complexity of computing the permanent. Theoretical Computer Science, 8:189–201.