Извините, если этот вопрос немного расплывчат, но мне любопытно, как успешные исследователи «чувствуют» результаты в TCS. Например, линейная алгебра может пониматься геометрически или в терминах ее физических интерпретаций (собственные векторы могут рассматриваться как «устойчивые точки» в системе)...
Хорошо известно, что если то иерархия полиномов разрушается и .P = N PP=NP\mathbf{P}=\mathbf{NP}P = P HP=PH\mathbf{P}=\mathbf{PH} Это можно легко понять индуктивно с помощью оракулов. Вопрос в том, почему мы не можем продолжить индуктивный процесс за пределами постоянного уровня чередований и...
Я преподаю курс по структурам данных и в начале следующей недели расскажу о деревьях сплайнов. Я много раз читал статью о деревьях сплайнов и знаком с анализом и интуицией, стоящими за структурой данных. Тем не менее, я не могу найти твердую интуицию для потенциальной функции, которую Слеатор и...
Я ищу примеры результатов, которые идут вразрез с интуицией людей для общей аудитории. Результаты, которые, если спросить у неэкспертов «что говорит ваша интуиция?», Почти все ошиблись бы. Заявление о результатах должно быть легко объяснимо для студентов в CS / математике. Я в основном ищу...
Я пытался обернуть голову вокруг того, что, почему и как вычислить, но я не могу понять, «почему это работает»?λλ\lambda «Интуитивно» я получаю модель вычислимости машин Тьюринга (ТМ). Но эта абстракция просто оставляет меня в замешательстве.λλ\lambda Давайте предположим, что ТМ не существуют -...