Какой математический фон необходим для теории сложности?

79

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

Какие области вы считаете необходимыми для тех, кто хочет изучать теорию сложности? Знаете ли вы о каких-либо хороших учебниках, охватывающих эти области, и если да, пожалуйста, укажите их уровень сложности (вступительный, выпускной и т. Д.).

Если вы рассматриваете область, которая не очень широко используется в теории сложности, но вы считаете ее критической для TCS, просим также сослаться на нее.

cc.complexity-theory soft-question advice-request chazisop
источник
14
Я бы порекомендовал вам начать читать стандартный текст по теории сложности, например, Arora / Barak или Papadimitriou, и всякий раз, когда вы застреваете, потому что не понимаете математику, попробуйте изучить соответствующую математику, прежде чем продолжить.
Робин Котари
8
После того, как вы сделали то, что предложил Робин, начните работать над некоторыми небольшими открытыми проблемами. Вы почувствуете стимул к изучению математики, которая стоит за ней. Как аспирант, я не нахожу очень эффективным изучать некоторые математические области только ради обучения.
Алессандро Косентино

Ответы:

53

Если вы посмотрите на ответы на этот вопрос TCS StackExchange , вы увидите, что существует вероятность того, что практически любая область математики может быть важной в теории сложности. Итак, если вы действительно интересуетесь какой-то областью математики, которая, кажется, не связана, продолжайте и изучайте ее в любом случае. Если это когда-нибудь станет актуальным для теории сложности, вы будете одним из немногих теоретиков сложности, которые это понимают.

Питер Шор
источник
20
Этот ответ не означает, что вы не должны изучать области, которые, как мы знаем , связаны (см. Другие ответы). Я бы сказал, что это линейная алгебра, теория графов, теория вероятностей, базовая абстрактная алгебра и базовая логика.
Питер Шор
6
≠
34

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

С точки зрения математического фона, в дополнение к тому, что упомянуто выше:

  • Теория вероятности
  • Линейная алгебра и абстрактная алгебра
  • теория графов
  • основная логика

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

Суреш Венкат
источник
32

∙AC0

Это (насколько мне известно) единственная опубликованная книга, в которой подробно рассматривается «метод линейной алгебры в комбинаторике» - удобный и мощный инструмент, о котором нужно знать. Существует черновик рукописи Бабая и Франкла, который гораздо глубже, но не опубликован и не находится в сети:

https://cs.uchicago.edu/page/linear-algebra-methods-combinatorics-applications-geometry-and-computer-science

∙

Энди Друкер
источник
2
В том же духе я хочу указать на прекрасно написанное руководство по методу энтропии «Энтропия и счет» Джайкумара Радхакришнана. Метод энтропии - это еще один из тех хитрых инструментов, которые очень приятно применять, когда появляется подходящая возможность.
Арнаб
27

В предыдущих ответах уже перечислены основные: теория вероятностей, комбинаторика, линейная алгебра, абстрактная алгебра (конечные поля, теория групп и т. Д.).

Я бы добавил:

Анализ Фурье , см., Например, курс Райана О'Доннела: http://www.cs.cmu.edu/~odonnell/boolean-analysis/

Теория кодирования , см. Курс Мадху Судана: http://people.csail.mit.edu/madhu/coding/course.html

Теория информации , стандартная книга «Элементы теории информации»: http://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954

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

Дана Мошковиц
источник
5
Большая часть материала, который вы узнаете по ходу дела, в зависимости от того, куда вас ведут исследования / жизнь: с курсов, с лекций, соавторов, из бумаг и т. Д.
Дана Мошковиц
22

Помимо основных вещей, вероятно:

  • Комбинаторика - Вы можете считать себя довольно регулярно
  • Стохастик - для анализа среднего случая и рандомизированных алгоритмов

Мне нравится Конкретная Математика Кнутом. Это дает хороший обзор / базовые знания многих важных инструментов.

Если вы хотите производящие функции (см generationfunctionology по Вильфу) в качестве инструмента, комплексный анализ пригождается, тоже.

Рафаэль
источник
Я люблю Concrete Math, но это немного эзотерично. Сначала я бы порекомендовал более популярную книгу, например «Комбинаторику» Кэмерона.
Эмиль
7
Вот мое впечатление - «Бетонная математика» кажется удивительной книгой, чтобы научиться делать точный (или почти точный) анализ алгоритмов, сильная сторона Кнута. Если это то, что вы хотите сделать, качайте дальше. Но имейте в виду, что большинство работ по теории сложности дают гораздо менее точные границы, поэтому методы КМ менее актуальны.
Энди Друкер
1
Некоторые могут сказать, что это потому, что теоретики сложности - ленивые задницы. Но я думаю, это потому, что (а) точные границы могут потребовать больше усилий, чем это того стоит, (б) часто существует такой большой разрыв между известными верхними и нижними границами, что небольшие уточнения с обеих сторон могут показаться малозначительными.
Энди Друкер
Должен сказать, что в книге есть много разных интересных вещей - мои замечания в основном касаются материала о точных решениях суммирования и рекуррентных отношений.
Энди Друкер
22

У Санджива Арора есть хороший документ для аспирантуры (для студентов 1-го курса), который он преподавал, под названием «инструментарий теоретика», в котором есть много базового материала, который студент должен знать. Многое из этого можно подождать, пока учатся в аспирантуре, но оно даст вам хорошее представление о том, что вам нужно знать, и о некоторых предпосылках.

Лев Рейзин
источник
20

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

«Откуда я знаю, что мне это нужно, если я никогда не видел его раньше?», Спросите вы? Хороший вопрос. Иногда вам везет и вы чувствуете это: «Знаете что, эта подзадача, которую я пытаюсь решить, звучит очень похоже на то, что Фурье преобразует штуковину» Фред не замолчит. Мне придется проверить это или поймать Фреда в ловушку в комнате, и пусть он быстро проведет меня по основам ". В других случаях вы ловите в комнате кучу более знающих людей, чем вы сами, например, выступая на семинаре или что-то в этом роде, и скулите о том, что вы не можете решить эту проблему, пока Фред не скажет: «Эй, держу пари, что вы может решить это с помощью анализа Фурье. Позвольте мне показать вам, как. " В конце концов, вы получаете совместный документ с Фредом, вы узнали что-то новое, и вы с Фредом теперь лучшие друзья и выходите выпивать каждую вторую субботнюю ночь.

TCSgradstudent
источник
18

Я думаю, что список областей математики, которые не являются полезными, будет намного короче, чем список полей, которые являются! Я не могу думать ни о чем.

Изучите любую математику, которая выглядит интересной, и / или то, что вам нужно в данный момент. Даже если вы не используете его напрямую, это поможет вам изучить другие вещи, которые вы делаете.

Jeffε
источник
4
Я второй ответ. Какую бы математику вы не нашли, она покажет, какие проблемы наиболее интересны, а также проблемы, которые вам подходят.
Деррик Столи
12

Я рекомендую взглянуть на эти книги:

Кроме того, темы конференции MFCS (Математические основы информатики) могут помочь вам понять, какие знания вам могут понадобиться. (Предостережение: конференция включает в себя очень сложные темы. Вам не нужно осваивать их. Просто попробуйте получить общую картину.)

М.С. Дусти
источник
9

Теория чисел не упоминалась, но это очень важный инструмент для многих криптографических и теоретико-сложных конструкций.

Арнаб
источник
6

Теория представлений конечных групп (также над конечными полями) может быть удивительно полезна для различных задач, включая:

  • Алгоритмы умножения матриц ( Кон-Клейнберг-Сегеди-Уманс )

  • построение локально декодируемых кодов (см., например, эту статью Клима Ефременко)

  • приложения в квантовых вычислениях (задача о скрытых подгруппах для неабелевых групп, мультипликативный метод противника)

Sn

Марчин Котовски
источник
не забывайте детерминированные конструкции графов расширителей
Сашо Николов
Вы имеете в виду алгебраические конструкции, использующие свойство (T) а-ля Любоцкий? В этом случае это немного отличается от приведенных выше примеров (не используйте IRRES конечных групп).
Марчин Котовски,
4

Я рекомендую прочитать книгу Гэри и Джонсона

Компьютеры и неразрешимость: руководство по теории NP-полноты .

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

Эмиль
источник
1
Я изучил сложность этой книги, но нашел ее несбалансированной, с множеством непростых, но, в конечном счете, неважных деталей, но в ней отсутствует освещение вопросов, которые были важны даже во время написания книги. С другой стороны, это иногда важная справочная работа. Напротив, текст Козена, упомянутый в другом ответе, ясен, всеобъемлющ и современен.
Андрас Саламон
1

Когда-то на курсе бакалавриата CS464 (2002) в UWaterloo CS использовалась вычислительная сложность Christos H. Papadimitriou , Addison-Wesley, 1994.

Перечисленные основные темы включают машины Тьюринга, неразрешимость, сложность времени и полноту NP.

Для справки, просмотрите вашу библиотеку около QA267.G57 (Годдард: Представление теории вычислений , основанной на быстром чтении или двух снятых программах, и ее доступность для меня, кажется, покрывает сторону CS фона; у меня есть ощущение, что некоторые наборы и группы теория с чисто математической стороны также была бы полезна.)

josh0
источник
2
Я хотел бы иметь достаточно репутации, чтобы проголосовать. Почему эти ссылки на один университет и его библиотеку?
Алессандро Косентино
2
FWIW, QA267.G57 - это телефонный номер Библиотеки Конгресса, который является широко используемым стандартом библиотеки. Это не характерно для Университета Ватерлоо (за исключением, возможно, последних цифр).
Эмиль Йержабек