Как я могу показать, что проблема Gap-P находится за пределами #P

14

В теории комбинаторного представления и алгебраической геометрии существует ряд проблем, для которых не существует положительной формулы. Есть несколько примеров, о которых я думаю, но позвольте мне взять в качестве примера вычисление коэффициентов Кронекера . Обычно понятие «положительная формула» не совсем точно определено в комбинаторике, но оно примерно означает «описание, поскольку количество элементов кажется достаточно явным множеством». Недавно я разговаривал с Ионой Бласиаком, и он убедил меня, что правильное определение «позитивной формулы» - это #P . Я собираюсь предположить, что на этом сайте мне не нужно определять #P.

Бюргиссер и Икенмейер показывают, что коэффициенты Кронекера жесткие #P. (Они также всегда положительны, потому что они являются тензорными кратностями произведений.) Но я вполне уверен, что никто не знает способ их вычисления, который даже переводит их в #P.

Итак, предположим, что я должен был попытаться доказать, что коэффициенты Кронекера не в #P. Я предполагаю, что то, что я хотел бы сделать, это предположить некоторую теоретическую гипотезу сложности, а затем свести произведение Кронекера к некоторой другой задаче, которая, как известно, является полной для класса, большего чем #P.

Какую гипотезу я могу предположить, и какую проблему я могу попытаться устранить?


ДОБАВЛЕНО: Как было указано в комментариях, Бюргиссер и Икенмейер показывают, что коэффициенты Кронекера находятся в Gap-P, что довольно близко к #P. Таким образом, звучит так, что я должен задать следующие вопросы: (1) Каковы некоторые проблемы, связанные с Gap-P-полнотой, которые я мог бы правдоподобно уменьшить, и (2) каковы перспективы показать, что Gap-P не является #P? Я думаю, (2) следует разбить на две части (2а) эксперты считают, что эти классы разные? и (2b) есть ли вероятные стратегии, чтобы доказать это?

Я надеюсь, что это большое редактирование вопроса не осуждается.

Дэвид Э Шпейер
источник
5
Добро пожаловать в историю! (Я добавил сложность подсчета и нижние оценки к вопросу).
Каве
3
@Kaveh Bürgisser и Ikenmeyer показывают, что вычисление коэффициентов Кронекера происходит в GapP. Дэвид, коэффициенты Кронекера всегда неотрицательные целые числа?
Тайсон Уильямс
2
Да. Они являются мультипликаторами тензорных произведений, поэтому они всегда неотрицательны.
Дэвид Э Шпейер
1
У вас проблема с GapP, и вы хотите доказать, что она находится за пределами #P. Очевидный подход состоит в том, чтобы показать, что проблема является GapP-полной при функциональной (левиновой) сводимости, что будет означать, что проблема находится вне #P, предполагая # P ≠ GapP.
Tsuyoshi Ito
1
То, что я написал в моем предыдущем комментарии, неверно, потому что любая проблема в GapP функционально сводится к #P (если я не ошибаюсь на этот раз). Другими словами, разница между #P и GapP слишком деликатна, чтобы справляться с ней, используя функциональную сводимость.
Tsuyoshi Ito

Ответы:

12

Я бы посоветовал взглянуть на свойства функций #P, которые отличаются от функций Gap-P. Например, определение, является ли функция #P нулем, находится в co-NP. Если бы вы могли показать, что коэффициенты Кронекера равны нулю - это трудно, то у вас будет «коэффициенты Кронекера в #P означают UP в со-NP», маловероятный вывод.

Лэнс Фортноу
источник
3

GapP - это как раз замыкание #P при вычитании. С другой стороны, #P не закрывается при вычитании, если UP = PP. Я считаю, что отвечает на ваши вопросы.

Тайфун Пей
источник
4
Если вы проголосовали за него, хотя бы объясните, почему это неправильно .. Спасибо
Tayfun Pay
3
Я согласен. Насколько я могу судить, ответ дает два правильных утверждения и отвечает на исходный вопрос (хотя мои поиски показали, что UP = PH - желаемое условное условие?)
Суреш Венкат
2
@Suresh: Как этот пост отвечает на оригинальный вопрос? Вопрос не в GapP-полной проблеме.
Цуёси Ито
3
Часть (2) в обновлении спрашивает: «Каковы перспективы GapP, не равного #P». этот ответ указывает на то, что, если не произойдет коллапс, #P не будет закрыт при вычитании, и поэтому нет смысла даже говорить о равенстве.
Суреш Венкат
1
@Suresh: это бумага. М.Огивара и Л. Хемачандра. «Теория сложности для возможных свойств замыкания». Журнал компьютерных и системных наук Том 46 Страницы 295-325. 1993.
Tayfun Pay
0

Вопрос вычисления символов неприводимых представлений симметрической группы может быть естественным кандидатом.

Я думаю, Чарльз Хеплер показывает, что Gap-P завершен, но я не уверен: ссылку на его магистерскую диссертацию см. По адресу https://dspace.ucalgary.ca/handle/1880/45530?mode=full.

Hari
источник