Класс сложности, соответствующий сортировке

14

Две части TCS - это алгоритмы и сложность. Я упрощенно скажу, что алгоритмы - это исследование верхних границ, показывающее, что вы можете что-то сделать (с заданными ограниченными ресурсами), а сложность заключается в том, чтобы показать, что вы не можете сделать это без каких-либо минимальных ресурсов.

Очень часто алгоритмическая проблема формулируется в модели решения, чтобы поместить ее в класс сложности.

Но меня всегда беспокоило то, что некоторые элементарные алгоритмы никогда не упоминаются как принадлежащие к определенному классу. Одним из примеров является (сравнение) сортировка. Попробуйте, как я мог бы, соответствующий класс кажется слишком неполноценным (на самом деле, он просто проверяет в лог-пространстве, что результат отсортирован? Это кажется слишком слабым, или я не понимаю верную версию решения).

Каков наилучший / наиболее подходящий / наиболее полезный класс сложности, в котором заключается сортировка сравнения?

Митч
источник

Ответы:

17

Задача сортировки фактически завершена для TC0 (при -редуцировании). Стандартным источником для этого является Раздел 1.4.3 книги Фольмера .AC0

Обратите внимание, что - это класс задач решения, но мы обычно думаем о сортировке как о функциональной проблеме, т.е. мы хотим вывести числа, скажем, в неубывающем порядке. Однако мы также можем определить сортировку как решение проблемы следующим образом:TC0

Учитывая последовательность чисел и двух чисел k , p [ n ] , мы хотим решить, находится ли a k в положении p в последовательности, которую мы получаем, сортируя a 1 , , a n по неубывающей заказ. Обратите внимание, что во избежание двусмысленности, когда a i = a j , мы хотим, чтобы a i предшествовал a j, если i < j .a1,,ank,p[n]akpa1,,anai=ajaiaji<j

Дай Ле
источник
Отлично ... указано, какое формальное решение проблемы?
Митч
1
Было бы в два раза лучше включить ссылку в ваш ответ.
Александр Бондаренко
@Mitch и @Okeksandr: Спасибо за ваши комментарии! Я только что расширил свой ответ, чтобы прояснить эти моменты.
Дай Ле
Это звучит как решение проблемы для статистики заказов. Есть ли связанная проблема, когда все на своем месте? Что-то вроде заданной последовательности и перестановка σ на [ 1 .. n ] , решает, если 1 k < j n , a σ k < a σ j . Это так же сложно, как у тебя; это сложнее или полнее для включающего класса? a1...anσ[1..n]1k<jn,aσk<aσj
Митч
2
@ Митч: Я считаю, что проверить, все ли в нужном месте, на самом деле проще, чем сортировку. Интуиция является то , что вы можете проверить , что σ к < σ J для всех возможных пар ( в сг к , σ J ) с к < J параллельно, который я считаю , может быть сделано в A C 0 . Для вышеупомянутой задачи сортировки вам нужно уметь «считать», чтобы вычислить правильную позицию числа в линейном порядке. aσk<aσj(aσk,aσj)k<jAC0
Дай Ле
0

Я считаю, что FP это то, что вы ищете.

Николас Манкузо
источник
Что ж, я скорее ищу соответствующий класс сложности решения, чем функциональный, но даже в этом случае, я вполне уверен, что сортировка сравнения не где-то рядом с P-полной (или FP-полной), поэтому я ожидаю меньший класс, для которого он должен быть в / завершен.
Митч
Я не знал, что полнота была одним из требований к вашему вопросу. Как решение проблемы (если вы игнорируете свое ограничение полноты), почему P не будет приемлемым в качестве ответа? При наличии DTM вы можете производить и проверять сертификат за полиномиальное время.
Николас Манкузо
Учитывая общую проблему, я обычно хочу знать не только то, что это полиномиальное время, но и наименьший класс, в котором он может находиться. Я хотел бы знать, находится ли он в LOGCFL, NL, L, AC_0 и т. Д. Полнота это один из способов, который вы не можете сделать лучше. Так что это не требование моего вопроса, а скорее всего ответ.
Митч