Нет проблем

Такой ответ можно часто слышать в повседневной жизни . И это хорошо и оптимистично
Но проблемы есть .
В 2000 году был публично объявлен «список проблем следующего тысячелетия», за которые Институт Клея обещает миллион долларов (Перельман решил одну из этих проблем — но миллион не взял). Первая проблема в этом списке — это проблема перебора, и она там заслуженно.
Ее можно объяснить на таком примере: выпускалась игрушка Eternity — это такая коробочка, в которую уложены плитки, раскрашенные в разные цвета, но они раскрашены так, что видно, какие плитки можно прикладывать друг к другу (там рисунок на краях).

Продаются они рассыпанными, и фирма, которая их изготовила, утверждает, что все это можно собрать в одну картинку внутри этой квадратной коробки (там 256 плиток) — то есть изначально это была одна картинка, разрезанная на плитки. По современным представлениям машины такие задачи за обозримое время решать не могут, — никакого способа, кроме как перебирать все варианты (а их очень много) сейчас не известно.

Но, с другой стороны, никто этого не может и доказать. Это и называется проблемой перебора — доказать, что такой полный перебор каких-то объектов нельзя заменить никаким более коротким вычислением.
Или другой более известный пример : криптография

Интересно в теории сложности вычислений то, что не только наличие какого-то алгоритма полезно практически, но, как ни странно, часто бывает полезно отсутствие алгоритма. Например, есть такой известный вопрос о разложении чисел на множители. Если число небольшое, то легко проверить, что оно простое — можно проверить все меньшие числа и понять, что там нет делителей. Если число большое, то так просто уже нельзя проверить — но существуют разные алгоритмы, которые позволяют это делать. (Они основаны на малой теореме Ферма и ее усовершенствованиях.) Так или иначе, алгоритмы проверки простоты существуют.

А теперь другая задача: возьмем два больших простых числа и их перемножим, сообщим, что у нас получилось, и спросим, какие это были числа. Это задача разложения на множители, и никто не знает, как это быстро сделать. И то, что этого никто не знает, очень хорошо, потому что благодаря этому существует вся вычислительная криптография, это одно из основных ее предположений. Когда кто-нибудь снимает деньги в банке, или в интернете заходит на сайт с помощью SSL — используются системы криптографии, основанные на том, что быстро разлагать на множители числа нельзя.

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

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

Да , и собственно , ради чего я это пишу : не кажется ли вам что леди на видео это одна из наших форумчанок ?
)