КИЕВ
Мой Киев, права потребителей, автомобили, аптеки, бассейны, лекарства, магазины
Карта сайта

 Мой Киев, права потребителей, автомобили, аптеки, бассейны, лекарства, магазины Главная
 Заказать сайт Сайт от 100 грн
 АВТО АВТО
 АВТО АНАЛИТИКА
 АВТО ГИПОТЕЗЫ
 АВТО Для ДЕТЕЙ
 АВТО ДЕНЬГИ
 АВТО ЖКХ
 АВТО ЗДОРОВЬЕ
 АВТО ИСТОРИЯ КИЕВА, УКРАИНЫ и РУСИ
 Наше КИНО КИНО
 Наше КИНО КОМПЬЮТЕР
  КОНЕЦ СВЕТА 2012
 МОЙ КИЕВ МОЙ КИЕВ
 АВТО МУЗЫКА
 UML— унифицированный язык моделирования. Децибел (dB), 
NP-полнота. Построение и анализ алгоритмов. Теория. Дискретная математика. Утилизация радиоактивных отходов. 
Деловая и познавательная информация для киевлян и гостей Киева
 АВТО НАША ИСТОРИЯ
 АВТО НОВОСТИ
 АВТО ПОЛИТИКА
 РАСПРОДАЖА РАСПРОДАЖА
 АВТО СВОИМИ РУКАМИ
 АВТО СПОРТ
 АВТО АРХИВ


email




Эльслотс казино (Эльдорадо) для игроков с Украины. Cashback по пятницам. Бонус 200FS + 150%.
Вкусные десерты, настолько полезные, насколько это возможно. Сотни интересных решений, которые удовлетворят ваши вкусовые рецепторы.
Строительный портал ДомСтрой: всё для ремонта, строительства и обустройства дома Удобный поиск компаний и мастеров по ремонтам
Аутсорсинговая компания предоставляющая IT услуги для предприятий. Услуги системного администратора.
2021 – Год Белого Стального Быка
Храни Киев
ЛЧ. Лацио-Бавария 1:4. Атлетико-Челси 0:1 ЛЕ. Динамо-Брюгге 1:1. Маккаби-Шахтер 0:2. ЛЧ. Порту-Ювентус 2:1. Севилья-Боруссия 2:3.
Australian Open 2021. Биатлон. Чемпионат мира - 2021. Поклюка.

Мой Киев, права потребителей, автомобили, аптеки, бассейны, лекарства, магазины

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

Построение и анализ алгоритмов. Теория. Дискретная математика.

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


В теории алгоритмов вопрос о равенстве классов сложности P и NP является 
одной из центральных открытых проблем уже более трех десятилетий. Если на 
него будет дан утвердительный ответ, это будет означать, что теоретически 
возможно решать многие сложные задачи существенно быстрее, чем сейчас.

Классы P и NP
В конечном счете проблема P = NP состоит в следующем: если положительный 
ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), 
то правда ли, что ответ на этот вопрос можно быстро найти (за 
полиномиальное время и используя полиномиальную память)?

Проще говоря, действительно ли задачу легче проверить, чем решить?

Например, верно ли, что среди чисел {-2, -3, 15, 14, 7, -10, …} есть такие, 
что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что 
-2 -3 + 15 -10 = 0 легко проверяется несколькими сложениями (информация, 
необходимая для проверки положительного ответа, называется сертификатом). 
Следует ли отсюда, что так же легко подобрать эти числа? Проверить 
сертификат так же легко, как найти его? 
Кажется, что подобрать числа сложнее (не доказано).

Содержание проблемы
Диаграмма классов сложности при условии P /= NP. Равенство классов P и NP. Построение и анализ алгоритмов. Теория. 
Дискретная математика.
Диаграмма классов сложности при условии P /= NP. Отношения между классами P и NP рассматриваются в теории вычислительной сложности (разделе теории вычислений), изучающей ресурсы, необходимые для решения некоторой задачи. Наиболее общие ресурсы — это время (сколько нужно сделать шагов) и память (сколько памяти потребуется для решения задачи). История Из определения классов P и NP сразу вытекает следствие: Равенство классов P и NP. Построение и анализ алгоритмов. 
Теория. Дискретная математика.. Однако до сих пор ничего не известно о строгости этого включения, т. е. существует ли алгоритм, лежащий в NP, но не лежащий в P. Если такого алгоритма не существует, то все задачи, принадлежащие классу NP, можно будет решать за полиномиальное время, что сулит огромную выгоду с вычислительной точки зрения. Сейчас самые сложные задачи из класса NP (так называемые NP-полные задачи) можно решить за экспоненциальное время, что почти всегда неприемлемо. Впервые вопрос о равенстве классов был поставлен независимо Стивеном Куком в 1971 году и Леонидом Левиным в 1973. В настоящее время большинство математиков считают, что эти классы не равны. Согласно опросу, проведённому в 2002 году среди 100 учёных, 61 человек считает, что ответ — «не равны», 9 — «равны», 22 затруднились ответить и 8 считают, что гипотеза не выводима из текущей системы аксиом и, таким образом, не может быть доказана или опровергнута. В настоящий момент проблема равенства классов P и NP является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США.