Моё видение проблемы равенства классов P и NP
Формулировка проблемы в википедии:
Нестрого говоря, проблема равенства P= NP состоит в следующем: если положительный ответ на какой-то вопрос можно довольно быстро проверить, то правда ли, что ответ на этот вопрос можно довольно быстро найти? Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать?
Возьмём такой пример.
Нужно вытянуть выигрышный лотерейный билет из бесконечного количества лотерейный билетов. Есть ли вероятность за ограниченное количетво попыток вытянуть выигрышный лотерейный билет? Есть. Есть ли вероятность его не вытянуть за любое количество попыток? Тоже есть. А есть ли вероятность выиграть в лотерею совсем не вытягивая билет? Нет.
NP- общее количество вытягиваний
P- количество вытягивания выигрышных билетов
Соответственно если вытянули сразу выигрышный билет, то P=NP, если нет то P < NP. Если ни разу не вытягивали то...... получается что P=0 и NP=0, соответсвенно в этом случае тоже P=NP. А в каком случае может быть P > NP ? Только если общее количество вытягиваний отрицательное, этого не может быть.
P=0 и NP=0. Согласен если задачи нет, то и решать не надо.
Вот только класс P включен в NP (что следует из определения классов) => противоречие.
Но ведь проблема перебора заключается в "решение задачи проверить не легче, чем его отыскать?"
Что в вашей задаче с лотереей поиск решения, а что проверка?
В вашем случае смотреть на это нужно так:
Р - проблема поиска решения задачи.
NP - проблема проверки решения.
Все 3 вопроса "есть ли вероятность..." являются NP-задачей, а являются ли они Р-задачами?
Суть вопроса в том что если проверить все лотерейные билеты, то будут ли затраты по ресурсам полиноминальны относительно проверки билета. С бесконечной лотерей получается бесконечные затраты по решению. С другой стороны проверка билета бесконечной лотереи займет бесконечное время. Как вы предполагаете проверить номер билета за конечное время если его номер хм бесконечен в потенциале? То есть у нас на лицо неопределенность.
С чего вы вообще задали ограничение в попытках. Это вообще при чем?