0
это ответ, который я нашел на переполнение стекаP NP и NP полная очистка?
«NP класс сложности, который представляет собой совокупность всех задач принятия решений, для которых случаи, когда ответ„да“есть доказательства того, что можно проверить за полиномиальное время.
Это означает, что если кто-то дает нам экземпляр проблемы и сертификат (иногда называемый свидетелем), давая ответ «да», мы можем проверить, что это правильно в полиномиальное время ». -jason
Мой вопрос: кто является «мы», который проверяет, правильно ли разрешено в полиномиальное время? Это программа или буквально означает, что человек сидит и работает на бумаге?
Это, наверное, немой вопрос, но, пожалуйста, со мной.
Возможный дубликат [Каковы различия между NP, NP-Complete и NP-Hard?] (Http://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np- hard) – RussS
Нет, это не то, о чем я прошу. Я ссылаюсь на один из ответов на этот вопрос в моем вопросе, написанном выше ... – Squaddy
В контексте алгоритмов нет никакой разницы между человеческой и компьютерной программой (если только это не квантовый компьютер, конечно!). Важно только количество ** действий **; будь то человек или программа. Фактически разница между этими двумя лежит в их ** скорости ** выполнения ** действий **, и теория сложности говорит о ** числе ** действий, но не ** скорости ** из них. – AliVar