Будет ли параметризованная сложность будущим теории сложности?

9

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

Вопрос: Будет ли параметризованная сложность будущим теории сложности? Будущее просто означает количество научных работ, количество исследователей, работающих в этой области и т. Д.

Обратите внимание, что я наивен и, возможно, не в курсе многих вещей.

старый
источник
3
Я думаю, что только ваш второй вопрос подходит для этого сайта, а именно, есть ли работы по "квантово-параметризованной сложности"? - поскольку первый вопрос (а) о предсказании будущего, что всегда сложно, и (б) ответы будут очень субъективными. Но я подозреваю, что ответ на ваш вопрос (1) заключается в том, что все еще проводится много активных исследований алгоритмов и сложности, а не параметризованной сложности.
Джошуа Грохов
1
Здесь нет исследователей, но я никогда не знал, что параметризованная сложность - это нечто другое, чем просто ... сложность. Что именно люди делали заранее, когда сложность зависела от двух величин? Просто забыли одного из них?
user541686
1
Я большой поклонник параметризованной сложности, и я был рад увидеть этот пост в тот же день, когда вышел бюллетень FPT. :)
Майкл Вехар

Ответы:

17

Предсказание будущего почти невозможно, особенно для передовых исследований. Я не думаю, что кто-то предсказал, какое влияние сейчас оказывает глубокое обучение или что криптография будет поглощена путаницей неразличимости.

Тем не менее, я скажу так много: я не вижу особой причины ожидать параметризованной сложности. Это зрелая сфера, которая работает уже около 20 лет. Это действительно не кажется мне перспективной областью. Чтобы быть ясным, я думаю, что это успешная область, которая будет продолжать процветать.

Если вы посмотрите на тренды Google , интерес к поиску в параметризованной сложности снижается. (. Палка в некоторых других терминах для сравнения , если вы заинтересованы) Если вы посмотрите комбинированные цитаты для Дауни - Fellows учебника Параметризованной Сложность и их обновленный учебник , вы видите , что они довольно стабильны: (Источник: Google ученый . Я добавил обе книги в свой профиль, объединил их, сделал снимок экрана с объединенными цитатами, а затем удалил их из своего профиля.)введите описание изображения здесь

Это большое количество ссылок, но это не экспоненциальный рост, который заставил бы вас думать, что параметризованная сложность возьмет верх. Конечно, эти данные очень ошибочны, но это лучший показатель, который я могу найти о глобальной популярности параметризованной сложности.

Обратите внимание, что вещи могут быть очень популярны локально, даже если они не популярны во всем мире. Когда я был студентом, я думал, что мне нужно узнать о теории категорий, потому что все вокруг меня говорили об этом; Я даже купил книгу. Затем я перешел в аспирантуру и больше никогда об этом не слышал; книга остается непрочитанной по сей день. Возможно, вы находитесь в аналогичной ситуации - вы находитесь в отделе, где происходит много параметризованной сложности, но если вы переедете куда-то еще, история будет совершенно другой.

Томас
источник
6
RIP ко всем этим непрочитанным книгам по теории категорий ...
Гигабайт
3
Просто из любопытства: вы говорите, что было место, где некоторое количество людей, работающих в области сложности и алгоритмов, некоторое время интересовались теорией категорий? Или эти люди были больше в мире языков программирования? (В таком случае это не удивительно). Как исследователь, ориентированный на теорию категорий, мне любопытно узнать, где это место и чем он интересуется.
Дамиано Мазза
@DamianoMazza Я получил в алгоритмах и сложности в аспирантуре. Мое знакомство с теорией категорий было с точки зрения PL / логики. Мне нравится теория категорий; это просто не очень подходило в моей работе.
Томас
Хорошо, как я уже сказал, это не очень удивительно! (Ни эти люди PL / logic не интересны в категориях, ни то, что вы не нашли их использования в алгоритмах и сложности). Спасибо!
Дамиано Мазза
@DamianoMazza вы можете создать «псевдо-категорию» ТМ и сгенерировать ее по некоторой слабой приводимости, а затем вы получите хорошие вещи, такие как способность характеризовать полноту с помощью теоретико-категориальных конструкций, но мне кажется, что вы получить точно такие же результаты, просто используя poset. Есть эта статья, которая была опубликована здесь некоторое время назад для установления этой связи: главные идеалы в этом наборе образуют «синтаксические классы», которые имеют законченный язык и счетно перечислимы. Может быть, есть больше пробега, который вы можете получить из подходящей категории, хотя я еще не получил.
Сэмюэль Шлезингер