Проще всего взять разницу между детерминированной и недетерминированной машиной тьюринга(или другим автоматом).

Недетерминированная машина с помощью «подкидывания монетки»(то есть недетерминированного перехода) может не вычислять все возможные состояния(а значит и такты), ей может повезти, и она окажется на решении ранее, нежели она переберет все возможные ходы. Для детерминированной машины необходимо вычислить все ветви, а соответственно, мы получаем разницу между ворзможностью везения(и соответственно уменьшения числа тактов) и полным перебором. Иными словами, стандартный случай для детерминированной машины будет наихудшим случаем для недетерминированной. Отсюда вытекает неэквивалентность

Перемещено tailgunner из development