Теория сложности - мой сильный вторичный интерес, но это не мой основной исследовательский интерес, поэтому у меня нет надежды посетить все конференции, прочитать все блоги и убедиться, что толпа «в» cc: me на каждом кусочке горячие новости. Я пытаюсь сделать что-то из этого, но мне интересно,...
При кодировании логики в ассистенте доказательства, таком как Coq или Isabelle, необходимо сделать выбор между использованием поверхностного и глубокого встраивания. При неглубоком встраивании логические формулы записываются непосредственно в логику доказательства теоремы, тогда как при глубоком...
Каковы лучшие нижние границы тока для времени и глубины цепи для
Я заинтересован в том, чтобы получить действительно твердое представление о зависимой типизации. Я прочитал большую часть TaPL и прочитал (если не полностью поглощен) «Зависимые типы» в ATTaPL . Я также прочитал и просмотрел кучу статей о зависимой типизации. Многие дискуссии по теории типов,...
Позвольте мне начать с нескольких примеров. Почему так просто показать, что CVP в P, а так сложно показать, что LP в P; в то время как оба являются P-полными проблемами. Или взять первичность. Композиты проще показывать в NP, чем простые числа в NP (что требовало Pratt) и, в конечном итоге, в P....
Мы знаем, что L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} и что L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , где L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Мы также знаем , что...
Я редактировал студенческую рукопись. Студент заметил, что было бы неплохо увидеть примеры качественного письма в опубликованных работах, и я понял, что не могу придумать хорошие примеры из головы Какие лучшие примеры качественного математического письма вы видели? Правила: Я бы предпочел документы...
Теорема Ладнера гласит, что если P ≠ NP, то существует бесконечная иерархия классов сложности, строго содержащих P и строго содержащихся в NP. В доказательстве используется полнота SAT при многократном сокращении NP. Иерархия содержит классы сложности, построенные по типу диагонализации, каждый из...
В другом потоке Андрей Бауэр определил денотационную семантику как: значение программы является функцией значений ее частей. Что беспокоит меня в этом определении, так это то, что оно, кажется, не выделяет то, что обычно считается денотационной семантикой, из того, что принято считать...
Предположим, у меня есть ориентированный ациклический граф с весами действительных чисел в его вершинах. Я хочу найти топологический порядок DAG, в котором для каждого префикса топологического порядка сумма весов неотрицательна. Или, если вы предпочитаете теоретико-порядковую терминологию, у меня...
Иерархия Хомского (–Schützenberger) используется в учебниках теоретической информатики, но она, очевидно, охватывает только очень небольшую часть формальных языков (REG, CFL, CSL, RE) по сравнению с полной диаграммой зоопарка сложности . Играет ли иерархия какую-либо роль в текущих исследованиях? Я...
Книга Ароры и Барака представляет факторинг как следующую проблему: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}Факторингзнак равно{⟨L,U,N⟩|(∃ простое число п∈{L,...,U})[п|N]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\} Далее в...
Известно, что показатель TSP может быть аппроксимирован в пределах и не может быть аппроксимирован лучше, чем за полиномиальное время. Известно ли что-нибудь о поиске аппроксимационных решений за экспоненциальное время (например, менее шагов только с полиномиальным пространством)? Например, в какое...
Вопрос: Как работает «тактика» у помощников по проверке? Похоже, они являются способами указания того, как переписать термин в эквивалентный термин (для некоторого определения «эквивалентный»). Предположительно, есть формальные правила для этого, как я могу узнать, кто они и как они работают? Они...
Сегодня Райан Уильямс опубликовал статью о arXiv (ранее появившуюся в SIGACT News), содержащую менее техническую версию своего недавнего метода нижней границы ACC . Мой вопрос не о самой технике (конечно, заслуживающей огромной похвалы), а о стиле бумаги. В аннотации он пишет: Доказательство будет...
Неформально говоря, колмогоровская сложность строки - это длина самой короткой программы, которая выводит . Мы можем определить понятие «случайная строка», используя ее ( является случайным, если ). Легко видеть, что большинство строк случайные (коротких программ не так много).х х К ( х ) ≥ 0,99 |...
У меня всегда были проблемы с пониманием важности разрыва целостности (IG) и ограничений на него. IG - это отношение (качества) оптимального целочисленного ответа к (качеству) оптимального реального решения релаксации задачи. Давайте рассмотрим покрытие вершин (VC) в качестве примера. VC можно...
Я ищу гипотезы об алгоритмах и сложности, которые многие считали заслуживающими доверия в какой-то момент времени, но позже они были либо опровергнуты, либо, по крайней мере, опровергнуты из-за растущих контрдоказательств. Вот два примера: Гипотеза случайного оракула: отношения между классами...
Насколько я понимаю, модель Тьюринга стала «стандартом» при описании вычислений. Мне интересно знать, почему это так - то есть, почему модель ТМ стала более широко используемой, чем другие теоретически эквивалентные (насколько мне известно) модели, например μ-Рекурсия Клини или Лямбда-исчисление (я...
Если бы вы могли переименовать динамическое программирование, как бы вы это