Когда мы хотим доказать , что является -полных, то стандартный подход выставляться полиномиальное время вычислимой сокращение многих один из известного -полных задачи в . В этом контексте нам не нужно жестко ограничивать время выполнения сокращения. Достаточно иметь любую полиномиальную границу,...
Я ищу: Майкл О. Рабин, «Степень сложности вычисления функции и частичное упорядочение рекурсивных множеств», Еврейский университет, Иерусалим, 1960 Резюме: «Мы пытаемся измерить объем работы, свойственный задаче вычисления заданной вычислимой (рекурсивной) функции. Представлено и изучено понятие...
Лэнс Фортноу недавно заявил, что доказательство L! = NP должно быть проще, чем доказательство P! = NP : Отдельный NP от логарифмического пространства. Я дал четыре подхода в обзоре диагонализации перед разделом 2001 года (Раздел 3), хотя ни один из них не удался. Должно быть намного проще, чем...
Класс сложности PPAD был изобретен Христосом Пападимитриу в его основополагающей статье 1994 года . Этот класс предназначен для охвата сложности задач поиска, когда существование решения гарантируется «аргументом четности в ориентированных графах»: если в ориентированном графе существует...
В 1978 году Адлеман показал, что BPP⊆P/polyBPP⊆P/poly\mathrm{BPP}\subseteq \mathrm{P/poly} : если булева функция fff из nnn переменных может быть вычислена с помощью вероятностной булевой схемы размера MMM , тогда fff может быть вычислена с помощью детерминированной булевой схемы размера многочлен...
Скажем, у нас есть свойство графа, которое можно проверить в недетерминированном полиномиальном времени, и доказательство в слабой формальной системе (скажем, RCA 0 ), что свойство является минорным. Можем ли мы что-нибудь сказать о силе формальной системы, которая может доказать, что данный...
Учитывая конечный (детерминированный или недетерминированный, я не думаю, что это имеет большое значение) автомат A и порог n , принимает ли A слово, содержащее не более n различных букв? (Под k разными буквами я подразумеваю, что aabaa имеет две разные буквы, a и b .) Я показал, что эта задача...
Рассмотрим следующую игру на ориентированном взвешенном графе гGG с чипом в некотором узле. Все узлы гGG отмечены буквой A или B. Есть два игрока Алиса и Боб. Цель Алисы (Боба) - сдвинуть фишку к узлу, обозначенному буквой A (B). Первоначально Алиса и Боб имеют мAmAm_A и мВmBm_B долларов...
Какие еще языки проблем, отличные от изоморфизма графов, есть в ? Можете ли вы дать некоторые ссылки?Nп∩ c o A MNP∩coAMNP\cap coAM Обновление: Я забыл упомянуть , что я заинтересован в языках , не известно, в .c o...
Пусть { 0 , . , , , П - 1 } и ∘ : S × S → S . Я хочу вычислить сложность коммуникации, решая, является ли ∘ ассоциативным.Sзнак равноS=S=0 , . , , , n - 10,...,n−10,...,n-1∘ : S× S→ S∘:S×S→S\circ : S \times S \rightarrow S∘∘\circ Модель следующая. задается в виде матрицы М . Алиса (соответственно...
Бумага Лаури Хелла и Хосе Мария Turull-Torres, Вычисление запросов с помощью логики высшего порядка , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 предлагает логику VO, логику переменного порядка. Это позволяет определять количество заказов по переменным. VO довольно мощный и может...
Эквивалентная формулировка теоремы PCP является: Для Макса 3-SAT это -трудного различать выполнимые формулы и формулы , где не более группу фракций из пунктов являются выполнимы (для некоторого ).r r < 1NпNPNPрrrг < 1r<1r\lt 1 Существует ли какая-либо известная теорема о дихотомии, которая...
Следующий вопрос использует идеи из криптографии, примененные к теории сложности. Тем не менее, это чисто теоретический вопрос сложности, и для его ответа не требуется никаких криптовалют. Я намеренно пишу этот вопрос очень неформально. В отсутствие подробностей, это, возможно, указано немного...
Автор: http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf. Если является PSPACE-полный язык, Р = N P A .AAAпA= NпAPA=NPAP^{A}=NP^{A} Если является детерминированным оракулом полиномиального времени, P B ≠ N P B (при условии, что P ≠ N P ).ВBBпВ≠ NпВPB≠NPBP^{B}\ne NP^{B}п≠ NпP≠NPP\ne NP -...
Опять проблема с разделением ребер, сложность которой мне интересна, мотивированная предыдущим моим вопросом . Вход: кубический графG = ( V, E)G=(V,E)G=(V,E) Вопрос: есть ли разбиение на , так что подграф, индуцированный каждым является либо когтем (то есть , часто называемым звездой), либо путём (...
Результат Бейкера-Гилла-Соловая показал, что вопрос о P = NP не релятивизируется в том смысле, что никакое релятивизирующее доказательство (нечувствительное к присутствию оракула) не может решить вопрос о P = NP. Мой вопрос: есть ли аналогичный результат для вопроса "Существует ли проблема полной...
Что меня особенно интересует, так это наличие интересного условия о проценте назначений, которые удовлетворяют формуле 3SAT, чтобы гарантировать, что такие проблемы поддаются решению. Предположим, например, класс задач 3SAT, что из возможных назначений удовлетворяет булевой формуле; мы можем...
Работая над несколько не связанным проектом для Suresh, я недавно натолкнулся на некоторую работу, проделанную Пейджем и Оппером о пользовательских системах, и в части их работы кратко обсуждались проблемы, которые невозможно проверить за полиномиальное время. Мне не удалось найти много информации...
Подсчитав аргументы, можно показать, что существуют многочлены степени n от 1 переменной (т. Что-то вроде которые имеют сложность схемы n. Также можно показать, что для многочлена типа требуется как минимум умножений (это нужно просто для получения достаточно высокой степени). Существуют ли явные...
Пусть G связный граф. Какова сложность подсчета всех связанных подграфов, если G имеет следующие типы? G является общим. Г плоская. G является двудольным. Я не забочусь о каких-либо структурах или ..., просто нужно сосчитать все связанные подграфы! Меня также интересует сложность подсчета всех...