допустим, у меня есть несколько ссылок на сайты, и моя задача заключается в том, чтобы выяснить, есть ли среди них такой сайт, где встречается слово «вася», и который, при этом содержит ссылку на сайт, где встречается слово «петя». Если нашли — выходим.
Элементарный алгоритм — проверить первый встретившийся сайт на васю. если нет вхождения — возврат на второе вхождение изначального списка, если есть — взять список ссылок этого сайта, и проверить каждую на петю, если нет — возврат на второе вхождение изначального списка.
Абсолютно ясно, что НМТ нам тут ни какого выигрыша не даст. Допустим, мы на первом шаге начали проверку не с первого, а, (недетерминированно) со второго сайта. Вероятность успеха тут равна первому варианту, а значит, в общем случае, скорость не увеличиться, и в худшем случае, нам предстоит полный перебор. Нет вообще никакой разницы, на какой машине мы это выполняем.
В таком случае, что нам дает недетерминированная машина?
Отсюда по идее, должно вытекать простое следствие, P = NP, разве не так? Ведь NP — это ни что иное, как алгоритм выполняемый на недетерминированной МТ. В чем подвох?
Буду благодарен за пояснения, но только без зауми.
UPD возможно, вопрос в действительности дилетантский, возможно формулировка некорректна, однако я более чем уверен, что те кто отвечают на него оскорблениями, просто вообще не понимают предмета, иначе бы они указали на конкретную ошибку, а не брызгали слюнями. Это так, к слову.
