Чтобы определить, является ли задача (A) NP-Complete, мы должны сделать четыре шага:
- Докажите, что A в NP
- Превратить известную задачу NP Complete (B) в A за полиномиальное время
- Докажите, что ответ на A является ответом на B
- Докажите, что ответ B - это ответ A
В вашей задаче вы начинаете с известной проблемы NP-Complete nSudoku с целью сначала показать, что факторизация также является NP-Complete. Для этого мы сначала покажем, что факторизация находится в NP. Затем вы предоставляете информацию о том, что nSudoku можно преобразовать в факторизацию за полиномиальное время. Если затем мы покажем, что ответ на nSudoku является ответом на факторизацию, и наоборот, то мы доказали, что факторизация является NP-полной.
Затем мы будем следовать той же схеме для факторизации и задачи сортировки целочисленного массива, чтобы доказать, что задача сортировки целочисленного массива является NP Complete (начиная с того факта, что факторизация находится в NP). Это, однако, усложняет ситуацию, потому что проблема сортировки целочисленного массива фактически находится в P, поскольку вы можете отсортировать целочисленный массив в O (nlogn), что является полиномиальным временем.
В основе этого вопроса лежит «проблема P против NP», которая представляет собой нерешенную проблему, которая задает вопрос, действительно ли каждая проблема в NP находится в P (иными словами, может ли быть проверена каждая проблема, для которой существует проблема решения) в полиномиальное время также может быть решена в полиномиальное время). На сегодняшний день нет ответа на проблему.
Однако в вашей задаче мы докажем, что задача, о которой известно, что P также является NP-полной, что приводит к заключению, сформулированному в вашей задаче, что P = NP.