Решает ли изменение одной записи уменьшение перманента матрицы в полиномиальной иерархии?
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^)
Это может быть решено двумя вызовами оракула #P ... Если бы он был в PH, то это означало бы, что PP также находится в PH ... Однако, если PP находится в PH, тогда PH рухнет. Поэтому я думаю, что вряд ли это в PH.
Тайфун Пей
1
@TayfunPay Я не думаю, что аргумент правильный. Эта проблема может быть решена с помощью двух вызовов #P, но это не может быть исключено так легко, что есть более простой алгоритм, который может показать, что он в PH. Вы должны показать, что это трудно для #P для этого, например, уменьшив значение Permanent.
Ян Йоханнсен
8
Если вы включите определение перманента и упростите полученное неравенство, ваша проблема сводится к тому, является ли перманент данной (n-1) -бай (n-1) матрицы строго положительным.
Гамов,
2
PER(M)>0MM′M ′ - 1 P E R ( M ″ ) = - P E R ( M ′ ) = - P E R ( M ) P E R ( M ) > 0 M ′ ( i , j ) = ( 0 , 0 ) а = - 1M′′M′−1PER(M′′)=−PER(M′)=−PER(M)PER(M)>0M′(i,j)=(0,0)a=−1возвращает истину.
holf
@holf: я думаю, что вы должны опубликовать это как ответ. Это довольно определенно отвечает на вопрос, и тогда вопрос больше не будет выглядеть как «без ответа».
Джошуа Грохов
Ответы:
10
Ваша проблема эквивалентна тестированию с учетом , если .MPER(M)>0
Доказательство : предположим, что вам дано и вы хотите решить, будет ли . Построим следующим образом :
Это Легко видеть, что . Теперь определим как где мы заменяем запись на . Из мультилинейности следует, что . Таким образом, тогда и только тогда, когдаMPER(M)>0M′
Ответы:
Ваша проблема эквивалентна тестированию с учетом , если .M PER(M)>0
Доказательство : предположим, что вам дано и вы хотите решить, будет ли . Построим следующим образом : Это Легко видеть, что . Теперь определим как где мы заменяем запись на . Из мультилинейности следует, что . Таким образом, тогда и только тогда, когдаM PER(M)>0 M′ ⎡⎣⎢⎢⎢10…00…M0⎤⎦⎥⎥⎥ PER(M)=PER(M′) M′^ M′ (0,0) M′ −1 PER(M)=PER(M′)=−PER(M′^) PER(M)>0 PER(M′)>PER(M′^)
Теперь предположим, что вам даны , и и определите как в вашем вопросе, то есть изменивM (i,j) М М [ я , J ]a M^ M[i,j] a PER(M)>∑σ∏k=1nM[k,σ(k)]>∑σ,σ(i)=jM[i,j]∏k≠inM[k,σ(k)]>(M[i,j]−a)⋅∑σ,σ(i)=j∏k≠inM[k,σ(k)]>(M[i,j]−a)⋅PER(M′)>0PER(M^) iff∑σ∏k=1nM^[k,σ(k)] iff∑σ,σ(i)=ja∏k≠inM[k,σ(k)] iff0 iff
источник