A few days ago Open AI and Anthropic announced the disproval of the Exponential Time Hypothesis by their models and published two relevant papers. ETH essentially states that the 3-SAT problem, in the worst case, can only be computed in exponential time.
Their proves are interesting, however they are not really built on novel ideas. In chapter 3 of my PhD thesis, also available here, I show that the state space, or else solution space, of the NP-hard problems is not a flat set of unrelated solutions. It is a complex space of related states and by exploiting these relations we can build algorithms that avoid the exhaustive computation of all the possible solutions.
I used this framework to build approximate polynomial algorithms by actually partitioning the state space and avoid unnecessary computations. This framework enabled me to build a Distributed Deep Learning method to compute efficiently a really demanding problem concerning resource allocation in datacenters.
The aforementioned proves build sub-exponential algorithms by partitioning the set of possible assignments in groups or tensors by exploiting the solution space properties and relations. The underlying logic has similarities in the three works and highlights fundamental properties of the NP-hard problems.
No comments:
Post a Comment