Насколько сложно точное моделирование алгоритмов и связанные с ними операции над классами сложности

17

задира

Поскольку проблема длинная, здесь есть особый случай, который отражает ее суть.

Проблема: Пусть A - детриминистический алгоритм для 3-SAT. Является ли проблема полного моделирования алгоритма A (на каждом экземпляре задачи). P-Space сложно?

(Точнее, есть ли основания полагать, что эта задача сложная в P-Space, что-то в этом направлении следует из стандартных гипотез CC, и есть ли надежда доказать, что эта задача X-трудная для некоторого класса сложности X, который предполагается быть строго выше НП.)

Вопросы, связанные с данной : являются-проблемы-полные-проблемы-изначально-менее-поддающиеся решению-чем-np-полные-проблемы ;

ОБНОВЛЕННОЕ ОБНОВЛЕНИЕ : Существуют различные интерпретации «Полностью имитировать А». И могут быть разные интересные ответы в зависимости от интерпретации. (Также Райан Уильямс предложил интерпретацию для моделирования недетерминированного алгоритма.) Для определенного способа связать решение проблемы с вычислительной задачей «Полностью смоделировать A», Джо Фитцсимонс нашел алгоритм A, для которого эта связанная проблема решения все еще находится в NP. , Если «полностью имитировать» относится к возможности вывести весь регистр компьютера на данном шаге то для алгоритма Джо кажется, что P N P - это то, что нужно. Для этой версии (я думаю, но не уверен) ответ Райана набрасывает P N PiPNPPNPТвердость аргумент. Джо отметил, что если от вас требуется предоставить все регистры (что больше не является проблемой для решения), не удивительно, что вам нужно активизировать классы сложности.

Во всяком случае, если мы требуем , чтобы вывести состояние регистров на заданном этапе тогда ответы Руана и Джо предлагает (но опять же , я не уверен в этом) , что N P + , по существу , P N P . Мы можем spaculate , что с помощью этой интерпретации операция толкает вверх на одну ступень выше в полиномиальное hiearachy, и что Р Н + = Р Н .iNP+PNPPH+=PH

В любом случае с помощью этих интерпретаций ответ на мой вопрос-тизер НЕТ .

Я имел в виду более радикальную интерпретацию «полностью имитирующего алгоритм А». (Но, возможно, интерпретация Джо и Райана более интересна.) Моя интерпретация «полностью имитирующего алгоритма A» заключается в том, что вы выходите из состояния регистров на каждом шаге . В частности, если алгоритм не является полиномиальным, ваш вывод также не является полиномиальным. При такой резкой интерпретации я задавался вопросом, должны ли мы верить, что для каждого алгоритма A C A является сложным P-SPACE, и что мы можем доказать.iCA

Мотивация:

Этот вопрос был мотивирован лекцией Пола Голдберга ( слайды , видео , статья ), в которой описывается статья с Пападимитриу и Савани. Они показали, что это P-пространство завершено, чтобы найти любые равновесия, которые вычисляются по алгоритму Лемке-Хоусона. Задача найти некоторую точку равновесия является только PPAD-полной. Этот разрыв весьма удивителен, и аналогичные результаты уже описаны в известной статье Пападимитриу: Сложность аргумента четности и другие неэффективные доказательства существования (1991) . (Известно, что PPAD-полные проблемы не могут быть даже NP-сложными (если не произойдут ужасные вещи, так что в мире сложности это намного ниже, чем в P-пространстве).

О чем идет речь

Мой вопрос о похожих пробелах для более старых и более классических задач вычислительной сложности. (Может быть, это уже знакомо.)

Учитывая вычислительную проблему, мы можем различить три проблемы

а) Решить проблему алгоритмически

б) Достичь того же решения, что и конкретный алгоритм А

в) Имитация всего алгоритма А

Конечно, в), по крайней мере, так же сложно, как б), что, по крайней мере, так же сложно, как а). Упомянутые выше результаты показывают разрыв между вычислительной сложностью задач а) и б) для задачи вычисления равновесий. Мы хотели бы понять ситуацию (и главным образом разрыв между a) и c)) для других вычислительных задач.

Вопрос:

Основная форма вопроса с примером

Мы начнем с вычислительной задачи, проблема X

Примером может быть

Проблема X: Решите экземпляр SAT с n переменными

мы также указываем

A: алгоритм, который выполняет задачу X

и мы ставим новую проблему

Задача Y: точно смоделировать алгоритм A

и нас интересует вычислительная сложность задачи Y. Мы хотим понять класс таких задач Y для всех алгоритмов A, которые решают исходную проблему X. Особенно мы хотим знать, насколько простой может быть проблема Y (или насколько сложной она должна быть) быть) если нам позволено выбрать алгоритм A по желанию.

Предлагаемая операция на классах сложности

Начните с класса сложности который описывается некоторой вычислительной задачей. Учитывая алгоритм А для выполнения каждого экземпляра этой вычислительной задачи, рассмотрит новую сложность класса C A , который описан в вычислительной задаче укомплектовать моделирования A . Тогда мы можем (надеюсь) определить «идеал» классов сложностиCCAA

для всех алгоритмов A}.C+={CA:

Если мы позволим , чтобы описать то , что цифровой компьютер может сделать в полиномиальное время (так что я не хочу , чтобы ограничить внимание , например , к проблемам принятия решений) , то P + является идеальным натянутым P самого.PP+P

Наконец, мои вопросы

Мои вопросы:

1) Является ли определение смыслом (в широком смысле слова смысл). Это хорошо известно или так же, как (или похоже) на какую-то известную вещь. (Моя формулировка была неформальной, и, в частности, когда мы переходим от конкретных проблем, таких как SAT, к классу сложности, таким как NP, нам приходится беспокоиться о различных вещах, которыми я пренебрег.)

Следующие два вопроса предполагают, что определение может иметь смысл или быть спасенным, чтобы иметь смысл.

2) Предположим, мы снабжаем себя всеми стандартными предположениями относительно вычислительной полноты. Можем ли мы сказать, что должен быть для некоторых знакомых классов сложности. (Например, C = N P , C = P-пространство, ..)? EDIT: Несколько человек указали, что P S P C E + = P S P C E . Так что> мы можем спросить вместо этого, что такое ( P N P ) + ? такое P H + = P H ?C+C=NPCPSPACE+=PSPACE(PNP)+PH+=PH

Можем ли мы угадать, что такое классы так что C + - это идеал, натянутый на C ?CC+C

Таким образом, вопрос, насколько легко вычислительная задача моделирования алгоритма A для 3-SAT (когда мы можем выбрать алгоритм, чтобы сделать его максимально простым), представляет собой интересный частный случай.

3) Есть ли надежда доказать что-то об этой операции?

Конечно, если вы докажете, что все классы сложности в являются P-пространственными, это покажет, что P = N P подразумевает P = P S P A C E , что (я думаю) будет огромным и весьма неожиданным результатом. , Но если показать , что все классы сложности в N P + трудно Somthing сказать третьего уровня полинома Hieararchy (например , Δ P 3 ) , это предполагало лишь то , что мы уже знаем, вещи , которые вытекают из того факта , что P = N P вызывает разрушение PH.NP+P=NPP=PSPACENP+Δ3PP=NP

Гил Калай
источник
3
Интересный вопрос! Но: «Конечно, а), по крайней мере, так же трудно, как б), что, по крайней мере, так же трудно, как с)». Разве порядок не должен быть наоборот?
Барт Янсен
2
Можно ли включить ссылку или, возможно, краткое описание того, что означает «моделировать весь алгоритм А». Мол, в чем разница между «симуляцией» и «бегом» в этом случае? Можно ли смоделировать алгоритм быстрее, чем его время выполнения?
Артем Казнатчеев
1
Уважаемый Артем, под моделированием алгоритма в конкретном случае я имею в виду описание всей эволюции алгоритма. (Так что, возможно, это похоже на «запуск» алгоритма.) Вы не можете моделировать алгоритм быстрее, чем его время выполнения. Это не стандартное понятие (насколько мне известно), поэтому я не могу давать ссылки или ссылки (но надеюсь получить ссылку и ссылки.). Моделирование алгоритма отличается от просто вычислительной задачи «дать тот же результат, что и алгоритм А», которая связана с мотивацией и задачей б), описанной в вопросе.
Гил Калай
2
Уважаемый Gil, я не в состоянии понять , почему мы не можем моделировать алгоритм с ресурсами одного и того же порядка, что и A использований. Если некоторые ресурсы не более ограничены , мы можем просто имитировать то , что делает. Позвольте мне увидеть , если я понимаю мотивацию часть правильно: У нас есть проблема Q в классе C . Представляет собой алгоритм , возможно , за пределами C решения Q . Несмотря на то, нахождение в решение для Q может быть сделано в C , находя одну из тех решений , которые А находки могут иметь сложности за пределами CAAAQCACQQCAC, Правильно ли я понимаю мотивационную часть поста?
Каве
2
Да, да, мы предполагаем, что алгоритм А является детерминированным! У меня нет четкой интуиции, почему мы должны ожидать, что моделирование каждого детерминированного алгоритма для 3-SAT является сложным в P-пространстве. Это вопрос! Я хотел посмотреть, что думают эксперты.
Гил Калай

Ответы:

12

Задача: Пусть A - детерминированный алгоритм для 3-SAT. Сложна ли проблема полного моделирования алгоритма A (в каждом случае задачи) P-Space?

Я не понимаю формулировку этой проблемы. Но я думаю, что есть естественный способ формализовать ваш более общий вопрос, который может пролить немного света на него. Может быть, я полностью упускаю вашу точку зрения, но, надеюсь, вы все равно найдете здесь что-нибудь интересное для чтения.

1) Является ли определение смыслом (в широком смысле слова смысл). Это хорошо известно или так же, как (или похоже) на какую-то известную вещь. (Моя формулировка была неформальной, и, в частности, когда мы переходим от конкретных проблем, таких как SAT, к классу сложности, таким как NP, нам приходится беспокоиться о различных вещах, которыми я пренебрег.)

Один из способов точноY понять задачу симуляции алгоритма Y заключается в следующем. Давайте сделаем так, чтобы модель была ленточной машиной Тьюринга для простоты; то, что я скажу, может применяться к любой типичной вычислительной модели.

Для каждого алгоритма и входных данных x мы можем определить его историю вычислений H Y ( x , i , j ) : заданные целые числа iYx HY(x,i,j)i и которые варьируются от 0 до времени выполнения Y , H Y ( x , i , j ) равно содержимое j- й ячейки ленты машины Тьюринга Y на входе x на временном шаге i . (И если головка ленты читает Jj0YHY(x,i,j)jYxijЭта ячейка на м шаге также включает это вместе с состоянием машины.) Конечно, в теории сложности все время возникают истории вычислений.i

Теперь можно утверждать, что любой алгоритм, который может решить язык

CY={(x,i,j,σ) | HY(x,i,j)=σ}

(или имитировать функцию на всех входах) решает задачу точно моделировать алгоритм Y , поскольку он имеет возможность печатать каждую небольшую часть всех возможных вычислений алгоритма Y . Конечно, учитывая оракул для C Y можно было сделать шаг за шагом моделирования Y .HYYYCYY

2) Предположим, мы снабжаем себя всеми стандартными гипотезами, касающимися сложности вычислений. Можем ли мы сказать, что C + должен быть для некоторых знакомых классов сложности. (Например, C = NP, C = P-пространство, ..)? Можем ли мы угадать, каковы классы сложности C, так что C + является идеалом, натянутым на C?

Это все еще интересный вопрос, в соответствии с вышеуказанным предложением. Для детерминированных временных классов ничего не меняется. - это просто P : мы можем решить, что C Y H Y больше не является четко определенным. Однако мы все еще хотим напечатать некоторую историю вычислений, поэтому наше «точное моделирование» должно было бы выделить конкретную недетерминированную историю вычислений и затем вывести ее значения. Для N PP+PCY в Polytime для каждого алгоритма Polytime. Аналогично . Кроме того, Р С Р С Е + еще Р С Р С Е . Для недетерминированных классов временной сложности ситуация становится более интересной. В этом случае алгоритм Y может иметь несколько историй вычислений, поэтомуEXP+=EXPPSPACE+PSPACEYHYNP алгоритма можно сказать, что C YP N P : мы можем использовать оракул N P для бинарного поиска «первой» принимающей истории вычислений (в лексном порядке), затем, как только мы ее получим, выведите соответствующие биты. Для N E X P алгоритма Y можно сказать, что C YYCYPNPNPNEXPY , по аналогичным причинам.CYEXPNP

Можем ли мы поставить в меньший класс? Я не знаю. Обратите внимание, что мы не можем просто переопределитьNP+

{ ( x , i , j , σ ) | существует H Y такое, что H Y ( x , i , j ) = σ }CY=(x,i,j,σ) | HYHY(x,i,j)=σ

попытаться поместить в N P , потому что нам нужно, чтобы строка истории была одинаковой для всех четырехкратных чисел, включающих x , для «точного моделирования алгоритма Y ».CYNPxY

В любом случае, эта проблема невозможности «напечатать свидетеля» для вычисления без перехода к E X P N P действительно возникает в некоторых ситуациях, таких как сложность схемы. ЕслиNEXPEXPNP имеет схемы полиномиального размера, то также имеет место случай, когда C YP / p o l y для каждого недетерминированного 2 n k времени Y ? Импальяццо, Кабанец и ВигдерсонNEXPCYP/poly2nkYна этот вопрос утвердительно ответили в 2001 году. Их доказательство чрезвычайно интересно, поскольку оно вызывает инструменты дерандомизации и диагонализации (почему для такого результата необходима дерандомизация?), и она оказывается очень полезной теоремой для доказательства нижних границ схем для функции.NEXP

Есть ли надежда доказать что-то об этой операции?

Может быть ... это зависит от того, довольны ли вы приведенной выше формализацией своего вопроса. Для детерминированного алгоритма 3-SAT , я думаю, что приведенное выше точное моделирование задачи Y будет P N P ( 1 )YYPNP(1) -Жесткий, где полиномиальное время с одним запросом к N P . (Раздражающий синтаксис StackExchange требует, чтобы я написал (1) вместо альтернативы. Ранее я говорил, что C Y должен быть P N P -hard, но я не уверен в деталях: вы можете увидеть, как обобщить приведенное ниже.)PNP(1)NPCYPNP

Приведет полиномиальное по уменьшению многих один из каждого к C Y . Учитывая такую L , пусть MLPNP(1)CYLM будет машиной, распознающей которая выполняет один запрос N P. WLOG, этот запрос является формулой SAT. Также WLOG, SAT-запрос может быть «отложен» до самого последнего шага вычисления, в следующем смысле: существует алгоритм A ( x ) полиномиального времени, который печатает формулу F и бит b , такой что для всех x ,LNPA(x)Fbx

принимает, если A ( x ) = ( F , b ) так , что ( S A T ( F ) XOR b ) = 1.M(x)A(x)=(F,b)SAT(F)b

( может отклонить, если F удовлетворительно, или он может принять; бит b захватывает это.)MFb

Для простоты, скажем, когда заканчивает вычисления, он перемещает головку ленты в ячейку 1, пишет «принять» или «отклонить» в этой ячейке и зацикливается навсегда. Тогда, спрашивая, если ( F , T , 1 , a c c e p t ) C Y для достаточно большойY(F,T,1,accept)CY , скажет нам, если F принято. (В общем, нам просто нужно, чтобы было эффективно вычислить экземпляр y в C Y, который скажет нам.) Обратите внимание, что это уже показывает, что C Y является одновременно и N P -hard, иTFyCYCYNP -hard; последнее вернотак как ( Р , Т , 1 , т е J е с т ) C Y тогдатолько тогда F являетсяневыполнима.coNP(F,T,1,reject)CYF

Окончательное сокращение от до C Y : дано x , прогон A ( x ), получая ( F , b ) . Если b = 0, тогда выведите ( F , T , 1 , a c c eLCYxA(x)(F,b)b=0 , иначе, если b = 1, выводится ( F , T , 1 , r e j e c t(F,T,1,accept)b=1 .(F,T,1,reject)

Для каждого мы производим (за полиномиальное время) а у такой , что М ( х ) принимает тогда и только тогда у C Y .xyM(x)yCY

(Спасибо Джо за требование прояснить эту часть.)

Но я не вижу (например), как получить -твердость. Уменьшить Σ 2Σ2PΣ2 -SAT к проблеме, может показаться, что вам нужно написать экземпляр 3-CNF SAT который имитирует ваш детерминистический алгоритм Y внутри него (где Y решает тавтологии в различных подзадачах). Но так как Y не имеет ограничения по времени, этот 3-CNF x может быть огромным, поэтому вы не обязательно получите сокращение за полиномиальное время. Если я что-то упустил.xYYYx

Райан Уильямс
источник
Райан, большое спасибо за ваш ответ. Мне интересно, как сложно моделировать детерминированный алгоритм Y для 3-SAT. И вопрос в том, неважно, что Y, это P-пространство трудно. (Ваше понимание симуляции недетерминированных алгоритмов также интересно и, возможно, является правильным вопросом, но я рассмотрел только симуляцию детерминированных алгоритмов.)
Гил Калай
Да, я думал, что последний абзац моего ответа будет посвящен этой части.
Райан Уильямс
Понимаю. Да, действительно так и есть. Я также подозревал, что это может быть доказуемо -hard, что интересно (но я не уверен, что понимаю ваше доказательство). Ожидаете ли вы, что P N P является правильным ответом? Я также подозревал, что доказать что-то за пределами P N P будет сложно. Возвращаясь к тому, что мы можем доказать, к чему мы должны верить, Райан, как ты думаешь, какой ответ? PNPPNPPNP
Гил Калай
Ну, сложность будет отличаться в зависимости от алгоритма Y . Некоторые C Y могут быть очень сложными, а другие могут быть намного проще. Но я думаю, что для каждого алгоритма Y вы, вероятно, не добьетесь большего успеха, чем сказать « C Y - P N P -hard». (Я не думаю, что для каждого Y вы можете получить Σ 2 PCYYCYYCYPNPYΣ2P -твердость по той интуитивной причине, которую я привел выше.)
Райан Уильямс
Райан, вы говорите , что «существует многочлен сокращение от полного языка ... на C Y », но ваше сокращение , кажется, использует несколько экземпляров C Y . Конечно, вместо этого это показывает, что существует полиномиальная редукция из неполной задачи P N P к P C Y ? PNPCYCYPNPPCY
Джо Фицсимонс
7

Я изначально разместил неправильный ответ, так что, надеюсь, это улучшение.

Я собираюсь начать с рассмотрения примера 3SAT. В своем комментарии к ответу Райана вы говорите

Мне интересно, как сложно моделировать детерминированный алгоритм Y для 3-SAT. И вопрос в том, неважно, что Y, это P-пространство трудно.

Ответ заключается в том, что он не является PSPACE-сложным по крайней мере для некоторого Y, предполагая, что NP PSPACE, но что существуют другие алгоритмы, для которых он PSPACE-трудный. Показ последнего является тривиальным: мы просто создаем алгоритм, который интерпретирует битовую строку, представляющую формулу 3SAT, вместо этого как проблему TQBF, которую он затем решает перед решением экземпляра 3SAT. Очевидно, что в этом случае нет ничего особенного в TQBF, поэтому алгоритм может быть произвольно затруднен для моделирования. Поэтому мы должны заботиться только о нижних границах моделирования любого алгоритма для данной задачи, а не о конкретном алгоритме.

Имея это в виду, мы строим следующий алгоритм для решения 3SAT:

Возьмите регистр из битов (первоначально все они установлены в 0), чтобы содержать пробное решение, вместе с регистром, содержащим экземпляр 3SAT, регистр счетчика размера log 2 ( c + 1 )n изначально установленный в 1 и два флага биты (назовите их как флаг сбоя и флаг принятия). Здесь c - количество предложений. Затем алгоритм работает следующим образом:log2(c+1)c

  • Если значение счетчика предложений меньше или равно c , а пробное решение не равно 111 ...... 1 , проверьте, выполнено ли условие k . Если нет, установите бит сбоя. Увеличьте счетчик.kc111......1k
  • Если значение счетчика предложений меньше или равно c , а пробное решение равно 111 ...... 1 , проверьте, выполнено ли условие k . Если это не так, установите флаг сбоя. Увеличьте счетчик.kc111......1k
  • Если превышает c , а пробное решение не 111 ...... 1 , проверьте, установлен ли флаг сбоя. Если это так, то увеличьте пробное решение, сбросьте счетчик k до 1 и снимите флажок сбоя. Если флаг сбоя не был установлен, установите флаг принятия, установите счетчик предложений k на ноль, установите пробное решение на ноль и остановите.kc111......1kk
  • Если превышает c , а пробное решение равно 111 ...... 1 , проверьте, установлен ли флаг сбоя. Если флаг сбоя не был установлен, установите флаг принятия. Установите счетчик предложений k на ноль, установите пробное решение на ноль и остановите.kc111......1k

Когда алгоритм останавливается, состояние флага принятия сообщает вам, может ли быть выполнена формула 3SAT.

Теперь, если я хочу , чтобы вычислить состояние алгоритма во время у меня есть алгоритм вычисления это за полиномиальное время с помощью одного вызова к оракулу НП следующим образом :i

Обратите внимание, что для любого , предполагая, что бит принятия еще не установлен, состояние регистров может быть вычислено за полиномиальное время, поскольку значение k и регистр t пробного решения являются просто функциями iikti . Определить, установлен ли флаг сбоя, можно за полиномиальное время, просто проверяя, удовлетворяет ли текущее состояние регистра пробного решения всем условиям, меньшим или равным текущему значению . Если и только если это не так, устанавливается флаг сбоя. Флаг принятия установлен в ноль.k

Точно так же, если бит принятия уже установлен, состояние регистров может быть эффективно вычислено, поскольку все равно нулю, кроме бита принятия, который установлен.

Таким образом, единственная сложность заключается в определении, установлен ли бит принятия. Это эквивалентно определению, имеет ли данный экземпляр 3SAT решение меньше, чем . Если это так, то бит принятия обязательно должен быть установлен, а если нет, то бит принятия обязательно должен быть равен нулю. Очевидно, что эта проблема сама по себе является NP-полной.t

Таким образом, состояние системы на шаге можно определить за полиномиальное время с помощью одного запроса к оракулу NP.i

Важное обновление: изначально я неправильно истолковал формулировку Райана точного моделирования как проблему принятия решения, и поэтому мое утверждение о том, что версия принятия решения была в NP, было неверным. Учитывая проблему решения, отвечает ли бит на шаге i на входе x, как сформулировано в Райансе, существует 3 варианта:jix

  1. Этот бит постоянен независимо от того, является ли выполнимым. Поскольку в настоящее время для системы существует только два возможных состояния (оба из которых могут быть вычислены в P), определяется, имеет ли это место, и если да, то равно ли значение σ значению P.Fσ
  2. Бит равен если F S A T , и неравен в противном случае. Эта проблема явно в NP, так как удовлетворительное назначение F выступает в качестве свидетеля.σFSATF
  3. Бит равен если F U N S A T, и в этом случае проблема в coNP.σFUNSAT

Ясно , что решить , какой один из этих трех является случай может быть сделано в полиномиальное время, просто путем сравнения значения , что бит принимает , если и , если F U N S A T . Таким образом, точная задача моделирования находится в NP coNP. Таким образом, поскольку нижняя граница Райана и моя верхняя граница совпадают, предполагая, что оба верны, я думаю, что у нас есть ответ: C Y = N P c o NFSATFUNSAT .CY=NPcoNP

Обратите внимание, что в этом случае нет ничего особенного в 3SAT, и то же самое можно сделать для любой проблемы в NP. Кроме того, та же самая хитрость может использоваться для любого недетерминированного класса сложности, а не только для NP, который кажется трудным для моделирования. Для детерминированных классов вы можете просто запустить лучший алгоритм и остановиться на шаге . Таким образом, с учетом этого полная имитация хотя бы некоторого детерминированного алгоритма для задачи является такой же сложной, как и решение самой проблемы.i

Джо Фитцсимонс
источник
1
Разве вы не можете использовать ту же технику, чтобы показать, что б) Достижение того же решения, что и алгоритм А , уже сложнее PSPACE? Пусть алгоритм выберет одно из двух возможных решений в зависимости от решения сложной задачи PSPACE, закодированной во вход.
Питер Шор
1
@Peter: Конечно, вы можете сделать это произвольно сложно, но я подумал, что интересным вопросом была верхняя граница, минимизированная по A, которая превращает наш в NP.
Джо Фицсимонс
3

Очень интересная мысль! Вот расширенный комментарий, который был слишком длинным, чтобы публиковать его как таковой:

Что касается определения в (1) как такового , то есть:

CCAAC+={CA:A}

C+MML(M)=?L(M) в общем случае неразрешимо путем сокращения из проблемы останова.

MMMMMt(n)MO(t(n))M

NPPSPACENP

PSPACE-completeness result, I believe the "gap" you're witnessing between PPAD-completeness and PSPACE-hardness is due to the distinction between finding any NE (in the sense of END OF LINE) and finding a unique NE given a specific, initial configuration (in the sense of OTHER END OF LINE).

Daniel Apon
источник
Dear Daniel, thanks for your answer. I am not sure I see why undecidability of membership in C^+ (Or even in C itself) is relevant to the question. The questions if :a) based on all our conjectures and beliefs regarding seperations of complexity classes is it the case that for every algorithm A for 3-SAT the computational task of simulating A (for every instance of 3-SAT) is Δ3P hard. b) Is it possible to actually proves such (or a similar) statement.(Maybe something very basic is wrong with my questions but I am not sure decidability is the issue.)
Gil Kalai
Gil, see if this speaks to your question at all: Fix some (arbitrary) algorithm A for 3-SAT. Consider a new algorithm B. Then we want to claim: B simulates A, in the sense of your (b) -- i.e. that B reaches the same solutions as A on all well-defined inputs. Since we can view algorithms as Turing machines, we can take the view that A accepts 3-SAT (by the supposition). To prove the claim, it appears to me that we then need to decide the question "Does B (viewed as a TM) accept 3-SAT as well?", which leads into undecidability issues.
Daniel Apon
I should point out that it's specifically the phrase "for all algorithms A" in the definition of C+ coupled with the notion of saying/guessing (or, presumably, computing or deciding) the elements of the set that gives me pause, if nothing else. Once we start considering computation on properties of arbitrary algorithms or languages or classes/sets of languages, the Halting problem often seems to creep in.
Daniel Apon
1
Dear Daniel, you wrote "Then we want to claim: B simulates A, in the sense of your (b) -- i.e. that B reaches the same solutions as A on all well-defined inputs." This is not what I mean by "B simulates A". For me B simulates A means that it describes precisely the entire "running" of algorithm A not just reach the same "solutions" (or output).
Gil Kalai
1
Regarding your second comment. It looks that we can find a reasonable restriction on the algorithms we consider or formulate the question a little differently: E.g. consider the statement "For every algorithm A to solve 3-SAT it is P-space hard to simulate A." I dont see how the halting problem creep in (more than in other questions in computational complexity).
Gil Kalai