Аннотация:В работе Родиона Хасанова исследуются вопросы сложности вычисления значений функций, реализуемых схемами из функциональных элементов. Ранее А.В.Чашкин предложил использовать для этих целей неветвящиеся программы и показал, что сложность вычисления значения функций с помощью неветвящихся программ экспоненциально зависит от числа переменных функции. С другой стороны Ю.С.Шуткиным было показано, что значение функции, представленной в виде контактной схемы, может быть вычислено за линейное время. Это позволяло надеяться, что при правильном выборе модели вычислений и для случая схем из функциональных элементов может быть получена линейная временная сложность.
. В работе Р.Хасановым было показано, что если в неветвящиеся программы добавить оператор условного перехода, то для любой булевой функции значение функции может быть вычислено за линейное время.
К сожалению, работа написана небрежно. В постановочной части нет строгого и полного описания предлагаемой модели. Доказательства требуют более детальной проработки. Результаты достаточно тривиальны. Не удалось получить точной (или асимптотически точной) оценки временной сложности.