Аннотация:Давыдовым Ф.Г. была рассмотрена классическая задача 3-ВЫП на выполнимость функции заданной в конъюктивно нормальной форме, где каждый дизъюнкт состоит из трех литералов. Как известно, данная задача является NP-полной, а значит к ней сводятся такие практически значимые трудно решаемые задачи как задача коммивояжера, проблема Штейнера, проблема раскраски графа, задача о независимом множестве и вершинном покрытии и другие.
Автором были изучены различные подходы к точному и приближенному решению данной задачи, выделены и проанализированы их сильные и слабые стороны.