В теории комбинаторного представления и алгебраической геометрии существует ряд проблем, для которых не существует положительной формулы. Есть несколько примеров, о которых я думаю, но позвольте мне взять в качестве примера вычисление коэффициентов Кронекера . Обычно понятие «положительная формула» не совсем точно определено в комбинаторике, но оно примерно означает «описание, поскольку количество элементов кажется достаточно явным множеством». Недавно я разговаривал с Ионой Бласиаком, и он убедил меня, что правильное определение «позитивной формулы» - это #P . Я собираюсь предположить, что на этом сайте мне не нужно определять #P.
Бюргиссер и Икенмейер показывают, что коэффициенты Кронекера жесткие #P. (Они также всегда положительны, потому что они являются тензорными кратностями произведений.) Но я вполне уверен, что никто не знает способ их вычисления, который даже переводит их в #P.
Итак, предположим, что я должен был попытаться доказать, что коэффициенты Кронекера не в #P. Я предполагаю, что то, что я хотел бы сделать, это предположить некоторую теоретическую гипотезу сложности, а затем свести произведение Кронекера к некоторой другой задаче, которая, как известно, является полной для класса, большего чем #P.
Какую гипотезу я могу предположить, и какую проблему я могу попытаться устранить?
ДОБАВЛЕНО: Как было указано в комментариях, Бюргиссер и Икенмейер показывают, что коэффициенты Кронекера находятся в Gap-P, что довольно близко к #P. Таким образом, звучит так, что я должен задать следующие вопросы: (1) Каковы некоторые проблемы, связанные с Gap-P-полнотой, которые я мог бы правдоподобно уменьшить, и (2) каковы перспективы показать, что Gap-P не является #P? Я думаю, (2) следует разбить на две части (2а) эксперты считают, что эти классы разные? и (2b) есть ли вероятные стратегии, чтобы доказать это?
Я надеюсь, что это большое редактирование вопроса не осуждается.
источник
Ответы:
Я бы посоветовал взглянуть на свойства функций #P, которые отличаются от функций Gap-P. Например, определение, является ли функция #P нулем, находится в co-NP. Если бы вы могли показать, что коэффициенты Кронекера равны нулю - это трудно, то у вас будет «коэффициенты Кронекера в #P означают UP в со-NP», маловероятный вывод.
источник
GapP - это как раз замыкание #P при вычитании. С другой стороны, #P не закрывается при вычитании, если UP = PP. Я считаю, что отвечает на ваши вопросы.
источник
Вопрос вычисления символов неприводимых представлений симметрической группы может быть естественным кандидатом.
Я думаю, Чарльз Хеплер показывает, что Gap-P завершен, но я не уверен: ссылку на его магистерскую диссертацию см. По адресу https://dspace.ucalgary.ca/handle/1880/45530?mode=full.
источник