Описательная сложность классифицирует проблемы на основе того, насколько сложно выразить проблему в некотором логическом формализме.
Теорема Иммермана-Варди утверждает, что PTIME (или P) - это именно тот класс языков, который может быть описан предложением логики первого порядка вместе с оператором с фиксированной точкой над классом упорядоченных структур. Оператор с фиксированной точкой может быть либо с наименьшей...
Название более или менее говорит само за себя, но я думаю, я мог бы добавить немного фона и некоторые конкретные примеры, которые меня интересуют. Теоретики описательной сложности, такие как Иммерман и Фагин, охарактеризовали многие из наиболее известных классов сложности с использованием логики....
Кажется, известно, что для того, чтобы найти ответ на запрос по реляционной базе данных , нужно время , и невозможно избавиться от показателя степени,QQQDDD|D||Q||D||Q||D|^{|Q|}|Q||Q||Q| Поскольку может быть очень большим, мы задаемся вопросом, почему базы данных вообще работают на практике.DDD...
Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...
Бумага Лаури Хелла и Хосе Мария Turull-Torres, Вычисление запросов с помощью логики высшего порядка , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 предлагает логику VO, логику переменного порядка. Это позволяет определять количество заказов по переменным. VO довольно мощный и может...
CMSOL - это подсчет монадической логики второго порядка, т. Е. Логики графов, в которой доменом является множество вершин и ребер, существуют предикаты для смежности вершин и вершин, существует ребро-вершина, существует количественное определение по ребрам, вершинам, наборам ребер и вершинам....
Пусть - перестановка. Обратите внимание, что хотя действует на бесконечной области, его описание может быть конечным. Под описанием я имею в виду программу, которая описывает функциональность . (Как и в колмогоровской сложности.) См. Пояснения ниже. π ππ:{0,1}∗→{0,1}∗π:{0,1}∗→{0,1}∗\pi \colon...
В этом вопросе было отмечено, что существуют версии описательной сложности теоремы Райса. Я нашел доказательство следующей теоремы: Учитывая класс сложности C , нетривиальные свойства языков в C не могут быть вычислены в C Ранее я опубликовал найденное мной доказательство, но поскольку оно было...
Контекст: мы рассматриваем только орграфы. Пусть CYCLE будет языком графов с циклом; это NL-полная проблема. Пусть HASEDGE будет языком графов с хотя бы одним ребром. Тогда не тривиально, CYCLE∪HASEDGECYCLE∪HASEDGE\text{CYCLE} \cup \text{HASEDGE} больше не NL-трудно, в то время как...
Хорошо известно , что некоторые классы NP -проблемы Have дихотомии теорем, которые гарантируют , что каждая задача в классе является либо NP -полное или находится в P . Наиболее известным таким результатом является теорема Шефера о дихотомии , а также ряд обобщений. Насколько я понимаю, доказать...
В зоопарке сложности говорится [ 1 ], что в описательной сложности может быть определен тремя различными типами формул: который также является , а также как .ппPFO ( L Fп)FО(LFп)FO(LFP)FO ( nO ( 1 ))FО(NО(1))FO(n^{O(1)})SO ( HO R N)SО(ЧАСОрN)SO(HORN) Однако есть некоторые исключения, например, не...
Мой вопрос касается теории конечных моделей / описательной сложности, поэтому будет означать «первый порядок по конечным двоичным словам с использованием предикатов Rs и унарного предиката P true в позиции 1 в слове».FO ( R )FО(р)FO(R) Я хотел бы знать, есть ли какая-либо характеристика с R любым...
Я пытаюсь понять статью о p-оптимальных системах доказательства и логике для PTIME . В статье есть понятие, называемое системами доказательства, и я не понимаю интуиции: Σ = { 0 , 1 }Σ={0,1}\Sigma = \{0,1\} ... Мы выявляем проблемы с подмножествами QQQ в Σ*Σ∗\Sigma^*, Я думаю, что интуиция...
Чтобы лучше понять статью, я пытаюсь получить краткое представление о логике с наименьшей фиксированной точкой. Есть несколько моментов, в которых я застрял. Если G=(V,E)G=(V,E)G = (V,E) это график и Φ(P) = { ( a , b ) ∣G⊨E( а , б)∨P( а , б )∨∃z(E( а,z)∧P(z, б ) ) }Φ(п)знак...
Закрыто. Этот вопрос не по теме . В настоящее время он не принимает ответы. Хотите улучшить этот вопрос? Обновите вопрос так, чтобы он соответствовал теме теоретической информатики в стеке. Закрыто 7 лет назад . Как мы можем выразитьP=PSPACEP=PSPACEP=PSPACE"как формула первого порядка? Какой...