Ladner 定理视角下 NP 中间问题猜想被打破：NPI 未必只有次指数解

Peter Schmidtnelson 就 NP 中间问题发推称，最新进展表明 NPI 中的问题未必会存在次指数级算法。这打破了他此前认为 NPI 问题甚至可能落入 BQP、而 NP 完全问题没有次指数算法的看法。该讨论基于 Ladner 定理：若 P≠NP，则 NPI 非空。