У меня возник вопрос.NP полный или NP жесткий, в проблемах с эквивалентами?
Поиск всего цикла в графике NP-Complete.
Я вижу эту заметку в поиске Google.
подсчет всего цикла на графике NP-Complete.
are these two sentence equivalences ? can we say these two is NP-Hard?
Спасибо за каждую полезную записку.
are these two sentence equivalences ?
Да, но это не правильно выразился. Ни один из этих вопросов не является решением проблем. Проблемы с решением возвращают либо true, либо false. NP-Complete - это категоризация проблем решения, поэтому будет «неправильно», чтобы сказать, что вышеперечисленные NP-Complete. Но если мы скажем: «Существует ли количество циклов на графике?» это будет вопрос NP-Complete.
can we say these two is NP-Hard? Да NP-Hard означает, что это так сложно, как NP, по крайней мере, потому что эти две проблемы NP-Complete, то это правда.
Вы подразумеваете, что два из них np-complete и np-hard? или лучше решить проблему np-hard или np-complete? –
NP Полные проблемы NP-Hard, но проблемы с NP-Hard могут не быть NP Complete. –
Вы имеете в виду «Поиск всего цикла в графике NP-Complete». np-hard с этой фразой? –