8 отношения: «O» большое и «o» малое, NP-полная задача, Тезис Чёрча — Тьюринга, Хопкрофт, Джон, Эйлеров цикл, Задача коммивояжёра, Дискретное логарифмирование, 2002 год.
«O» большое и «o» малое
«O» большое и «o» малое (O и o) — математические обозначения для сравнения асимптотического поведения (асимптотики) функций.
Новый!!: Класс P и «O» большое и «o» малое · Узнать больше »
NP-полная задача
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).
Новый!!: Класс P и NP-полная задача · Узнать больше »
Тезис Чёрча — Тьюринга
Те́зис Чёрча — Тью́ринга — это гипотеза, постулирующая эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга.
Новый!!: Класс P и Тезис Чёрча — Тьюринга · Узнать больше »
Хопкрофт, Джон
Джон Эдвард Хопкрофт (John Edward Hopcroft, 7 октября 1939 года, Сиэтл, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга.
Новый!!: Класс P и Хопкрофт, Джон · Узнать больше »
Эйлеров цикл
Граф Кёнигсбергских мостов. Этот граф не является эйлеровым, поэтому решения не существует. Каждая вершина этого графа имеет чётную степень, поэтому этот граф — эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл. Эйлеров путь (эйлерова цепь) в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Новый!!: Класс P и Эйлеров цикл · Узнать больше »
Задача коммивояжёра
43589145600 вариантов. Задача коммивояжёра (Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
Новый!!: Класс P и Задача коммивояжёра · Узнать больше »
Дискретное логарифмирование
Дискретное логарифмирование (DLOG) — задача обращения функции g^x в некоторой конечной мультипликативной группе G. Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем.
Новый!!: Класс P и Дискретное логарифмирование · Узнать больше »
2002 год
В связи с 500-летием со дня смерти Дионисия решением ЮНЕСКО 2002 год назван годом Дионисия.
Новый!!: Класс P и 2002 год · Узнать больше »
Перенаправления здесь:
Полиномиальная сложность, Полиномиальное время, Полиномиальный алгоритм.