Мы знаем, что если у вас есть машина PSPACE, она достаточно мощна, чтобы предоставить интерактивное доказательство любого уровня полиномиальной иерархии. (И если я правильно помню, все, что вам нужно, это #P.) Но предположим, что вы хотите предоставить интерактивное подтверждение членства на языке...
Я был (и до сих пор) действительно заинтересован в ответе на этот вопрос, потому что это интересный вариант сложности игр, который не был решен, поэтому я предложил вознаграждение. Я подумал, что исходный вопрос, скорее всего, слишком сложный, поэтому я опубликовал три связанных вопроса, которые...
Недавно Ватроус и др. Доказали, что QIP (3) = PSPACE - замечательный результат. Это был удивительный результат для меня, если не сказать больше, и это заставило меня задуматься ... Я задавался вопросом, что если бы Quantum Computers могла эффективно моделироваться классическими компьютерами. Может...
ООOC ø N P O ⊆ P S P C E O Oc o N PОP я PОсоNпО⊈япО{\sf coNP}^O \not\subseteq {\sf IP}^Oc o N PО⊆ Р С Р С ЕОсоNпО⊆пSпAСЕО{\sf coNP}^O \subseteq {\sf PSPACE}^OООO Тем не менее, я видел только несколько человек, которые дают «прямое» объяснение того, почему результат не релятивизируется, и обычный...
Хорошо известно, что набор языков, имеющих интерактивные системы доказательства с двумя доказательствами, в которых верификатор работает за полиномиальное время (MIP), является NEXP. Но известны ли пределы силы таких интерактивных доказательств, когда доказатели ограничены в силе? Например, что...
Вероятностная система доказательств обычно называется ограничением M A , где Артур может использовать только f ( n ) случайных битов и может проверять только g ( n ) битов подтверждающий сертификат, присланный Мерлином (см. http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).пСп[ ф( н ) ,...
Преамбула. Класс сложности AM - это те проблемы, которые могут быть решены с помощью двухсторонней интерактивной системы доказательств между прувером «Мерлин» и верификатором «Артур». Проблема, которая проверяет некоторое свойство объекта X, заключается в AM, если: Для случаев ДА для случайного...
Как я могу убедить Coq, что приведенная ниже рекурсивная функция завершается? Функция принимает два индуктивных аргумента. Интуитивно понятно, что рекурсия завершается, потому что любой аргумент разлагается. В частности, функция принимает два дерева в качестве входных данных. Inductive Tree := |...
Мой первый вопрос: известна ли интерактивная характеристика системы доказательств для всех классических классов сложности. Я бы назвал P, NP, PSPACE, EXP, NEXP, EXPSPACE рекурсивными и рекурсивно перечислимыми функциями классическими (среди прочих). В частности, известна ли интерактивная...
У Бейджи, Шора и Уотруса есть очень хорошая статья о силе квантовых интерактивных доказательств с короткими сообщениями. Они рассматривают три варианта «коротких сообщений», и один из них, который меня волнует, - это их второй вариант, в котором может быть отправлено любое количество сообщений, но...
Теорема Раза о параллельном предсказании является важным результатом в PCP, аппроксимации и т. Д. Теорема оформилась следующим образом. Игра , где S , T , A , B - конечные множества, π - распределение по S × T и предикат V : S × T × A × B → { 0 , 1 } . Определить значение игры v ( G ) = max...
Я читал в СП Иордане, Д. Госсе, «PJ Лява -полных задачи для stoquastic гамильтонианов и матриц МарковаQ MAQMAQMA » , что маловероятно , что .Q MA ⊆ A MQMA⊆AMQMA \subseteq AM Я был удивлен этим утверждением. Итак, каковы правильные отношения между и A M ?Q MAQMAQMAА...
Мерлин, имеющий неограниченные вычислительные ресурсы, хочет убедить Артура, что для с и Простое вычисление этой суммы (модульное возведение в степень и сложение) занимает время с умножением на основе БПФ. * Но Артур может выполнять только операций.m|∑p≤N, p primepkm|∑p≤N, p primepkm|\sum_{p\le N,\...
Полнота и обоснованность интерактивных систем доказательства неформально определяются как: Полнота: если утверждение верно, честный проверяющий может убедить честного проверяющего в этом факте whp . Обоснованность: если утверждение ложно, обманщик не может убедить честного проверяющего (в...
В последнее время я узнал об интерактивных доказательствах, и мне было интересно, было ли все это не более чем теоретическое любопытство, или у него было какое-то практическое применение. Я думал, что начну с примера, который пришёл мне в душ: В последнее время стало известно, что «Божье число» =...
Есть ли способ, которым проверяющий может убедить верификатора в том, что некоторое выражение HORN-SAT выполнимо? Конечно, это может показаться глупым, поскольку для HORN-SAT существуют линейные алгоритмы времени. С другой стороны, HORN-SAT является P-полным, что означает, что он не имеет...
В большинстве вероятностных систем доказательства (например, теорема PCP) вероятности ошибок обычно определяются на стороне ложноположительных значений, т. Е. Типичное определение может выглядеть так: если то верификатор всегда принимает, но в другом случае вероятность отклонения составляет не...
Определите, что вычислительная модель MPostBQP идентична PostBQP, за исключением того, что мы разрешаем полиномиально много измерений в кубитах перед последующим выбором и окончательным измерением. Можем ли мы привести какие-либо доказательства того, что MPostBQP более мощный, чем PostBQP?...
IP (2pfa) и AM (2pfa) - это классы языков, распознаваемые с ограниченной ошибкой в частных и открытых версиях монет, соответственно, интерактивных систем доказательства с верификаторами, которые являются вероятностными конечными автоматами с двусторонней входной головкой. Известны ли какие-либо...