np
-
Хабрахабр
Вычислительная сложность некоторых игр и головоломок (часть 2)
В предыдущей статье мы рассмотрели сложность некоторых игр и головоломок. Данная тема вызвала некоторый интерес, вот и продолжение. В комментариях некоторые читатели высказали свои пожелания, которые я постарался учесть. В первой статье и правда по справедливому замечанию avsmal «не хватает каких-то более строгих и конкретных утверждений», но не стоит забывать, что любой даже самый нудный материал нужно стараться подать интересно.…
Читать далее » -
Хабрахабр
Есть проблемы гораздо сложнее, чем NP-Complete
Люди часто сравнивают P и NP в таком духе, что проблемы P простые, а NP — сложные. Но это чрезмерное упрощение. На самом деле проблемы могут быть намного, намного сложнее, чем NP. В этом смысле можно вспомнить интеллектуально-фантастический триллер Travelling Salesman (Коммивояжёр, 2012) о четырёх математиках, нанятых правительством США для решения самой сложной проблемы в истории информатики — равенства классов сложности P…
Читать далее » -
Хабрахабр
![Фото [Из песочницы] Формальная верификация на примере задачи о волке, козе и капусте](http://orion-int.ru/wp-content/uploads/2019/04/iz-pesochnicy-formalnaya-verifikaciya-na-primere-zadachi-o-volke-koze-i-kapuste.png)
[Из песочницы] Формальная верификация на примере задачи о волке, козе и капусте
На мой взгляд, в русскоязычном секторе интернета тематика формальной верификации освещена недостаточно, и особенно не хватает простых и наглядных примеров. Я приведу такой пример из зарубежного источника, и дополню собственным решением известной задачи о переправе волка, козы и капусты на другую сторону реки. Но вначале вкратце опишу, что из себя представляет формальная верификация и зачем она нужна. Под формальной верификацией…
Читать далее » -
Хабрахабр
![Фото [Перевод] Краткое руководство по сложным вычислительным задачам](http://orion-int.ru/wp-content/uploads/2018/08/perevod-kratkoe-rukovodstvo-po-slozhnym-vychislitelnym-zadacham.jpg)
[Перевод] Краткое руководство по сложным вычислительным задачам
Что компьютеру сделать легко, а что почти невозможно? Эти вопросы лежат в основе вопроса вычислительной сложности. Представляем вам карту этого ландшафта. Различные классы сложности сортируют задачи в иерархическом виде. Один класс может содержать все задачи другого, плюс задачи, требующие дополнительных вычислительных ресурсов. Такова постановка базовой задачи специалистов по информатике, пытающихся рассортировать задачи по т.н. Какова фундаментальная сложность задачи? Это группы,…
Читать далее »