Я преподаю курс по структурам данных и в начале следующей недели расскажу о деревьях сплайнов. Я много раз читал статью о деревьях сплайнов и знаком с анализом и интуицией, стоящими за структурой данных. Тем не менее, я не могу найти твердую интуицию для потенциальной функции, которую Слеатор и...
Мы говорим , что НКА является постоянно Неоднозначность , если существует K ∈ N такое , что любое слово W ∈ Е * принимается либо 0 или (точно) К путям.MMMk∈Nk∈Nk\in \mathbb{N}w∈Σ∗w∈Σ∗w\in \Sigma^*000kkk Если автомат постоянно неоднозначен при k = 1 , то M называется однозначным FA...
Любой язык, не являющийся полным по Тьюрингу, не может написать для себя интерпретатор. Я понятия не имею, где я это прочитал, но я видел, что это использовалось несколько раз. Кажется, что это порождает своего рода «окончательный» нетуринговский законченный язык; те, которые могут...
Недавно у меня была беседа с другом (сторонником строго типизированных языков). Он сделал комментарий: Изобретатели Lambda Calculus всегда предполагали, что он будет напечатан. Теперь мы видим , что церковь была связана с в Просто типизированных лямбда - исчислению . Действительно, кажется, что он...
Мне нужен список полных языков . Есть две такие проблемы, перечисленные в зоопарке сложности , а именно:Σp2Σ2p\Sigma_2^p Минимальный эквивалент DNF. Учитывая формулу DNF F и целое число k, существует ли формула DNF, эквивалентная F с k или меньшим числом вхождений литералов? Кратчайший имплицит....
Следующая проблема появляется в списке Ааронсона « Десять полуградовых вызовов для теории квантовых вычислений» . IsB Q P = B P PB Q N CВQпзнак равноВппВQNС\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} р о л у л о г (п) В В Р В Р Р Б В Н С Другими словами, может ли «квантовая» часть любого квантового...
Существует ли общая теорема, которая при надлежащей дезинфекции утверждает, что наиболее известные результаты, касающиеся использования действительных чисел, могут фактически использоваться при рассмотрении только вычислимых вещественных чисел? Или существует правильная характеристика результатов,...
Пусть орграф (не обязательно DAG) и . Что является сложность подсчета количества простой путей в . GGGs,t∈V(G)s,t∈V(G)s,t \in V(G) s−ts−ts-tGGG Я ожидал бы, что проблема будет # -полной, но не смог найти точную ссылку. PP{\mathsf P} Также обратите внимание, что на ряд похожих вопросов были даны...
Я ищу однопроходный алгоритм, который вычисляет четность перестановки. Я предполагаю, что входная перестановка задается потоком . Выходными данными должно быть соотношение перестановок. Вопрос, который меня интересует, сколько памяти должен использовать детерминированный алгоритм. Есть ли...
Глядя на блог по теории гомотопических типов, можно легко найти множество библиотек, формализующих большую часть теории гомотопических типов в Agda и Coq. Кто-нибудь знает, есть ли подобная попытка формализовать HoTT в Идрисе...
Я читал, что целочисленное линейное программирование разрешимо за полиноминальное время, если число переменных фиксировано, т.е. n ∈ O ( 1 ) . Если число переменных растет логарифмически, т. Е. N ∈ O ( log 2 ( N ) ) для заданного входного значения размера N , проблема все еще разрешима за...
Принцип 0-1 говорит, что если сеть сортировки работает для всех последовательностей 0-1, то она работает для любого набора чисел. Существует ли такое, что если сеть сортирует каждую последовательность 0-1 из S, то она сортирует каждую последовательность 0-1, а размер S является полиномиальным по n...
Подсчет треугольников в общих графах можно сделать тривиально за раз, и я думаю, что делать намного быстрее сложно (ссылки приветствуются). Как насчет планарных графиков? Следующая простая процедура показывает, что это можно сделать за O ( n log n ) времени. У меня вопрос...
Я представлю свою проблему на примере. Скажем, вы разрабатываете экзамен, который состоит из определенного набора независимых вопросов (которые кандидаты могут получить как правильно, так и неправильно). Вы хотите принять решение о балле, который нужно дать для каждого из вопросов, при этом правило...
Пусть AA и BB - подмножества {0,…,n}\{0,\ldots,n\} . Нам интересно найти сумму Минковского A+B={a+b | a∈A,b∈B}A+B=\{a+b~|~a\in A,b\in B\} . χX:{0,…,2n}→{0,1}\chi_X:\{0,\ldots,2n\}\to \{0,1\} является характеристической функциейXX еслиχX(x)={1 if x∈X0 otherwise\chi_X(x) = \begin{cases} 1 \text{ if }...
В формальном описании автоматов детерминированного пушинга они разрешают перемещения, когда машина может вставлять или помещать символы в стек без чтения символа из ввода. Если эти перемещения недопустимы, а стек может быть изменен только один раз после каждого чтения символа, равны ли полученные...
Смешанный граф - это граф, который может иметь как направленные, так и ненаправленные ребра. Его лежащий в основе ненаправленный граф получается путем забывания ориентации направленных ребер, а в другом направлении ориентация смешанного графа получается путем назначения направления каждому...
В ответ на вопрос, заданный мне Грегом Купербергом, мне интересно, есть ли какие-нибудь статьи, которые определяют и изучают классы сложности языков, допускающие различные виды доказательств знания . Такие классы, как SZK и NISZK, являются чрезвычайно естественными с точки зрения сложности, даже...
Какие примеры пар классов сложности и B такие, чтоAAABBB мы не знаем, является ли , иA=BA=BA=B мы также не знаем противоречивых релятивизаций (т. е. мы не знаем оракулов и Q таких, что A P = B P и A Q ≠ B Q )?PPPQQQAP=BPAP=BPA^P = B^PAQ≠BQAQ≠BQA^Q \ne B^Q Чтобы сформулировать вопрос по-другому,...
Многие публикации по компьютерным наукам 1950-х и 1960-х годов содержат захватывающие философские рассуждения о природе ума и значении информации по отношению к физическому миру. Известными примерами являются «Тест Тьюринга», «Расчет пространства» Цузе, «Это из бит» Уилера и т. Д. Сегодня такие...