Обсуждение:Класс P

Материал из Википедии — свободной энциклопедии

[править] Проблемы с терминологией

Неверно называть класс P классом алгоритмов. Это класс языков (или задач распознавания). Algo

[править] Еще проблемы

Теория алгоритмов ничего не говорит о классе P. Обычно теорией алгоритмов называют раздел математики занимающийся качественными (а не сложностными) свойствами задач. Например, теория алгоритмов ведает вопросами алгоритмической разрешимости. Классами сложности (P, NP и проч.) занимается теория сложности.

Определение машины Тьюринга лучше вынести в отдельную статью. Желательно заметить, что выбор машины Тьюринга, как средства вычисления совершенно не принципиален. Тот же самый класс получается для других известных вычислителей: нормальный алгоритм Маркова, машина Поста и др. -- снимается.

В целом статье сильно не достает формальности. Слишком формальная статья -- тоже плохо, но статья по математике, изложенная вольным стилем, не годится. Algo

[править] Еще

Алгоритмы, принадлежащие классу P, считаются быстрыми. Сомнительно. Скорее это алгоритмы которые можно надеяться применить на практике (практически реализуемые).

время работы которых не слишком сильно зависит от размера входных данных . Что значит "не слишком сильно зависит"? Видимо имелось ввиду, "не слишком быстро возрастает с возрастанием размера входных данных".

Алгоритм отождествляется с детерминированной машиной Тьюринга . Правильнее сказать: "алгоритмом называется ...".

Ни здесь, ни в статье о машинах Тьюринга ничего не сказано о том, что значит "машина вычисляет функцию".

Спутаны понятия сложности функции и сложности алгоритма. То что, по непонятным мне причинам, обозначено через , является сложностью алгоритма и обычно обозначается через .

Функции общего вида: в принципе не могут принадлежать классу P. Класс P -- класс задач распознавания. Далее говорится, что такое определение является более общим (расширенным), однако, лучше функции, вычислимые за полиномиальное время, так и называть -- "вычислимыми за полиномиальное время", а класс P оставить классом языков.

Большинство алгоритмов, лежащих в классе P, имеют сложность, не превосходящую многочлен небольшой степени от размера входных данных . Правильно было бы сказать "большинство известных задач" или "большинство практических задач".

Степень многочлена редко бывает большой. Это уже совсем не годится. Нужно либо убрать, либо существенно переработать, иначе мысль не воспринимается, хотя понятно, что автор имел в виду нечто содержательное.

...взятия остатка от деления, перемножения матриц, выяснение связности графов и некоторые другие. "Некоторые другие" -- это то, что было перечислено. Все, что осталось -- это "многие другие".

Algo 14:11, 26 сентября 2006 (UTC)