Аннотация:
В работе схематично доказывается интуитивно понятный факт о соответствии полиномиальной сложности СФЭ в базисе из штриха Шеффера полиномиальному числу шагов машины Тьюринга. Приведены числовые оценки.
Ключевые слова:сложность схемы, штрих Шеффера, машина Тьюринга.
Полный текст:
PDF файл (222 kB)