TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Simulating Time in Square-Root Space

109 点作者 EvgeniyZh3 个月前

6 条评论

robinhouston3 个月前
This cool result relies on an amazing algorithm that was discovered last year: the Cook-Mertz tree evaluation procedure.<p>See [0] for an exposition, or [1] for a recent popular article about it.<p>0. <a href="https:&#x2F;&#x2F;www.wisdom.weizmann.ac.il&#x2F;~oded&#x2F;p_TreeEval.html" rel="nofollow">https:&#x2F;&#x2F;www.wisdom.weizmann.ac.il&#x2F;~oded&#x2F;p_TreeEval.html</a><p>1. <a href="https:&#x2F;&#x2F;www.quantamagazine.org&#x2F;catalytic-computing-taps-the-full-power-of-a-full-hard-drive-20250218&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.quantamagazine.org&#x2F;catalytic-computing-taps-the-...</a>
评论 #43195650 未加载
评论 #43192219 未加载
LPisGood3 个月前
This reminds me of the joke from Ergodic theory that a lazy physicist can check for phenomena by only looking square numbers.<p>To elaborate, Poincare recurrence says that certain nice dynamical systems will always return to near their original state after finite time, and by Sarkozy’s theorem any set which contains infinitely many pairs of terms that differ by a square is in some sense big enough to observe that recurrence.
nsoonhui3 个月前
Blog post from Scott Aaronson <a href="https:&#x2F;&#x2F;scottaaronson.blog&#x2F;?p=8680" rel="nofollow">https:&#x2F;&#x2F;scottaaronson.blog&#x2F;?p=8680</a>
croissants3 个月前
(To appear at STOC 2025 [1], one of the top CS theory conferences, so it&#x27;s passed peer review.)<p>[1] <a href="https:&#x2F;&#x2F;acm-stoc.org&#x2F;stoc2025&#x2F;accepted-papers.html" rel="nofollow">https:&#x2F;&#x2F;acm-stoc.org&#x2F;stoc2025&#x2F;accepted-papers.html</a>
eru3 个月前
To give a bit of context (context that wasn&#x27;t obvious just from the abstract, at least to me): this paper makes progress on, amongst other things, P!=NP.
评论 #43191414 未加载
CGamesPlay3 个月前
How much space does it take to factor a 2048-bit integer? Just plugging the numbers into the big-O notation, it&#x27;s just some constant times a modest 8.466×10^296 TB.
评论 #43191401 未加载
评论 #43192326 未加载