есть ли доказательство, что из равенства p=np следует

[erwins]

что можно найти произведение матриц $n$за время порядка $n^2 \cdot \ln^k (n)$

[ИСН]

а это из него следует? это к нему вообще имеет отношение?

[Shtorm]

Цитата:

есть ли доказательство, что из равенства p=np следует

А $p$ - это тоже матрица? Если $p$ и $n$ - матрицы, то не значит ли это, что $n$ - единичная матрица?

[ИСН]

[Sonic86]

(Оффтоп)

[erwins]

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

-- Пн июн 18, 2012 17:33:01 --

просто интересно, есть ли такой результат.

[Shtorm]

erwins в сообщении #586430 писал(а):

....
из быстрого вычисления паффиана ....
...

Вы хотели написать, пфаффианна?

[erwins]

да

[Xaositect]

А какая связь между пфаффианом и P=NP? Вы точно не имели в виду перманент?