Что не так с этим аргументом P

Question

Мой учитель привел этот аргумент и спросил нас, что может быть не так с ним.

для массива A из n различных чисел. Так как есть n! Перестановки A, мы не можем проверить для каждой перестановки, отсортирована ли она, за общее время, которое является полиномиальным от n. Поэтому сортировка A не может быть в P.

мой друг подумал, что так и должно быть: поэтому сортировка не может быть в NP. Это или мы думаем легко об этом?

Answer 1

Аргумент не является последовательным, заключение логически не следует из предыдущих шагов. Почему это не следует? Чтобы дать удовлетворительный ответ на этот вопрос, необходимо знать, почему человек, который написал аргумент , считает правильным, а затем обратиться к своему заблуждению. В этом случае человек, который написал аргумент, является вашим учителем, который не считает аргумент правильным, поэтому нет неправильного представления и, следовательно, нет полностью удовлетворительного ответа на вопрос.

Тем не менее, мое объяснение будет состоять в том, что аргумент неверен, поскольку он предлагает конкретный c алгоритм для сортировки, а именно - итерацию по всем n! перестановки и выбор той, которая отсортирована - и затем предполагает, что сложность задачи такая же, как сложность этого алгоритма. Это ошибка, потому что сложность задачи определяется как самая низкая сложность из всех алгоритмов, которые ее решают. Аргумент рассматривал только один алгоритм и ничего не показал о других алгоритмах, которые решают проблему, поэтому он не может прийти к выводу о сложности самой проблемы.

Answer 2

Проблема с этим аргументом заключается в том, что он не может адекватно указать точную проблему.

Сортировка может быть линейной (O (n)) по количеству элементов для сортировки, если вы сортируете большой список целых чисел, взятых из небольшого пула (сортировка по счетам, сортировка по основанию).

Сортировка может быть линейной c -time (O (nlogn)) по количеству элементов для сортировки, если вы ' повторная сортировка списка произвольных вещей, которые все полностью упорядочены согласно некоторому отношению порядка (например, меньше или равно целым числам).

Сортировка на основе частичного порядка (например, топологическая сортировка) должна быть проанализирована еще одним способом.

Мы можем представить себе проблему, подобную сортировке, при которой сортировка списка не может быть определена путем сравнения только смежных записей. В крайнем случае сортировка (в соответствии с тем, что мы считаем сортировкой) может быть проверена только путем проверки всего списка. Если наш вид сортировки спроектирован так, чтобы гарантировать, что в любом заданном списке есть только одна отсортированная перестановка, временная сложность равна факториальному времени (O (n!)), А проблема не в P.

Это реальная проблема с этим аргументом. Если ваш профессор предполагает, что «сортировка» относится к сортировке целых чисел не в каком-либо конкретном небольшом диапазоне, проблема с аргументом заключается в том, что нам не нужно рассматривать все перестановки, чтобы построить отсортированную. Если у меня есть сумка с 100 шариками, и я прошу вас убрать три шарика, сложность времени постоянна; Неважно, что существует n (n-1) (n-2) / 6 = 161700 или O (n ^ 3) способов, которыми вы можете выполнить sh эту задачу.