Leaf language is a method in

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

for characterizing a

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

by formalizing what it means for a machine to "accept" an input. Complexity classes are typically defined in terms of a

polynomial-time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

nondeterministic Turing machine In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...

(NTM). These machines possess multiple computational paths, and the outcomes of these paths determine whether an input is accepted or rejected. Traditionally, an NTM accepts an input if at least one path accepts it, and rejects it only if all paths reject it. In contrast, a co-Nondeterministic Turing Machine (co-NTM) accepts an input only if all paths accept it, and rejects it if any path rejects it. Moreover, more complex notions of acceptance can also be defined. To formalize the characterization of a complexity class, one can examine the

formal language In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet". The alphabet of a formal language consists of symbols that concatenate into strings (also c ...

associated with each acceptance condition. This involves assuming an ordered tree, and reading the accepted/rejected strings from the leaves of the computation tree. NTMs will accept if the leaf string is in the language , and will reject if the leaf string is in the language .

References

{{Reflist Computational complexity theory