16 отношения: NP-полная задача, Кубит, Класс сложности, Оптимизация (математика), Алгоритм Гровера, Недетерминированная машина Тьюринга, Равенство классов P и NP, Хопкрофт, Джон, Экспонента, Машина Тьюринга, Задача разрешимости, Задача выполнимости булевых формул, Задача коммивояжёра, Задача о клике, Дробь (математика), 1 год.
NP-полная задача
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).
Новый!!: Класс NP и NP-полная задача · Узнать больше »
Кубит
Представление кубита в виде сферы Блоха (en:Bloch sphere). Амплитуды вероятностей в тексте считаются как A.
Новый!!: Класс NP и Кубит · Узнать больше »
Класс сложности
В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления.
Новый!!: Класс NP и Класс сложности · Узнать больше »
Оптимизация (математика)
Оптимизация — в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.
Новый!!: Класс NP и Оптимизация (математика) · Узнать больше »
Алгоритм Гровера
Алгоритм Гровера Алгоритм Гровера (Grover search algorithm, GSA) — квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения где f есть булева функция от n переменных.
Новый!!: Класс NP и Алгоритм Гровера · Узнать больше »
Недетерминированная машина Тьюринга
В теоретической информатике недетерминированная машина Тьюринга — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат.
Новый!!: Класс NP и Недетерминированная машина Тьюринга · Узнать больше »
Равенство классов P и NP
Вопрос о равенстве классов сложности ''P'' и ''NP'' (в русских источниках также известный как проблема перебора) — это одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий.
Новый!!: Класс NP и Равенство классов P и NP · Узнать больше »
Хопкрофт, Джон
Джон Эдвард Хопкрофт (John Edward Hopcroft, 7 октября 1939 года, Сиэтл, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга.
Новый!!: Класс NP и Хопкрофт, Джон · Узнать больше »
Экспонента
График экспоненты y.
Новый!!: Класс NP и Экспонента · Узнать больше »
Машина Тьюринга
Художественное представление машины Тьюринга Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина).
Новый!!: Класс NP и Машина Тьюринга · Узнать больше »
Задача разрешимости
Задача разрешимости (проблема разрешимости) — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно, зависящего от значений некоторых входных параметров.
Новый!!: Класс NP и Задача разрешимости · Узнать больше »
Задача выполнимости булевых формул
Зада́ча выполни́мости бу́левых фо́рмул (SAT или ВЫП) — важная для теории вычислительной сложности алгоритмическая задача.
Новый!!: Класс NP и Задача выполнимости булевых формул · Узнать больше »
Задача коммивояжёра
43589145600 вариантов. Задача коммивояжёра (Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
Новый!!: Класс NP и Задача коммивояжёра · Узнать больше »
Задача о клике
Задача о клике относится к классу NP-полных задач в области теории графов.
Новый!!: Класс NP и Задача о клике · Узнать больше »
Дробь (математика)
Дробь в математике — число, состоящее из одной или нескольких частей (долей) единицы.
Новый!!: Класс NP и Дробь (математика) · Узнать больше »
1 год
Без описания.
Новый!!: Класс NP и 1 год · Узнать больше »