Моё видение проблемы равенства классов P и NP
Формулировка проблемы в википедии:
Нестрого говоря, проблема равенства P= NP состоит в следующем: если положительный ответ на какой-то вопрос можно довольно быстро проверить, то правда ли, что ответ на этот вопрос можно довольно быстро найти? Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать?
Возьмём такой пример.
Нужно вытянуть выигрышный лотерейный билет из бесконечного количества лотерейный билетов. Есть ли вероятность за ограниченное количетво попыток вытянуть выигрышный лотерейный билет? Есть. Есть ли вероятность его не вытянуть за любое количество попыток? Тоже есть. А есть ли вероятность выиграть в лотерею совсем не вытягивая билет? Нет.
NP- общее количество вытягиваний
P- количество вытягивания выигрышных билетов
Соответственно если вытянули сразу выигрышный билет, то P=NP, если нет то P < NP. Если ни разу не вытягивали то...... получается что P=0 и NP=0, соответсвенно в этом случае тоже P=NP. А в каком случае может быть P > NP ? Только если общее количество вытягиваний отрицательное, этого не может быть.
Наука | Научпоп
7.8K поста78.7K подписчика
Правила сообщества
Основные условия публикации
- Посты должны иметь отношение к науке, актуальным открытиям или жизни научного сообщества и содержать ссылки на авторитетный источник.
- Посты должны по возможности избегать кликбейта и броских фраз, вводящих в заблуждение.
- Научные статьи должны сопровождаться описанием исследования, доступным на популярном уровне. Слишком профессиональный материал может быть отклонён.
- Видеоматериалы должны иметь описание.
- Названия должны отражать суть исследования.
- Если пост содержит материал, оригинал которого написан или снят на иностранном языке, русская версия должна содержать все основные положения.
Не принимаются к публикации
- Точные или урезанные копии журнальных и газетных статей. Посты о последних достижениях науки должны содержать ваш разъясняющий комментарий или представлять обзоры нескольких статей.
- Юмористические посты, представляющие также точные и урезанные копии из популярных источников, цитаты сборников. Научный юмор приветствуется, но должен публиковаться большими порциями, а не набивать рейтинг единичными цитатами огромного сборника.
- Посты с вопросами околонаучного, но базового уровня, просьбы о помощи в решении задач и проведении исследований отправляются в общую ленту. По возможности модерация сообщества даст свой ответ.
Наказывается баном
- Оскорбления, выраженные лично пользователю или категории пользователей.
- Попытки использовать сообщество для рекламы.
- Фальсификация фактов.
- Многократные попытки публикации материалов, не удовлетворяющих правилам.
- Троллинг, флейм.
- Нарушение правил сайта в целом.
Окончательное решение по соответствию поста или комментария правилам принимается модерацией сообщества. Просьбы о разбане и жалобы на модерацию принимает администратор сообщества. Жалобы на администратора принимает и общество Пикабу.