Аннотация:Проблема P=NP остается открытой многие годы и возникает вопрос: может ли параллельное (автоматное, нейросетевое) или приближенное вычисление позволить решать задачи класса NP за приемлемое время.
Давыдов Ф.Г. рассмотрел классическую NP-полную задачу 3-ВЫП, проверки на выполнимость (наличие единицы в таблице истинности) функции по ее формуле, записанной в форме 3-КНФ, то есть конъюнкции некоторого количества дизъюнктов состоящих ровно из трех литералов (литерал, это символ переменной или его отрицание).
Федору удалось построить множество из 2^n универсальных структурных автоматов, определяющих выполнимость формулы от n переменных, записанной в форме 3-КНФ из m дизъюнктов. Были оценены такие параметры как сложность схемы автомата (количество элементов) и время работы (количество тактов, необходимое для получение ответа о выполнимости формулы на выходе автомата). Оказалось, что в зависимости от параметра k=1,…,2^n, время вычисления можно уменьшить в k раз (по сравнению с алгоритмом полного перебора значений x1,…,xn), но при этом сложность предложенной схемы возрастает также в k раз.