Пусть - формула 2CNF, а k - неотрицательное целое число. В этой статье доказано, что проблема принятия решения о том, можно ли удалить не более k предложений, чтобы сделать φ выполнимой, задается с фиксированным параметром, где k - параметр. Мой вопрос заключается в том, есть ли какие-либо работы,...
является класс схем полиномиального размера постоянной глубины с не воротами и неограниченным вентилятором-в И и ИЛИ воротах, где входы и ворота также имеют неограниченное разветвление.A C0AC0AC^0 Теперь рассмотрим новый класс, назовите его который похож на A C 0, но для которого входы и вентили...
Быстрая версия Существуют ли модели декогеренции для квантового блуждания на линии, чтобы мы могли настроить блуждание так, чтобы оно распространялось как для любого ?1 / 2 ≤ K ≤ 1Θ(tk)Θ(tk)\Theta(t^k)1/2≤k≤11/2≤k≤11/2 \leq k \leq 1 мотивация Классические случайные блуждания полезны при разработке...
Мы знаем, что если то весь PH разрушается. Что если полиномиальная иерархия частично разрушится? (Или как понять, что PH может рухнуть выше определенной точки, а не ниже?)п= NпP=NPP=NP Короче говоря, каковы будут последствия и P ≠ N P ?Nп= с о нпNP=coNPNP=coNPп≠ NпP≠NPP\ne...
Обычно энтропия Шеннона используется для доказательства результатов канального кодирования. Даже для результатов разделения канала источника используется энтропия Шеннона. Учитывая эквивалентность между Шенноном (глобальным) и колмогоровским (локальным) понятиями информации, проводилось ли...
В главе 10 HAC (10.4.2) мы видим хорошо известный протокол идентификации Фейге-Фиат-Шамира, основанный на доказательстве с нулевым знанием, использующем (предполагаемую) сложность извлечения квадратных корней по модулю композита, который трудно проанализировать. Я дам схему своими словами (и,...
Уникальная SAT является хорошо известной проблемой: учитывая формулу CNF , верно ли, что F имеет ровно одну модель?FFFFFF Меня интересует проблема «точно -SAT»: учитывая формулу CNF F и целое число m > 1 , правда ли, что F имеет ровно m моделей?мmmFFFm > 1m>1m>1FFFmmm Обе проблемы выглядят...
Мне интересно, каковы последние достижения в теории реляционных баз данных и смежных областях? Меня интересуют новые подходы, языки запросов (альтернативы SQL и / или расширениям к нему), продукты (проприетарные и открытые, хотя я гораздо больше интересуюсь открытым исходным кодом) и...
Какие стандартные задачи мы можем уменьшить, чтобы доказать нижних оценок?Ω(nlogn)Ω(nlogn)\Omega(n\log n) Конечно, проблемы состояния, отличные от сортировки и четкости элементов....
В моей работе возникает следующая проблема: Существует ли известный алгоритм, который аппроксимирует хроматическое число графа без независимого набора порядка 65? (Таким образом, альфа (G) <= 64 известна, а | V | / 64 - тривиальная нижняя, | V | тривиальная верхняя граница. Но существуют ли...
Я нашел проблему в доказательстве понижения субъекта Барендрегтом (Thm 4.2.5. Лямбда-исчисления с типами ). Последний шаг доказательства (стр. 60) гласит: "и, следовательно, по лемме 4.1.19 (1), Γ,x:ρ⊢P:σ′Γ,x:ρ⊢P:σ′\quad\Gamma,x:\rho\vdash P:\sigma' . " Однако согласно лемме 4.1.19 (1) это должно...
Рассмотрим следующую задачу проверки принадлежности к абелевой подгруппе . Входы: Конечная абелева группа с произвольно большим .G = Zd1× Zd1… × ZdмG=Zd1×Zd1…×ZdmG=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}dяdid_i Производящая-набор { ч1, ... , чN}{h1,…,hn}\lbrace...
Как хорошо известно, задачи NP-hard оптимизации могут иметь много разных коэффициентов аппроксимации, начиная от PTAS и заканчивая отсутствием аппроксимации ни по одному фактору. Между ними у нас есть различные константы, , и т. Д.p o l y ( n )O ( журналн )O(logn)O(\log n)р о л у( н...
Я ищу язык L со следующими свойствами: L не должен быть контекстно-свободным. Дополнение L не должно быть контекстно-свободным. (Все, что вы видите в учебниках как главные примеры неконтекстно-свободных языков, похоже, не соответствует этому второму требованию.) L не должен быть слишком сложным....
Вес |x||x||x|двоичной строки x∈{0,1}nx∈{0,1}nx\in\{0,1\}^n - количество единиц в строке. Что произойдет, если мы заинтересованы в вычислении монотонной функции на входах с несколькими из них? Мы знаем, что решить, имеет ли граф клик, сложно для монотонных цепей (см., Среди прочего, Alon Boppana,...
Учитывая endofunctor , мы можем определить функции наблюдения как функции , которые являются полиморфными для любого F -коалгебры, то есть о б ы определена для любого F -коалгебры ⟨ A , гр : A → F A ⟩ . о б ы : ∀ ⟨ А , с ⟩ . A → B Другой способ рассмотрения функций наблюдения - это функции...
Обычно проще рассуждать о исчислении, где ограничение - это конечность вычислений, а не порог, подобный «вычислимому за полиномиальное количество времени». В теории формальных языков, например, вместо использования чтобы охарактеризовать апериодический моноид, проще использовать проконечные слова,...
Я просто хочу знать некоторые примеры функций, которые могут быть вычислены нетипизированным лямбда-исчислением, но не типизированными лямбда-исчислениями. Поскольку я новичок, некоторые повторение справочной информации будет оценено. Благодарю. Редактировать: набрав лямбда-исчисление, я...
Скажем, у кого-то есть язык , но вы не знаете, какие строки на самом деле являются частью языка. Все, что есть, - это конечное представление языка: конечный набор строк о которых известно, что они есть в языке, и конечный набор строк , которые известны не быть на языке.L⊆Σ∗L⊆Σ∗L \subseteq...
Я ищу быстрый алгоритм для расчета максимального потока в динамических графиках. то есть, учитывая граф и s , t ∈ V, мы имеем максимальный поток F в G от s к t . Затем новый / старый узел u добавляется / удаляется с соответствующими ему ребрами для формирования графа G 1 . Каков максимальный поток...