Имеет

Насколько я понимаю, программа теории геометрической сложности пытается разделить , доказав, что постоянство комплексной матрицы гораздо сложнее вычислить, чем определитель.$VP \neq VNP$

Вопрос, который у меня возник после просмотра документов GCT: будет ли это сразу означать , или это просто важный шаг к этой цели?$P \neq NP$

Короткий ответ - нет'. Никаких таких последствий не известно. Есть два основных препятствия: переход от сложности арифметической схемы к логической сложности (VP ≠ VNP подразумевает P / poly ≠ NP / poly), а затем переход от сложности логической схемы (P / poly ≠ NP / poly) к однородной сложности (P ≠ NP). ). Ни один из этих шагов не известен. Однако я считаю, что P / poly poly NP / poly подразумевает VP ≠ VNP.

Предполагая обобщенную гипотезу Римана (GRH), известны следующие довольно сильные связи между и коллапсом полиномиальной иерархии ( P H ):$VP= VNP$${\rm PH}$

1. Если $VP= VNP\,$ (над любым полем), тогда иерархия полиномов падает на второй уровень;
2. Если $VP=VNP\,$над полем характеристики , тогда N C 3 / p o l y = P / p o l y = P H / p o l y ;$0$$\rm{NC}^3/{\rm poly}={\rm P}/{\rm poly} = {\rm PH}/{\rm poly}$
3. Если $VP=VNP\,$над полем конечной характеристики , тогда N C 2 / p o l y = P / p o l y = P H / p o l y .$p$$\rm{NC}^2/{\rm poly}={\rm P}/{\rm poly} = {\rm PH}/{\rm poly}$

Это результаты: Питер Бургиссер, «Гипотеза Кука против Валианта », Теор. Комп. Sci., 235: 71–88, 2000.

См. Также: Бургиссер, « Полнота и редукция в алгебраической теории сложности », 1998.

Я могу дать вам неофициальную причину , по которой разделение не будет доказать .$P \ne NP$

VP и VNP фокусируются на алгебраических функциях, степень которых ограничена полиномом. Обратите внимание, что это легко вычислить в алгебраической функции экспоненциальной степени с алгебраической схемой полиномиального размера.

Хорошо известно уменьшение глубины 1 для алгебраических цепей: любая алгебраическая схема полиномиального размера, вычисляющая полином степени может быть превращена в алгебраическую схему полиномиального размера и глубины O ( log d log n ) .$d$$O(\log d \log n)$

Вы можете думать о как алгебраический вариант N C 2 , таким образом , доказывает , что V Р ≠ V Н Р составляет доказать алгебраическую неравномерную эквивалент N C 2 ≠ # P . Это не исключает P = N P , по крайней мере, не сразу.$VP$$NC^2$$VP \ne VNP$$NC^2 \ne \# P$$P = NP$

Отказ от ответственности : я не могу получить доступ к бумаге прямо сейчас, и я не помню, работает ли сокращение в какой-либо области или только в конечных.

1 LG Valiant, S. Skyum, S. Berkowitz, C. Rackoff. Быстрое параллельное вычисление полиномов с использованием нескольких процессоров . SIAM J. Comput. 12 (4), с. 641-644, 1983.