Более быстрый доступ, чем браузер!
36 отношения: APX, NP-полная задача, Simpsorama, Кубический граф, Кук, Стивен Артур, Класс NP, Класс PH, Комбинаторная оптимизация, Проблемы Смейла, Полуопределённое программирование, Перманент, Открытые математические проблемы, Односторонняя функция, Аппроксимационный алгоритм, Недетерминированная машина Тьюринга, Разборов, Александр Александрович, Сингх, Саймон, Сложность аппроксимации, Смейл, Стивен, Список эпизодов телесериала «4исла», Список эпизодов телесериала «Элементарно», Теория алгоритмов, Теорема Курселя, Футурама, Японский кроссворд, Изоморфизм графов, Информатика, Задача разбиения множества чисел, Вычислительная сложность, Временная сложность алгоритма, Гусеница (теория графов), Гипотеза (математика), Гипотеза об экспоненциальном времени, Двудольная размерность, Доминирующее множество, Левин, Леонид Анатольевич.
APX
APX (от англ. «approximable») в теории вычислительной сложности — это класс NP-трудных задач, для которых существуют аппроксимационные алгоритмы полиномиальной сложности с постоянным коэффициентом аппроксимации.
Новый!!: Равенство классов P и NP и APX · Узнать больше »
NP-полная задача
NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).
Новый!!: Равенство классов P и NP и NP-полная задача · Узнать больше »
Simpsorama
Simpsorama (Симпсорама) — шестой эпизод двадцать шестого сезона американского мультсериала «Симпсоны», является 558-м по счёту в сквозной нумерации.
Новый!!: Равенство классов P и NP и Simpsorama · Узнать больше »
Кубический граф
Граф Петерсена является кубическим. Полный двудольный граф K_3,3 является примером бикубического графа Кубический граф — граф, в котором все вершины имеют степень три.
Новый!!: Равенство классов P и NP и Кубический граф · Узнать больше »
Кук, Стивен Артур
Стивен Артур Кук (Stephen Arthur Cook, 14 декабря 1939 года, Буффало, США) — американский учёный в области теории вычислительных систем.
Новый!!: Равенство классов P и NP и Кук, Стивен Артур · Узнать больше »
Класс NP
В теории алгоритмов классом NP (от non-deterministic polynomial) называют множество проблем разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее полинома от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения).
Новый!!: Равенство классов P и NP и Класс NP · Узнать больше »
Класс PH
Класс сложности PH (от polynomial hierarchy) — объединение всех классов сложности из полиномиальной иерархии: Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит классу \Sigma^p_k или \Pi^p_k.
Новый!!: Равенство классов P и NP и Класс PH · Узнать больше »
Комбинаторная оптимизация
Комбинаторная оптимизация — область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности.
Новый!!: Равенство классов P и NP и Комбинаторная оптимизация · Узнать больше »
Проблемы Смейла
Проблемы Смейла — список из восемнадцати нерешённых математических проблем, предложенный Стивеном Смейлом в 2000 году.
Новый!!: Равенство классов P и NP и Проблемы Смейла · Узнать больше »
Полуопределённое программирование
Полуопределённое программирование (en: Semidefinite programming, SDP) — это подраздел, которое занимается оптимизацией линейной целевой функции (целевая функция — это заданная пользователем функция, значение которой пользователь хочет минимизировать или максимизировать) на пересечении конусов положительно полуопределённых матриц с аффинным пространством.
Новый!!: Равенство классов P и NP и Полуопределённое программирование · Узнать больше »
Перманент
В математике пермане́нт — числовая функция, определённая для матриц, для квадратных матриц похожая на детерминант, и отличающаяся от него лишь в том, что в разложении на перестановки (или на миноры) берутся не чередующиеся знаки, а все плюсы.
Новый!!: Равенство классов P и NP и Перманент · Узнать больше »
Открытые математические проблемы
Откры́тые (нерешённые) математи́ческие пробле́мы — задачи, которые рассматривались математиками, но до сих пор не решены.
Новый!!: Равенство классов P и NP и Открытые математические проблемы · Узнать больше »
Односторонняя функция
Односторонняя функция — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции.
Новый!!: Равенство классов P и NP и Односторонняя функция · Узнать больше »
Аппроксимационный алгоритм
В исследовании операций под аппроксимационным алгоритмом понимается алгоритм, использующийся для поиска приближённого решения оптимизационной задачи.
Новый!!: Равенство классов P и NP и Аппроксимационный алгоритм · Узнать больше »
Недетерминированная машина Тьюринга
В теоретической информатике недетерминированная машина Тьюринга — машина Тьюринга, функция перехода которой представляет собой недетерминированный конечный автомат.
Новый!!: Равенство классов P и NP и Недетерминированная машина Тьюринга · Узнать больше »
Разборов, Александр Александрович
Алекса́ндр Алекса́ндрович Разбо́ров (родился 16 февраля 1963 года в Белово Кемеровской обл.) — российский и советский учёный-математик, член-корреспондент РАН (с 2000 года), специалист в области теории вычислений.
Новый!!: Равенство классов P и NP и Разборов, Александр Александрович · Узнать больше »
Сингх, Саймон
Саймон Ле́хна Сингх (Simon Lehna Singh; 19 сентября 1964,, графство Сомерсет, Великобритания) — британский популяризатор науки, журналист и режиссёр-документалист.
Новый!!: Равенство классов P и NP и Сингх, Саймон · Узнать больше »
Сложность аппроксимации
В информатике сложность аппроксимации — это область изучения вычислительной сложности поиска решений задач оптимизации, близких к оптимальным.
Новый!!: Равенство классов P и NP и Сложность аппроксимации · Узнать больше »
Смейл, Стивен
Сти́вен Смейл (Stephen Smale) — американский, возглавлявший факультет математики Калифорнийского университета в Беркли в 1960—61 и 1964—95 годах, лауреат премии Филдса 1966 года.
Новый!!: Равенство классов P и NP и Смейл, Стивен · Узнать больше »
Список эпизодов телесериала «4исла»
link.
Новый!!: Равенство классов P и NP и Список эпизодов телесериала «4исла» · Узнать больше »
Список эпизодов телесериала «Элементарно»
Список эпизодов американского детективного телесериала «Элементарно», основанного на персонажах книг сэра Артура Конан Дойла о Шерлоке Холмсе, действие происходит в наши дни в Нью-Йорке.
Новый!!: Равенство классов P и NP и Список эпизодов телесериала «Элементарно» · Узнать больше »
Теория алгоритмов
Тео́рия алгори́тмов — наука, находящаяся на стыке математики и информатики, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления.
Новый!!: Равенство классов P и NP и Теория алгоритмов · Узнать больше »
Теорема Курселя
Теорема Курселя — утверждение о том, что любое свойство графа, определяемое в второго порядка, может быть установлено за линейное время на графах с ограниченной древесной шириной.
Новый!!: Равенство классов P и NP и Теорема Курселя · Узнать больше »
Футурама
«Футура́ма» (Futurama — игра слов от future — «будущее» и panorama — «панорама») — американский научно-фантастический сатирический мультсериал, созданный в студии «20th Century Fox» Мэттом Грейнингом (Matt Groening) и Дэвидом Коэном (David X. Cohen), авторами мультсериала «Симпсоны».
Новый!!: Равенство классов P и NP и Футурама · Узнать больше »
Японский кроссворд
Японский кроссворд «футбол» с анимацией процесса решения кроссворда Японская головоломка (также японский кроссворд, японское рисование, нонограмма) — головоломка, в которой, в отличие от обычных кроссвордов, зашифрованы не слова, а изображения.
Новый!!: Равенство классов P и NP и Японский кроссворд · Узнать больше »
Изоморфизм графов
В теории графов изоморфизмом графов G.
Новый!!: Равенство классов P и NP и Изоморфизм графов · Узнать больше »
Информатика
Информа́тика (Informatique; Computer science) — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.
Новый!!: Равенство классов P и NP и Информатика · Узнать больше »
Задача разбиения множества чисел
Задача разбиения множества чисел — это задача определения, можно ли данное мультимножество S положительных целых чисел разбить на два подмножества S1 и S2, таких, что сумма чисел из S1 равна сумме чисел из S2.
Новый!!: Равенство классов P и NP и Задача разбиения множества чисел · Узнать больше »
Вычислительная сложность
Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.
Новый!!: Равенство классов P и NP и Вычислительная сложность · Узнать больше »
Временная сложность алгоритма
В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные.
Новый!!: Равенство классов P и NP и Временная сложность алгоритма · Узнать больше »
Гусеница (теория графов)
Гусеница Гусеница или гусеничное дерево — это дерево, в котором все вершины находятся на расстоянии 1 от центрального пути.
Новый!!: Равенство классов P и NP и Гусеница (теория графов) · Узнать больше »
Гипотеза (математика)
Действительная (красный) и мнимая части (синий) дзета-функции Римана на критической прямой \mathrmRe(z).
Новый!!: Равенство классов P и NP и Гипотеза (математика) · Узнать больше »
Гипотеза об экспоненциальном времени
Гипотеза об экспоненциальном времени — это недоказанное, которое сформулировали Импальяццо и Патури.
Новый!!: Равенство классов P и NP и Гипотеза об экспоненциальном времени · Узнать больше »
Двудольная размерность
В теории графов и комбинаторной оптимизации двудольная размерность или число бикликового покрытия графа G .
Новый!!: Равенство классов P и NP и Двудольная размерность · Узнать больше »
Доминирующее множество
Доминирующее множество (красные вершины). В теории графов доминирующее множество для графа G.
Новый!!: Равенство классов P и NP и Доминирующее множество · Узнать больше »
Левин, Леонид Анатольевич
Леони́д Анато́льевич Ле́вин (род. 2 ноября 1948, Днепропетровск) — советский и американский, специалист в области теории вычислительной сложности.
Новый!!: Равенство классов P и NP и Левин, Леонид Анатольевич · Узнать больше »
Перенаправления здесь:
P != NP, P = NP, P vs. NP, P ≠ NP, P!=NP, P=NP, P≠NP, Проблема перебора.
