Какой самый быстрый из известных алгоритмов изоморфизма неориентированных
Это расширение классической проблемы секретаря . В игре найма у вас есть набор кандидатов C={c1,…,cN}C={c1,…,cN}\mathcal C=\{c_1,\ldots,c_N\}и приказ о том, насколько квалифицирован каждый работник. Wlog, мы предполагаем, что c1c1c_1 самый опытный, а затем c2c2c_2, так далее. Порядок проведения...
Я изучаю гипотезу об уникальных играх и известное сведение к Max-Cut из Khot et al. Из их статьи и из других источников в Интернете большинство авторов используют (что для меня является) неявную эквивалентность между сокращением MAX-CUT и созданием конкретных тестов для длинных кодов. Из-за моей...
Цветной граф можно описать как кортеж где - граф, а - раскраска. Два цветных графа и называются изоморфными, если существует такой изоморфизм , что выполняется раскраска, т.е. для всех v \ в V (G) .(G,c)(G,c)(G,c)GGGc:V(G)→Nc:V(G)→Nc : V(G) \rightarrow...
Рассмотрим произвольную контекстно-свободную грамматику гGG по алфавиту { 0 , 1 ,0¯¯¯,1¯¯¯}{0,1,0¯,1¯}\lbrace 0,1,\overline{0} ,\overline{1} \rbrace, К произведениям этой грамматики добавьте два фиксированных неконтекстно-свободных произведения.пPP: 0¯¯¯0 → ϵ0¯0→ϵ\overline{0} 0 \rightarrow \epsilon...
Из теоремы Черча мы знаем, что определение выполнимости первого порядка вообще неразрешимо, но есть несколько методов, которые мы можем использовать для определения выполнимости первого порядка. Наиболее очевидным является поиск конечной модели. Однако в логике первого порядка есть ряд утверждений,...
Позволять еff быть Nnnмногочлен, заданный в виде арифметической схемы размера поли(N)(n)(n), и разреши пзнак равно2Ω(N)p=2Ω(n)p = 2^{\Omega(n)} быть простым. Можете ли вы проверить, если еff тождественно ноль ZпZp\mathbb{Z}_p, со временем поли(N)poly(n)\mbox{poly}(n) и вероятность ошибки...
Рейнольдс первоначально предложил реляционную семантику для полиморфного лямбда-исчисления второго порядка [1]. Однако позднее он показал [2], что этот подход не согласуется с классической теорией множеств. Питтс описал структуру гипердоктринных моделей и топос-моделей [3], которые согласуются с...
Случайные леса имеют репутацию среди самых эффективных методов классификации. Тем не менее, мы не сталкиваемся с ними в учебно-теоретической литературе, из которой я предполагаю отсутствие глубоких теоретических результатов. Если бы кто-то хотел вникнуть в эту теорию, с чего бы...
Большинство современных методов криптографии зависят от сложности факторизации чисел, являющихся произведением двух больших простых чисел. Насколько я понимаю, это сложно только до тех пор, пока метод, использованный для генерации больших простых чисел, не может быть использован в качестве ярлыка...
Давайте исправим кодировку машин Тьюринга и универсальной машины Тьюринга U, которая на входе (T, x) выводит все выходные данные T на входе x (возможно, оба работают вечно). Определим колмогоровскую сложность x, K (x) как длину самой короткой программы p, такой, что U (p) = x. Существует ли N...
Я ищу ссылки на следующую задачу: с учетом целых чисел и перечислить все неизоморфные плоские графы по вершинам и ширине дерева . Меня интересуют как теоретические, так и практические результаты, но в основном практические алгоритмы, которые можно кодировать и запускать для максимально больших...
Этот вопрос двоякий и в основном ориентирован на справочную информацию: Есть ли где-нибудь, где даны основные интуиции для доказательства теоремы о графе, не вдаваясь в подробности? Я знаю, что доказательство длинное и сложное, но, безусловно, должны быть ключевые идеи, которые можно донести проще....
Один из моих проектов Java является ответвлением пропаренного , и в отличие от, скажем, Antlr или JavaCC, парсеры генерируются во время выполнения. Генерируемые грамматики - это грамматики синтаксического анализа или PEG (я слышал, что для них используется другой термин - «packrat»). Хотя генерация...
Я хочу знать, может ли быть доказана разрешимость равенства двух разрешимых доказательств одного и того же предложения без каких-либо дополнительных аксиом в исчислении индуктивных построений. В частности, я хочу знать, правда ли это, без каких-либо дополнительных аксиом в Coq....
Меня интересует вариант соответствия максимального веса на графике, который я называю «Максимальное соответствие соответствия». Предположим, что график заполнен (т.е. E=V×VE=V×VE=V\times V), Имеет четное число вершин, и что вес задается функцией прибыль . Для совпадающего обозначим через прибыль...
Меня интересуют эффективные алгоритмы пересечения DFA для особых случаев. А именно, когда DFA пересекаются, подчиняются определенной структуре и / или работают по ограниченному алфавиту. Есть ли источник, где я могу найти алгоритмы таких случаев? Чтобы не делать вопрос слишком широким, особый...
Экземпляр: неориентированный графGGGс двумя выделенными вершинами и целым числом .s≠ts≠ts\neq tk≥0k≥0k\geq 0 Вопрос: существует ли путь в , такой, что путь пересекает не болееs−ts−ts-tGGGkkkтреугольники? (Для этой задачи говорят, что путь пересекает треугольник, если путь содержит хотя бы одно...
Позволять G = ( V, E)гзнак равно(В,Е)G=(V,E)быть графом Набор вершинИкс⊆ VИкс⊆ВX\subseteq Vназывается критическим, еслиИкс≠ ∅Икс≠∅X\neq\emptyset и нет вершины в В∖ XВ∖ИксV\setminus X смежна ровно с одной вершиной в ИксИксX, Проблема состоит в том, чтобы найти множество вершинS⊆ VS⊆ВS\subseteq V...
Я ищу доказательство того, что колмогоровская сложность невычислима, используя редукцию из другой невычислимой задачи. Общим доказательством является скорее формализация парадокса Берри, чем сокращение, но должно быть доказательство путем сокращения из чего-то вроде проблемы остановки или проблемы...