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

erwins · 10/10/10 109

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

ИСН · 18/05/06 13438 с Территории

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

Shtorm · 14/02/10 4956

Цитата:

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

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

ИСН · 18/05/06 13438 с Территории

Sonic86 · 08/04/08 8562

(Оффтоп)

erwins · 10/10/10 109

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

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

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

Shtorm · 14/02/10 4956

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

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

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

erwins · 10/10/10 109

Xaositect · 06/10/08 6422

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

Научный форум dxdy

Правила форума

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

Кто сейчас на конференции