The exponential time hypothesis states that the hardest problems in NP, like traveling salesman or subset sum or 3SAT, require exponential time. This was widely believed to be true but has not been proven because that would also prove P ≠ NP, which like Navier Stokes, is one of the $1 million Clay Millineum problems.
OpenAI and Anthropic independently refuted the decades old exponential time hypothesis about a day apart. They found that 3SAT can be solved faster than O(2^n) for n > 10^7. Since 3SAT is NP complete, it means that all problems in NP are sub exponential, including the 3000+ known NP complete ones. https://www.science.org/content/article/ai-cracks-27-year-old-pillar-computer-science-openai-and-anthropic-claim The most practical effect is that it invalidates about 800 math papers that assumed the hypothesis is true. It also suggests weaknesses in encryption algorithms which depend on there being no algorithm for guessing an n bit key faster than brute force searching all 2^n possible keys. This feels sort of like what happens when machines surpass human intelligence and start improving themselves and years of progress happens in days. Maybe if you believe in singularities. Humans can't recognize superhuman intelligence, so what do I know? -- Matt Mahoney, [email protected] ------------------------------------------ Artificial General Intelligence List: AGI Permalink: https://agi.topicbox.com/groups/agi/T84f9e5f945b7204a-M150a3c184ede2b58c21e22dc Delivery options: https://agi.topicbox.com/groups/agi/subscription
