Войти
В теории сложности вычислений, листовой язык - это метод характеристики класса сложности путем формализации того, что означает для машины «принять» ввод.
Несколько классов сложности обычно определяются в терминах полиномиального времени недетерминированной машины Тьюринга, где каждая ветвь может принимать или отклонять, а вся машина принимает или отвергает как некоторую функцию условий филиалов. Например, недетерминированная машина Тьюринга принимает, если хотя бы одна ветвь принимает, и отклоняет, только если все ветки отклоняют. A, с другой стороны, принимает, только если все ветви принимают, и отклоняет, если какая-либо ветвь отклоняет. Таким образом можно определить многие классы.
Затем мы можем формализовать это, исследуя формальный язык, связанный с каждым условием принятия. Мы предполагаем, что дерево упорядочено, и считываем строки принятия / отклонения с листьев дерева вычислений. Например, недетерминированная машина примет , если и только если конечная строка находится на языке {0, 1} 1 {0, 1}, и отклонит, если конечная строка находится на языке 0.
