3-SAT“亚指数时间”概念需区分
热点事件持续更新
3-SAT“亚指数时间”概念需区分
1 篇报道1 个报道来源2 小时前更新
先了解这件事
AI 综述
理论计算机科学家 TCzajka 就新的 3-SAT 亚指数时间结果作出澄清，指出讨论“指数时间”和“亚指数时间”时必须明确采用哪种复杂度定义，否则对结果强度的判断会不同。 在一种定义下，类 E 指运行时间为 2^{O(n)}、即 O(c^n) 的问题；EXPTIME 则涵盖 O(2^{n^k}) 这类更高阶的指数时间，所有 NP 问题均属于其中。亚指数时间通常写作 2^{o(n)}，即对任意 ε>0 都为 O(2^{εn})。TCzajka 的说明正是要区分这些术语，避免把不同的运行时间上界混为一谈。
AI 根据报道生成 · 1 小时前更新
最新进展10月31日 04:14
TCzajka 科普 3-SAT 亚指数时间结果中的「指数时间」歧义报道时间线
沿着报道，了解事件的不同侧面。
10月31日
- AGI HuntTCzajka 科普 3-SAT 亚指数时间结果中的「指数时间」歧义
理论计算机科学家 TCzajka 科普 3-SAT 亚指数时间新结果，区分「指数时间」的两种复杂度含义。类 E 指 2^O(n)，即 O(c^n)；EXPTIME 则涵盖 O(2^(n^k))，所有 NP 问题都在其中。亚指数时间亦有 2^o(n) 定义，即对每个 ε>0 为 O(2^(εn))，不同定义会改变结论强度。
本事件热度走势
还没有足够的连续观测数据，暂不绘制趋势。