в 1979 году Хопкрофт / Ульман написал, что L ⊆ P ⊆ NP ⊆ PSpace известно, но L ⊊ PSpace является единственным известным (и тривиальным) сдерживанием, известным, хотя все предполагаются как надлежащие сдерживания, и «где вещи все еще стоят» ~ 4 десятилетия спустя ,
с тех пор существует ли какая-либо известная связь (и) между L ⊊ P, P ⊊ PSpace и P ⊊ NP? все они все еще считаются независимыми, или есть какие-то признаки какой-то взаимозависимости?
мотивация: этот вопрос частично вдохновлен недавними результатами Backurs-Indyk, связывающими SETH с O (n 2 ) расстоянием редактирования. SETH - экспоненциальное время, а расстояние редактирования - PTime. (а также несколько вопрос о доказательстве нижних границ, доказывая верхние оценки )