История изменений
Исправление Waterlaz, (текущая версия) :
так... классы P и NP на пальцах:
Рассмотрим классы задач, для которых нужно лишь дать ответ «да» или «нет».
Представим себе самый обычный комп, но с бесконечной оперативной памятью. Класс P - это все задачи, для которых существует программа для этого компа, которая решает задачу за не очень большое время (время зависит как полином от объема входных данных).
Теперь представим тот же обычный комп, но который может в любой момент форкнуться на два компа, каждый из которых может сделать то же самое и так далее сколько угодно раз. К сожалению, форкнувшиеся компы не имеют средств взаимодействия друг с другом. Тем не менее, когда все компы закончат работу, мы можем узнать, ответил ли хоть один из компов «да» или все ответили «нет». Если хоть один из них ответил «да», то принимаем ответ «да», если все ответили «нет», то «нет».
Множество задач, для которых существует заверщающаяся за полиномиальное время программа, и есть класс NP.
Исходная версия Waterlaz, :
так... классы P и NP на пальцах:
Рассмотрим классы задач, для которых нужно лишь дать ответ «да» или «нет».
Представим себе самый обычный комп, но с бесконечной оперативной памятью. Класс P - это все задачи, для которых существует программа для этого компа, которая решает задачу за не очень большое время (время зависит как полином от объема входных данных).
Теперь представим тот же обычный комп, но который может в любой момент форкнуться на два компа, каждый из которых может сделать то же самое и так далее сколько угодно раз. К сожалению, форкнувшиеся компы не имеют средств взаимодействия друг с другом. Тем не менее, когда все компы закончат работу, мы можем узнать, ответил ли хоть один из компов «да» или все ответили «нет». Если хоть один из них ответил «да», то принимаем ответ «да», если все ответили «нет», то «нет».
Множество задач, для которых существует заверщающаяся за полиномиальное время программа, и есть множество NP.