Вот моя проблема: Даны числа x1, ... xn.Числа соответствуют n размерам файлов и объему памяти диска D. Надо понимать, можем ли мы, чтобы файлы разбивались на 3 диска.Размер файла, записанный на любом диске, не может превышать емкость диска D. Давайте оценим, что эта вычислительная задача относится к классу NP.Что такое дополнительная информация (сертификат), что в этом случае требуется для алгоритма проверки?
Вот моя идея, но я действительно не уверен:
Дополнительная информация: 3 комплекта в одном наборе, который содержит файлы x1, ..., xn.Эти наборы могут быть распознаны, если к строке добавить переменные y1, y2, y3, которые будут помещены в начало набора мыслей и содержат символ, который отличается от числа, чтобы не мешать строке размера файла..
Проверка: Должна быть возможность проверить, не превышает ли общий размер каждого набора файлов емкость диска D.Алгоритм может быть простым для этого путем введения переменной.К переменной будет добавляться размер загруженного файла до тех пор, пока либо эта сумма не превысит емкость диска D, либо пока не будет достигнут новый установленный начальный символ.В момент превышения емкости диска D выдается отрицательный ответ, в противном случае - положительный.Время, затрачиваемое на этот алгоритм, составляет O (n).
Я не знаю, как оценить, что этот алгоритм является классом NP.Потому что NP может быть решена недетерминированной машиной Тьюринга за O (n ^ k) времени.