Обсуждение:Класс сложности
Неточности терминологии[править код]
Все классы сложности находятся в иерархическом отношении: одни включают в себя другие. неясна смысловая нагрузка фразы. Кто куда вложен? Любые два класса сложности вложены? -- Это не верно. Некоторые классы сложности вложены? -- Это очевидно. В чем же смысл?
Языки, распознаваемые предикатами из некоторого класса (т.е. множества слов, на которых предикат возвращает 1), также называются принадлежащими тому же классу. "Языки, распознаваемые предикатами" -- редко встречающееся словосочетание. Язык распознается алгоритмом (машиной Тьюринга), а предикатом он задается или определяется. Можно сказать: "языки, являющиеся характеристическими множествами предикатов". Что значит "принадлежащими тому же классу"? Класс сложности содержит разнородные объекты -- предикаты и языки? На самом деле между языками и предикатами проводится отождествления. С точки зрения классов сложности считается, что предикат и язык это один и тот же объект.
Статью желательно переработать. На мой скромный взгляд, хорошо бы уменьшить количество рассуждений "вообще" и увеличить число упоминаемых классов сложности. Диаграмма классов, более-менее отражающая современную ситуацию в области, намного обширнее приведенной. Если же читатель хочет понять что такое класс сложности, то это лучше сделать на простом примере. Слава богу, всегда под рукой классы P и NP.
Кроме того, судя по названию, статья должна содержать информацию о любых классах сложности. Однако, ничего не сказано о классах сложности в неуниформных моделях (схемы из функциональных элементов), о классах Валианта и проч.