Мой вопрос сегодня (как обычно) немного глупый; но я бы попросил вас рассмотреть это. Я хотел знать о происхождении и / или мотивации концепции ширины дерева. Я уверен, что понимаю, что это используется в алгоритмах FPT, но я не думаю, что это было причиной, почему это понятие было определено. Я...
Я хотел бы написать обзор по применению топологии в информатике. Я планирую осветить историю топологических идей в области компьютерных наук, а также выделить несколько текущих событий. Было бы чрезвычайно полезно, если бы кто-то мог дать вклад по любому из вопросов ниже. Существуют ли какие-либо...
За эти годы я привык видеть много теорем TCS, доказанных с использованием дискретного анализа Фурье. Преобразование Уолша-Фурье (Адамара) полезно практически во всех подполях TCS, включая тестирование свойств, псевдослучайность, сложность связи и квантовые вычисления. Хотя мне стало удобно...
Я ищу примеры задач, параметризованных числом , где жесткость задачи немонотонна по k . Большинство проблем (по моему опыту) имеют один фазовый переход, например, k- SAT имеет один фазовый переход от k ∈ { 1 , 2 } (где проблема в P) к k ≥ 3 (где проблема NP- полный). Меня интересуют проблемы, в...
Мы в TCS часто используем мощные результаты и идеи из классической математики (алгебра, топология, анализ, геометрия и т. Д.). Каковы некоторые примеры того, когда это пошло наоборот? Вот некоторые из них, о которых я знаю (а также чтобы дать представление о типе результатов, о которых я...
фон Несколько лет назад, когда я был студентом, нам дали домашнее задание по амортизированному анализу. Я не смог решить одну из проблем. Я спрашивал об этом в теории , но удовлетворительного результата не было. Я помню курс, на котором Т.А. настаивал на том, что он не смог доказать, и сказал, что...
После изучения детерминированных конечных автоматов (DFA) в старшекурснике, я почувствовал, что они очень хорошо поняты. Мой вопрос: есть ли что-то, чего мы до сих пор не понимаем в них. Я имею в виду не обобщения ДФА, а исходные немодифицированные ДФА, которые мы изучаем в старшекурсниках. Это...
Широко распространено мнение, что , оптимальный показатель для умножения матриц, фактически равен 2. Мой вопрос прост:ωω\omega Какие у нас есть основания полагать, что ?ω=2ω=2\omega = 2 Мне известны быстрые алгоритмы, такие как Coppersmith-Winograd, но я не знаю, почему их можно считать...
Я новичок на сайте. На mathoverflow это будет вики сообщества, но я не вижу, как это установить здесь. Не вопрос исследования, но, надеюсь, представляет интерес для профессиональных теоретических компьютерных ученых. Я студент 2-го курса по теории, и мне было интересно, что бы посоветовал...
Каковы общие рекомендации по проверке ваших доказательств? Я считаю, что это важно для аспирантов, как я. Я уже знаю, что нам нужно сделать, чтобы что-то доказать, но вам всегда нужно все проверять, прежде чем отправлять. Даже вашему собственному советнику. Я разработал некоторые стратегии методом...
Этот вопрос я задавался вопросом некоторое время. Когда люди описывают проблему P против NP, они часто сравнивают класс NP с творчеством. Они отмечают, что составление симфонии качества Моцарта (аналог задачи NP) кажется намного сложнее, чем проверка того, что уже составленная симфония имеет...
Знаете ли вы разумные алгоритмы, которые выполняются за полиномиальное время в (Длина ввода + Длина выхода), но у которых асимптотическое время выполнения в той же мере имеет действительно огромную экспоненту / постоянную (по крайней мере, когда доказанная верхняя граница времени выполнения...
В теме Основные нерешенные проблемы теоретической информатики? Иддо Цамерет сделал следующий превосходный комментарий: Я думаю, что мы должны различать основные открытые проблемы, которые рассматриваются как фундаментальные проблемы, такие как P≠NPP≠NP P\neq NP , и основные открытые проблемы,...
При разработке алгоритма для новой задачи, если я не смогу найти алгоритм полиномиального времени через некоторое время, я мог бы попытаться доказать, что он NP-сложный. Если мне это удастся, я объяснил, почему я не смог найти алгоритм полиномиального времени. Не то, чтобы я точно знал, что P! =...
С появлением Интернета (и здравого смысла) появляется все больший спрос на исследования открытого доступа. Некоторые исследователи (включая меня) считают разочаровывающим, что опубликованные рецензируемые исследовательские статьи стоят за платными системами. Я ищу журналы и конференции (связанные с...
Недавно, когда я разговаривал с физиком, я утверждал, что в моем опыте, когда проблема, которая наивно кажется такой, что она требует экспоненциального времени, нетривиально оказывается в P или BPP, обычно можно определить «общую причину», почему происходит сокращение --- и почти всегда эта причина...
Генетические алгоритмы не пользуются большой популярностью в мире теории, но они представляют собой достаточно хорошо используемый метаэвристический метод (под метаэвристическим я подразумеваю технику, которая в целом применяется ко многим задачам, таким как отжиг, градиентный спуск и т. П.)....
Какие инструменты вы используете для написания статей? Исходя из своего небольшого опыта, теоретики тратят много времени на написание и уточнение статей, помимо того, что они на самом деле творческие. То есть, сообщая свою работу другим людям. Может быть, документы не правильный способ сделать...
Цель этого вопроса - собрать примеры из теоретической информатики, где систематическое использование компьютеров было полезным в построении гипотезы, которая приводит к теореме, фальсификация гипотезы или доказательного подхода, построение / проверка (части) доказательства. Если у вас есть...
Я сталкивался с полиномиальным алгоритмом, который решает 2SAT. Мне показалось удивительным, что 2SAT находится в P, где все (или многие другие) экземпляры SAT являются NP-Complete. Что отличает эту проблему? Что делает его таким простым (NL-Complete - даже проще, чем...