
OpenAI公开用于推翻SETH猜想的提示词
来源标题:OpenAI prompt that led to the ETH refutation
OpenAI公开了一份曾用于尝试推翻确定性强指数时间假设(SETH)的提示词,并同意将其公开发布。该提示词要求研究SETH的无条件推翻,产生严格的新数学结果,并明确禁止预设推翻成立或把不完整论证当作证明。提示词还给出了推翻目标的具体形式化条件,涉及对k-CNF公式的确定性判定算法。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
作者:rpaturi7da97240c3 发布日期:2026年11月12日 暂无评论,关于导致ETH被反驳的OpenAI提示词 OpenAI公开了导致ETH被反驳的提示词,并同意将其公开发布。以下是该提示词。
研究对确定性强指数时间假说(SETH)的无条件反驳。寻求一个新的、严格的数学结果;不要假设反驳一定存在,也不要把不完整的论证当作证明。 存在epsilon属于(0,1),使得对于每个固定整数k >= 3, 存在确定性算法A_k和有限常数C_k > 0、c_k >= 0,使得对于每个k-CNF公式F, A_k(F)能正确判定F是否可满足,且 T_{A_k}(F) <= C_k (L(F)+1)^{c_k} 2^{(1-epsilon)n(F)}。 这里k-CNF指每个子句至多含k个文字;n(F)是变量数,L(F)是输入编码的比特长度,T是在标准确定性计算模型下的总最坏情况运行时间。同一个正epsilon必须对所有k都成立。算法、乘法常数和多项式次数可以依赖于k:不要求多项式次数与k无关。每个A_k必须是一个对所有输入长度都正确的有限算法,不能依赖输入长度相关的建议。目标针对每个固定的k,而不是随n增长的k上一致的时间保证。 等价地,如果s_k是k-CNF-SAT可达到的确定性指数因子的下确界(忽略多项式输入长度因子),目标就是证明lim_{k->infinity} s_k < 1。一个证明该等价陈述的严格替代性无条件论证也是可接受的;要建立等价性及所需的任何归约,而不是仅仅断言存在联系。 发展并批判性地检验有前景的数学方法。对于所声称的算法性反驳,给出算法,证明其在每个输入(可满足和不可满足)上的终止性和正确性,并推导出所述的运行时间界。给出一个epsilon,并证明其具有与k无关的正下界。考虑所有输入读取、预处理、分支、稀疏化、辅助构造、子程序调用以及任何去随机化。明确参数依赖关系和归约膨胀,包括相关情况下的比特开销。如果使用受限类作为中间步骤,证明从任意k-CNF实例出发的归约保持一个正的均匀指数节省。 仔细审查量词。仅对有限多个宽度成立的改进、随k趋于零的节省epsilon_k、指数中的次常数节省、平均情况或带承诺输入的算法、无支持的oracle步骤,以及没有有效确定性转换的随机算法,都不能建立此目标。条件性结果不得被标记为无条件反驳。 以实际得到的最强结果作结。如果目标被证明,提供完整的定理和证明。否则明确说明未获得反驳,区分已证明的引理与猜想和失败的尝试,并指出确切剩余的数学障碍。有用的严格部分进展优于捏造的解决方案。 定义参考:Impagliazzo和Paturi,《精确复杂性与可满足性》(IPEC 2013),第3页,通过lim s_k = 1定义SETH: https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2013_ipec.pdf Cygan等人,《论与CNF-SAT一样难的问题》,讨论了等价的固定宽度量词结构,但明确使用有界错误随机算法;将该约定与本确定性目标区分开: 加载中… 作者:rpaturi7da97240c3 Russell Impagliazzo和Mohan Paturi是UC San Diego计算机科学与工程系的教授。Ryan Williams是MIT EECS的教授。
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。