Решает ли изменение одной записи уменьшение перманента матрицы в полиномиальной иерархии?

11

Рассмотрим следующую задачу: для заданной матрицы , индексов i , j { 1 , , n } и целого числа a . Заменить M [ я , J ] по и вызвать новую матрицу M . Является ли p e r ( M ) > pM{m,,0,,m}n×ni,j{1,,n}aM[i,j]aM^ ?per(M)>per(M^)

Это проблема в полиномиальной иерархии?

Т ....
источник
4
Это может быть решено двумя вызовами оракула #P ... Если бы он был в PH, то это означало бы, что PP также находится в PH ... Однако, если PP находится в PH, тогда PH рухнет. Поэтому я думаю, что вряд ли это в PH.
Тайфун Пей
1
@TayfunPay Я не думаю, что аргумент правильный. Эта проблема может быть решена с помощью двух вызовов #P, но это не может быть исключено так легко, что есть более простой алгоритм, который может показать, что он в PH. Вы должны показать, что это трудно для #P для этого, например, уменьшив значение Permanent.
Ян Йоханнсен
8
Если вы включите определение перманента и упростите полученное неравенство, ваша проблема сводится к тому, является ли перманент данной (n-1) -бай (n-1) матрицы строго положительным.
Гамов,
2
PER(M)>0MMM - 1 P E R ( M ) = - P E R ( M ) = - P E R ( M ) P E R ( M ) > 0 M ( i , j ) = ( 0 , 0 ) а = - 1MM1PER(M)=PER(M)=PER(M)PER(M)>0M(i,j)=(0,0)a=1возвращает истину.
holf
@holf: я думаю, что вы должны опубликовать это как ответ. Это довольно определенно отвечает на вопрос, и тогда вопрос больше не будет выглядеть как «без ответа».
Джошуа Грохов

Ответы:

10

Ваша проблема эквивалентна тестированию с учетом , если .MPER(M)>0

Доказательство : предположим, что вам дано и вы хотите решить, будет ли . Построим следующим образом : Это Легко видеть, что . Теперь определим как где мы заменяем запись на . Из мультилинейности следует, что . Таким образом, тогда и только тогда, когдаMPER(M)>0M

[1000M0]
PER(M)=PER(M)M^M(0,0)M1PER(M)=PER(M)=PER(M^)PER(M)>0PER(M)>PER(M^)

Теперь предположим, что вам даны , и и определите как в вашем вопросе, то есть изменивM(i,j)М М [ я , J ]aM^M[i,j]a

PER(M)>PER(M^) iffσk=1nM[k,σ(k)]>σk=1nM^[k,σ(k)] iffσ,σ(i)=jM[i,j]kinM[k,σ(k)]>σ,σ(i)=jakinM[k,σ(k)] iff(M[i,j]a)σ,σ(i)=jkinM[k,σ(k)]>0 iff(M[i,j]a)PER(M)>0

M(n1)×(n1)Mij

holf
источник
Хороший ответ, но, вероятно, стоит четко указать и ответ на вопрос ОП.
Стелла Бидерман