Until the strong exponential hypothesis is (dis-)proven, the quadratic cost is required or you have to give something up. Just the cost of exhaustive search.

Until the strong exponential hypothesis is (dis-)proven, the quadratic cost is required or you have to give something up. Just the cost of exhaustive search. As (dis-)proving SETH will resolve the P vs NP problem, I wouldn't hold my breath. The question is if a particular use case can accept those costs.