Blum axioms and nondeterministic computation of functions - Royer, Tiago; Marchi, Jerusa (Anais do Concurso de Trabalhos de Iniciação Científica da SBC (CTIC-SBC); 2016: Anais do XXXV Concurso de Trabalhos de Iniciação Científica da SBC, 2016)
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.