Как вы получаете «Физическую интуицию» для результатов в TCS?

Извините, если этот вопрос немного расплывчат, но мне любопытно, как успешные исследователи «чувствуют» результаты в TCS.

Например, линейная алгебра может пониматься геометрически или в терминах ее физических интерпретаций (собственные векторы могут рассматриваться как «устойчивые точки» в системе) и т. Д. Также интуитивно понятно, что существует протокол IP для TQBF (как IP Протокол может быть визуализирован как своего рода «игра» между двумя объектами, сильно отличающимися вычислительной мощностью). Тем не менее, я считаю, что многие результаты, даже очень простые в TCS, не имеют такой простой интуиции (MA AM). Еще хуже то, что иногда неочищенные интуиции оказываются крайне осторожными (2-SAT находится в P, в то время как 3-SAT, как полагают, не находится в P (фактически, NP-завершен)). Существуют ли «общие принципы» для развития интуиции в TCS?$\subseteq$

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

Есть несколько основных упражнений, которые вы можете использовать, чтобы попытаться создать интуицию для какой-то статьи, которую вы читаете и не можете ее понять. Вот то, что я до сих пор делаю время от времени. Начните с доказательства, которое вы не понимаете, но очень хотите, и это очень долго. Читая каждый абзац доказательства, попробуйте написать предложение своими словами о том, что, по вашему мнению, говорится в абзаце, на полях. Надеемся, что доказательство написано достаточно хорошо, чтобы в доказательстве были четко определенные «части» («сделайте X, затем определите новую функцию f, затем примените X к f, ...»). Если нет, то из ваших предложений отделите доказательство на свои части.

Теперь для каждой части попробуйте написать предложение (своими словами) о том, что делает каждая часть. В этот момент может оказаться, что ваши предыдущие предложения не совсем точны или плохо сочетаются друг с другом (ваша интуиция была «выключена»), поэтому вы можете уточнить их, чтобы они логически соответствовали друг другу. Теперь у вас есть несколько предложений, обобщающих все доказательства. Тогда (теперь эта последняя часть от моего советника, Мануэля Блюма) попытайтесь придумать одно слово или фразу для всего этого. Эта фраза будет ключевой идеей, которая, по вашему мнению, и является началом всего спора. (Например, большинство доказательств существования с помощью вероятностного метода можно суммировать с помощью «PICK RANDOM». В случае$MA \subseteq AM$Я бы сказал что-то вроде «СДЕЛАЙТЕ АРТУРА ГОВОРИТЕ БОЛЬШЕ». Но, может быть, что-то еще в доказательстве кажется вам «ключевой» идеей, что совершенно нормально. Это твоя интуиция!)

Я предполагаю, что мое предложение может быть полезно для большинства математики, но я нашел его очень полезным для TCS, где многие доказательства действительно сводятся к 1-2 действительно новым идеям, а остальные представляют собой синтез этой идеи с тем, что уже было известно.

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

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

Поскольку вы считаете игры примером «физической интуиции», а я не вижу ничего, связанного с физикой в ​​играх, я предполагаю, что вы делаете упор не на «физической», а на «интуиции».

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

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

Что касается конкретного результата, я не согласен с тем, что для MA⊆AM не существует простой интуиции. (Предупреждение: в настоящее время я сам изучаю этот и связанные с ним результаты, и я могу сказать что-то неправильное.) В системе МА Мерлин должен дать один ответ, который соответствует большинству случайных последовательностей, используемых Артуром. Мы меняем систему так, что Артур посылает несколько (полиномиально много) случайных последовательностей Мерлину, и Мерлин должен дать один ответ, который подходит всем им, что кажется мне естественным испытанием. Доказательство надежности этой системы AM является простым приложением границы Чернова. Я не думаю, что что-то в этом результате концептуально трудно понять.

Маргинально связанный: Ваш вопрос напомнил мне о прекрасном посте в блоге « Абстракция, интуиция и« ошибка учебного монады » » Брента Йорджи, где он объяснил сложность передачи интуиции вымышленным не объяснением «Монады - это буррито». Если приведенное выше объяснение того, как работает доказательство MA⊆AM, не имеет никакого смысла, я мог бы продемонстрировать ту же ошибку. :(

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

Вы научитесь знать, как X ведет себя, как он себя чувствует, как он реагирует на ваши манипуляции и в каком районе он живет. Вы узнаете, кто это обнаружил, когда и почему, и что другие сделали с X, успешно или безуспешно. Вы будете знать X так же, как вы знаете любой физический объект, с которым вы сталкиваетесь каждый день.

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

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

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

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

Тот же метод работает, если вы читаете новую статью, и хотите получить больше интуиции, чем та, которую дает чтение.

В моем собственном случае большинство концепций TCS, о которых я чувствую, что у меня есть какая-то интуиция, - это те, на которые я опирался с помощью практических результатов. Если я обнаруживаю, что развиваюсь и успешно использую одну и ту же модель или алгоритм в течение многих лет, это все больше отвлекает меня, пока я не могу понять, почему алгоритм был успешным. Это особенно верно, если пришло время для переписывания - я хочу знать, в чем суть TCS, чтобы не потерять волшебную пыль при рефакторинге. Чтобы понять все это, как правило, требуется (для меня) глубокое погружение в 1936 г. или около того, и связь того, что я делал, с этими основными понятиями. Однажды мой друг посоветовал мне «думать как машина Тьюринга», когда я был на одном из этих погружений, и этот совет застрял у меня в голове.