Max Flow и NP, нужны эксперты, чтобы проверить этот вызов?
Я вижу этот вопрос о проблемах NP и нуждаюсь в некоторых деталях?
Я изучаю NP, P и NP-Complete на вычислительном курсе, и застрял в одном определении:
у нас есть пример, чтобы определить, есть ли в NP или нет:
Нахождение максимального потока в сети.
кто-то говорит, что "есть решение за полиномиальное время, что означает, что оно находится в P. Таким образом, оно находится в NP"
кто-то говорит: "Неважно, что здесь нет проблемы с решением. Вы можете найти максимальный поток за полиномиальное время, поэтому в этом случае вам не нужно сначала создавать сертификат. Проблема явно в P из-за Алгоритм Форда-Фулкерсона и, следовательно, расширение в NP. Это не вариант решения, который создает что-то NP. Дело в том, что вы не можете использовать недетерминизм, чтобы точно знать, что сертификат является оптимальным ".
кто-то говорит: "Нахождение максимального потока не является проблемой для решения, и поэтому он не подходит для участия в NP"
В этой категории мое основное недоразумение состоит в том, можем ли мы сказать эту проблему в NP или не можем сказать, потому что e не существует Решающей проблемы? любая идея? или доказательство?