Хорошо известно, что вычисление недетерминированной машины Тьюринга (NTM) представляется в виде дерева конфигураций, основанного на начальной конфигурации. Любой переход в программе представлен ссылкой «отец-ребенок» в этом дереве.
Подобные деревья также могут быть построены для визуализации вычислений вероятностных и квантовых машин. (Обратите внимание, что для некоторых целей лучше не рассматривать связанный граф для квантовых вычислений в виде дерева, поскольку два узла, представляющих идентичные конфигурации на одном и том же уровне дерева, могут «компенсировать» друг друга из-за квантовых помех, но это не имеет ничего общего с настоящим вопросом.)
Конечно, детерминированные вычисления не такие; для каждого прогона детерминированной машины существует одна «ветка» в соответствующем «дереве».
Во всех трех упомянутых выше случаях то, что иногда делает эти вычисления «трудными» для детерминированных компьютеров, на самом деле вовсе не в том, что происходит ветвление, а в том, насколько много ветвлений присутствует в дереве. Например, недетерминированная машина Тьюринга с полиномиальным временем, которая гарантированно генерирует деревья вычислений, чьи «ширины» (то есть число узлов на самом переполненном уровне) также ограничены сверху полиномиальной функцией входного размера, может моделироваться полиномом детерминированный ТМ. (Обратите внимание, что это условие «полиномиальной ширины» эквивалентно ограничению NTM, чтобы сделать не более логарифмически ограниченного числа недетерминированных догадок.) То же самое верно, когда мы устанавливаем одинаковые границы ширины для вероятностных и квантовых вычислений.
Я знаю, что этот вопрос был подробно рассмотрен для недетерминированных вычислений. См., Например, опрос « Ограниченный недетерминизм », проведенный Голдсмитом, Леви и Мундхенком. Мой вопрос заключается в том, изучалось ли это явление «ограниченного ветвления» или «ограниченной ширины» в общей структуре, охватывающей все недетерминированные, вероятностные и квантовые модели? Если так, каково стандартное название для этого? Любые ссылки на ресурсы будут оценены.