Anthropic has released its own claimed refutation of the Exponential Time Hypothesis (ETH), hours after OpenAI said one of its models had disproved the long-standing computer science assumption, TechCrunch reports.
The ETH holds that solving a certain class of hard logic puzzles must take exponentially longer as they grow. Both labs say their models found faster, sub-exponential algorithms. If confirmed, many published papers that rely on the assumption would need revisiting, and there could be implications for cryptography based on certain key sizes.
An Anthropic mathematician suggested OpenAI's work built on existing research. MIT professor Ryan Williams, who once criticised OpenAI's mass release of proofs, is now leading the computer science community's review with Russell Impagliazzo and Ramamohan Paturi, who first proposed the ETH in 1999. They have published an open letter seeking feedback and asked OpenAI to fund a conference on the results.
Source: TechCrunch
