Логотип
Юнионпедия
Связь
Доступно в Google Play
Новый! Скачать Юнионпедия на вашем Android™ устройстве!
Свободно
Более быстрый доступ, чем браузер!
 

Равенство классов P и NP

Индекс Равенство классов P и NP

Вопрос о равенстве классов сложности ''P'' и ''NP'' (в русских источниках также известный как проблема перебора) — это одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий.

35 отношения: Hashcash, Hewlett-Packard, Minecraft, NP-полная задача, RSA, Кук, Стивен Артур, Класс NP, Класс P, Пало-Алто, ПостНаука, Полный перебор, Открытые математические проблемы, Ааронсон, Скотт, Алгебраическая сложность, Нейман, Джон фон, Разборов, Александр Александрович, Стюарт, Иэн (математик), Стросс, Чарльз, Тьюринг, Алан, Технический университет Эйндховена, Футурама, Хопкрофт, Джон, Элементарно, Математический институт Клэя, Майнинг, Московский центр непрерывного математического образования, Биткойн, Вычислительная сложность, Временная сложность алгоритма, Гёдель, Курт, Доказательство выполнения работы, Левин, Леонид Анатольевич, 1971 год, 1973 год, 2002 год.

Hashcash

Hashcash — система доказательства правильности работы, используемая с целью уменьшения количества спама и DoS-атак.

Новый!!: Равенство классов P и NP и Hashcash · Узнать больше »

Hewlett-Packard

Hewlett-Packard (HP, Хью́летт-Па́ккард) — одна из крупнейших американских компаний в сфере информационных технологий, существовавшая в период 1939—2015 годов, поставщик аппаратного и программного обеспечения для организаций и индивидуальных потребителей.

Новый!!: Равенство классов P и NP и Hewlett-Packard · Узнать больше »

Minecraft

Minecraft (от mine — «шахта», «добывать» и craft — «ремесло») — компьютерная инди-игра в жанре песочницы с элементами симулятора выживания и открытым миром, разработанная шведским программистом Маркусом Перссоном, известным также как «Notch», и позже выпускаемая основанной Маркусом Персоном компанией Mojang.

Новый!!: Равенство классов P и NP и Minecraft · Узнать больше »

NP-полная задача

NP-полная задача — в теории алгоритмов задача с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время (то есть при помощи операций, число которых не превышает некоторого полинома в зависимости от размера исходных данных).

Новый!!: Равенство классов P и NP и NP-полная задача · Узнать больше »

RSA

RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.

Новый!!: Равенство классов P и NP и RSA · Узнать больше »

Кук, Стивен Артур

Стивен Артур Кук (Stephen Arthur Cook, 14 декабря 1939 года, Буффало, США) — американский учёный в области теории вычислительных систем.

Новый!!: Равенство классов P и NP и Кук, Стивен Артур · Узнать больше »

Класс NP

В теории алгоритмов классом NP (от non-deterministic polynomial) называют множество проблем разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее полинома от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения).

Новый!!: Равенство классов P и NP и Класс NP · Узнать больше »

Класс P

В теории алгоритмов классом P (от polynomial) называют множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных).

Новый!!: Равенство классов P и NP и Класс P · Узнать больше »

Пало-Алто

Па́ло-А́лто, Па́ло-А́льто (Palo Alto, произносится) — город в округе Санта-Клара, штат Калифорния, США.

Новый!!: Равенство классов P и NP и Пало-Алто · Узнать больше »

ПостНаука

ПостНаука — интернет-журнал о современной фундаментальной науке и учёных, которые её создают, о популяризации научных знаний.

Новый!!: Равенство классов P и NP и ПостНаука · Узнать больше »

Полный перебор

Полный перебор (или метод «грубой силы», brute force) — метод решения математических задач.

Новый!!: Равенство классов P и NP и Полный перебор · Узнать больше »

Открытые математические проблемы

Откры́тые (нерешённые) математи́ческие пробле́мы — задачи, которые рассматривались математиками, но до сих пор не решены.

Новый!!: Равенство классов P и NP и Открытые математические проблемы · Узнать больше »

Ааронсон, Скотт

Скотт Джоэл Ааронсон (Scott Joel Aaronson) — специалист в области теории вычислительных машин и систем, преподаватель факультета электротехники и информатики Массачусетского технологического института.

Новый!!: Равенство классов P и NP и Ааронсон, Скотт · Узнать больше »

Алгебраическая сложность

Алгебраическая сложность — раздел теории сложности вычислений, имеющий дело с полиномами.

Новый!!: Равенство классов P и NP и Алгебраическая сложность · Узнать больше »

Нейман, Джон фон

Джон фон Не́йман (John von Neumann; или Иоганн фон Нейман, Johann von Neumann; при рождении Я́нош Ла́йош Нейман,, IPA:; 28 декабря 1903, Будапешт — 8 февраля 1957, Вашингтон) — венгеро-американский математик еврейского происхождения, сделавший важный вклад в квантовую физику, квантовую логику, функциональный анализ, теорию множеств, информатику, экономику и другие отрасли науки.

Новый!!: Равенство классов P и NP и Нейман, Джон фон · Узнать больше »

Разборов, Александр Александрович

Алекса́ндр Алекса́ндрович Разбо́ров (родился 16 февраля 1963 года в Белово Кемеровской обл.) — российский и советский учёный-математик, член-корреспондент РАН (с 2000 года), специалист в области теории вычислений.

Новый!!: Равенство классов P и NP и Разборов, Александр Александрович · Узнать больше »

Стюарт, Иэн (математик)

Иэн Николас Стюарт,, (24 сентября 1945 года) — британский математик, популяризатор науки и писатель-фантаст на сайте Scopus.

Новый!!: Равенство классов P и NP и Стюарт, Иэн (математик) · Узнать больше »

Стросс, Чарльз

Чарльз Дэвид Джордж «Чарли» Стросс (Charles David George «Charlie» Stross, род. 18 октября 1964 года) — английский писатель-фантаст.

Новый!!: Равенство классов P и NP и Стросс, Чарльз · Узнать больше »

Тьюринг, Алан

А́лан Мэ́тисон Тью́ринг, OBE (Alan Mathison Turing;  —) — английский математик, логик, криптограф, оказавший существенное влияние на развитие информатики.

Новый!!: Равенство классов P и NP и Тьюринг, Алан · Узнать больше »

Технический университет Эйндховена

Технический университет Эйндховена (TU/e, Technische Universiteit Eindhoven) — технический университет, расположенный в Эйндховене.

Новый!!: Равенство классов P и NP и Технический университет Эйндховена · Узнать больше »

Футурама

«Футура́ма» (Futurama — игра слов от future — «будущее» и panorama — «панорама») — американский научно-фантастический сатирический мультсериал, созданный в студии «20th Century Fox» Мэттом Грейнингом (Matt Groening) и Дэвидом Коэном (David X. Cohen), авторами мультсериала «Симпсоны».

Новый!!: Равенство классов P и NP и Футурама · Узнать больше »

Хопкрофт, Джон

Джон Эдвард Хопкрофт (John Edward Hopcroft, 7 октября 1939 года, Сиэтл, США) — американский учёный в области теории вычислительных систем, лауреат премии Тьюринга.

Новый!!: Равенство классов P и NP и Хопкрофт, Джон · Узнать больше »

Элементарно

«Элемента́рно» (Elementary) — американский детективный телесериал, основанный на персонажах книг сэра Артура Конан Дойла о Шерлоке Холмсе, действие происходит в наши дни.

Новый!!: Равенство классов P и NP и Элементарно · Узнать больше »

Математический институт Клэя

Математический институт Клэя — частная некоммерческая организация, расположенная в Кембридже, штат Массачусетс (США).

Новый!!: Равенство классов P и NP и Математический институт Клэя · Узнать больше »

Майнинг

Стойка с блоками майнинга Ares256 в дата-центре компании HashCoins OÜ Майнинг, также добыча (от mining — добыча полезных ископаемых) — деятельность по созданию новых структур (обычно речь идёт о новых блоках в блокчейне) для обеспечения функционирования криптовалютных платформ.

Новый!!: Равенство классов P и NP и Майнинг · Узнать больше »

Московский центр непрерывного математического образования

Московский центр непрерывного математического образования (МЦНМО) — негосударственное некоммерческое образовательное учреждение, ставящее своей целью сохранение традиций математического образования.

Новый!!: Равенство классов P и NP и Московский центр непрерывного математического образования · Узнать больше »

Биткойн

Битко́йн, или битко́ин (Bitcoin, от bit — «бит» и coin — «монета»), — пиринговая платёжная система, использующая одноимённую единицу для учёта операций и одноимённый протокол передачи данных.

Новый!!: Равенство классов P и NP и Биткойн · Узнать больше »

Вычислительная сложность

Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.

Новый!!: Равенство классов P и NP и Вычислительная сложность · Узнать больше »

Временная сложность алгоритма

В информатике временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные.

Новый!!: Равенство классов P и NP и Временная сложность алгоритма · Узнать больше »

Гёдель, Курт

Курт Фри́дрих Гёдель (Kurt Friedrich Gödel; 28 апреля 1906, Брюнн, Австро-Венгрия — 14 января 1978, Принстон, Нью-Джерси) — австрийский, и философ математики.

Новый!!: Равенство классов P и NP и Гёдель, Курт · Узнать больше »

Доказательство выполнения работы

Доказательство выполнения работы (Proof-of-work, POW, PoW) — принцип защиты сетевых систем от злоупотребления услугами (например, от DoS-атак или организации рассылок спама), основанный на необходимости выполнения на стороне клиента некоторой достаточно длительной работы (нахождение решения задачи), результат которой легко и быстро проверяется на стороне сервера (см. односторонняя функция).

Новый!!: Равенство классов P и NP и Доказательство выполнения работы · Узнать больше »

Левин, Леонид Анатольевич

Леони́д Анато́льевич Ле́вин (род. 2 ноября 1948, Днепропетровск) — советский и американский, специалист в области теории вычислительной сложности.

Новый!!: Равенство классов P и NP и Левин, Леонид Анатольевич · Узнать больше »

1971 год

* Международный год ООН по борьбе с расизмом и расовой дискриминацией.

Новый!!: Равенство классов P и NP и 1971 год · Узнать больше »

1973 год

Без описания.

Новый!!: Равенство классов P и NP и 1973 год · Узнать больше »

2002 год

В связи с 500-летием со дня смерти Дионисия решением ЮНЕСКО 2002 год назван годом Дионисия.

Новый!!: Равенство классов P и NP и 2002 год · Узнать больше »

Перенаправления здесь:

P != NP, P = NP, P vs. NP, P ≠ NP, P!=NP, P=NP, P≠NP, Проблема перебора.

ИсходящиеВходящий
Привет! Мы на Facebook сейчас! »