Объяснение не обязательно должно быть «на пальцах», «для чайников», «простыми словами. Объясните так, как вам удобнее.
Я следую Александру Шеню https://postnauka.ru/faq/43795
Проблема перебора является, вероятно, самым главным открытым вопросом в области математической логики, философии математики и computer science, так что решить ее мечтают почти все. Она фигурирует и в известном широкой публике списке «задач тысячелетия», за решение которых дают миллионные призы
Однако никто толком не знает, как к этой задаче подступиться. Неформально говоря, вопрос состоит в следующем: верно ли, что любую переборную задачу можно быстро решить?
Технически проблему перебора формулируют так: совпадают ли классы P и NP? Класс P — это те задачи, которые могут быть решены «быстро». А класс NP — это переборные задачи. Если P равно NP, то окажется, что все переборные задачи могут быть быстро решены. А если не равно, то не все.
Когда мы определяем класс P (класс «быстро решаемых» задач), то требуем, чтобы число шагов машины Тьюринга, решающей такую задачу, было невелико: при обработке входных данных из n битов число шагов должно быть ограничено некоторой степенью числа n (полиномом). Поэтому задачи из P называют задачами, разрешимыми на полиномиальное время, буква P в названии как раз происходит от polynomial time (полиномиальное время).
Класс переборных задач называют NP — в первых работах он определялся в терминах так называемых недетерминированных машин Тьюринга .(*) В таких задачах мы интересуемся вопросом о наличии объекта полиномиального размера, обладающего некоторым полиномиально проверяемым свойством.
Проблема перебора важна прежде всего для современной криптографии. Если обнаружится, что есть быстрый способ решения переборных задач, то разрушится вся современная технология криптографии с открытым ключом, позволяющая наладить предположительно безопасный обмен информацией между собеседниками, которые не договорились заранее о каком-то секретном ключе, известном только им. Такой «взлом» приведет к серьезному экономическому кризису, потому что в нынешнем мире на криптографии с открытым ключом очень многое завязано (все стандартные протоколы защищенной передачи информации именно таковы).
Посмотрите подробно https://postnauka.ru/faq/43795 . Это написано именно для не-специалистов. Я не профи в этой области , но думаю , что Александр Шень объясняет предельно сжато и предельно понятно - «на пальцах», но в тоже время вполне профессионально. Хороший технический писатель - это именно тот человек, который может о сложном сказать просто. За мою репутацию отвечает http://lxer.com/module/newswire/byuser.php?user=dba477
Именно разделы - 1. Определение переборной задачи и 2. Более формальное определение - это определение машины Тьюринга именно в контексте Вашего вопроса.