У Клопа, ван Оострома и де Врийера есть статья о лямбда-исчислении с узорами. http://www.sciencedirect.com/science/article/pii/S0304397508000571 В некотором смысле шаблон - это дерево переменных - хотя я просто думаю о нем как о вложенном кортеже переменных, например, ((x, y), z), (t, s)). В статье...
В Приложении B « Повышение и дифференциальная конфиденциальность » Дворка и др. Авторы приводят следующий результат без доказательств и называют его неравенством Азумы: Пусть - действительные случайные величины, такие что для каждого ,C1,…,CkC1,…,CkC_1, \dots, C_ki∈[k]i∈[k]i \in [k]...
Кто первым показал, что язык находится в NP, если сертификат для языка можно проверить за полиномиальное время? У нас есть документ, который формально доказывает это? Когда сообщество TCS начало преуменьшать недетерминизм в пользу проверяемости? Для жизни я не могу найти хорошую ссылку на это...
Я хочу быть очень конкретным. Кто-нибудь знает опровержение или доказательство следующего предложения: ∃p∈Z[x],n,k,C∈N,∃p∈Z[x],n,k,C∈N,\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N}, ∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),∀G,H∈STRUC[Σgraph](min(|G|,|H|)=n,G≄H),\forall G, H \in...
Заранее извиняюсь за этот мягкий вопрос, на который нет закрытого, правильного ответа. Это, вероятно, лучший форум, чтобы задать мой вопрос. Я студент третьего курса теоретической группы из 15 лучших школ США. До сих пор я неплохо справлялся. У меня есть первая авторская теоретическая статья и...
Предположим, вам даны два детерминированных автомата нажатия, которые распознают языки и B , и хотите определить, существует ли регулярный язык R такой, что A ⊆ R и R ∩ B = ∅ . По сути, задача состоит в том, чтобы определить, существует ли DFA, способный распознавать, из какого из двух языков...
В недавнем препринте https://arxiv.org/abs/1801.00776 утверждается, что вещественных чисел можно отсортировать по времени и линейному пространству. Статья кажется разумной, хотя я не эксперт в алгоритмах сортировки.nnnO(nlogn−−−−√),O(nlogn),O(n \sqrt{\log n}), Если это правильно, это будет...
Есть исследователь, показывающий, что стирающий бит должен потреблять энергию, а сейчас проводится какое-либо исследование среднего потребления энергии алгоритмом с вычислительной сложностью ? Я предполагаю, что вычислительная сложность F ( n ) коррелирует со средним потреблением энергии, надеюсь,...
Представьте, что у нас есть два размера mmm наборов точек X,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^n . Какова (временная) сложность тестирования, если они отличаются только ротацией? : существует матрица вращения OOT=OTO=IOOT=OTO=IOO^T=O^TO=I такая, что X=OYX=OYX=OY ? Здесь возникает проблема...
Недавно я попытался реализовать Cedille-Core Аарона , минималистский язык программирования, способный доказывать математические теоремы о своих собственных терминах. Я также доказал индукцию для λ-кодированных типов данных на нем, что прояснило, почему его расширения были бы необходимы. Тем не...
Есть ли машина Тьюринга, которая может решить, остановятся ли почти все другие машины Тьюринга? Предположим, у нас есть некоторое перечисление машин Тьюринга и некоторое представление о «размере» набора натуральных чисел ‖ ⋅ ‖ , и мы определяем:N→{Mi}N→{Mi}\mathbb{N} \rightarrow \{M_i\}∥⋅∥‖⋅‖\|...
Помимо научных кругов, которые, несомненно, являются домом для теоретиков, меня интересуют промышленные работы, связанные с теоретической информатикой, которые требуют чисто математического образования....
Рассмотрим функцию вычисляется с помощью булевой схемы C с п входами размера сек ( п ) = р ø л у ( п ) в базисе { Х О Р , Н Д , Н О Т } (с полустепень захода 2 для X O R , A N D ворота).еffСCCNnns ( n ) = p o l y ( n )s(n)=poly(n)s(n) = \mathsf{poly}(n){ X O R , A N D , N O T...
Пусть С4C4C_4 - цикл с четырьмя вершинами. Для произвольного графа GGG с nnn вершинами и m ребрами скажем m>nn−−√m>nnm>n\sqrt n , сколько существуетC4C4C_4? Есть ли нижняя граница для...
Я студент третьего курса университета «топ-20», который работает над мелкозернистой сложностью (много игр с 3-SUM, OV и обычными популярными гипотезами о твердости). Я был довольно продуктивным в течение последнего года или около того, и у меня есть 3 принятых документа и два представленных...
Хорошо известно, что дополнение к зависит от контекста. Но как насчет дополнения ?{ww∣w∈Σ∗}{ww∣w∈Σ∗}\{ ww \mid w\in \Sigma^*\}{www∣w∈Σ∗}{www∣w∈Σ∗}\{ www \mid w\in
Отсюда я читаю доказательства и наткнулся на техническую (хотя и крайне важную) проблему. Я знаю, что это довольно специфично, и контекст проблематичен, но я не мог понять это сам. На страницах 51 и 55 после представления «стандартных» верификаторов они поворачиваются, чтобы модифицировать...
Предположим, что у каждого есть рандомизированный (BPP) алгоритм AAA использующий рrr битов случайности. Естественные способы увеличить вероятность успеха до 1 - δ1−δ1-\delta для любого выбранного δ> 0δ>0\delta>0 : Независимые прогоны + голосование большинством: прогоните AAA независимо T= Θ...
Я особенно заинтересован в их использовании в приложениях для проверки моделей. У меня есть открытые, закрытые и смешанные сети очередей с разными классами клиентов по Baskett et al. Любые другие предложения для чтения материала?...
В ориентированном графе , , если - DAG (направленный ациклический граф), называется множеством дуг обратной связи. F ⊂ E G ∖ F FG = ( V, E)G=(V,E)G=(V,E)F⊂ EF⊂EF\subset EG ∖ FG∖FG\setminus FFFF Если каждое ребро связано с весом , минимальная проблема набора дуги обратной связи по стоимости состоит...