все они эквивалентны. Если бы мы научились решать одну из них за полиномиальное время, то мы бы смогли решить все задачи данного класса за промежуток времени того же порядка величины.
Напомним два других свойства 
-полных задач: мы не знаем, являются ли они неполиномиальными, и не знаем для их решения детерминированного полиномиально ограниченного алгоритма.
Рис. 4.9. Пример сортировки первого типа.
Приведем для примера несколько доказательств эквивалентности.
Идея состоит в том, чтобы перевести задачу из одного класса задач в другой. Трудность заключается в том, что мы не умеем как следует решать основную задачу — задачу логической разрешимости. Но принципы моделирования и преобразования условий могут успешно использоваться в конкретных случаях.
В действительности при изучении этих проблем никогда не следует упускать из виду, что даже если теоретическая принадлежность некоторой общей задачи 
к классу 
-полных доказана, любая конкретная задача с уточненными данными может быть все-таки решена. Не является невозможным решение этой уточненной задачи за полиномиальное время. Единственное, что утверждает теория: для общего случая не существует единого полиномиального алгоритма.
одновременно устанавливается отношение сводимости 
логическая разрешимость”. Но отношение сводимости является транзитивным. Поэтому если нам удастся доказать, что логическая разрешимость сводима к некоторой задаче 
которая сама сводится к 
то мы получим класс эквивалентных задач.
-полной в том и только в том случае, если она является NP-полной и попадает в класс 
сегодня кажется невероятным. Для большинства действительно сложных классических задач была доказана принадлежность к классу 
-сложных. Но, что еще более удивительно, почти все они попадают в класс 
т. е. являются NP-полными, и, следовательно, в этом смысле
