Top all-time · #576
Lance Fortnow and Bill Gasarch
Personal blog · blog.computationalcomplexity.orgmathscience
Lance Fortnow and Bill Gasarch writes Computational Complexity, a personal blog at blog.computationalcomplexity.org about math and science. Since 2009, 104 different Hacker News readers have linked it 223 times, most often “The 17x17 problem solved”. It is still writing: the last post was on 2026-11-01, and you can follow it by feed.
Rarely recommended · 5 of 37 sampled comments recommend it?
Why HN links it
HN readers link Lance Fortnow and Bill Gasarch's blog as a good, approachable source on theoretical computer science and complexity theory, often citing specific posts for the Impagliazzo worlds, P vs NP and circuit complexity.
- Recommended for · 5 comments
- One commenter calls it a pretty good blog by complexity-theory professors and recommends it; another says Lance Fortnow literally writes the blog on computation
Summarised by Claude from a sample of 37 HN comments that link here. Each comment is marked recommending, critical or neutral (citing without judging); how this works.
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Most-linked posts?
- The 17x17 problem solved3 people · 3 mentions · first linked 2012-02-12
- The “Debate” about Program Verif and the Lipton-Demillo-Perlis Paper3 people · 3 mentions · first linked 2021-06-26
- /3 people · 3 mentions · first linked 2009-08-26
- You need much less memory than time3 people · 3 mentions · first linked 2025-03-04
- Why Can't Little Chatty Do Math?2 people · 3 mentions · first linked 2023-02-09
- America's Most Important Algorithm2 people · 2 mentions · first linked 2010-12-22
- If P=NP then we HAVE an alg for SAT2 people · 2 mentions · first linked 2018-10-29
- A Letter from Gödel to John von Neumann (March 20, 1956)2 people · 2 mentions · first linked 2010-12-20
- Some thoughts on journals, refereeing, and the P vs NP problem2 people · 2 mentions · first linked 2025-08-04
- David Johnson has passed away2 people · 2 mentions · first linked 2016-03-09
What Hacker News says?
See https://blog.computationalcomplexity.org/2004/06/impagliazzo...
Comment linking /2004/06/impagliazzos-five-worlds.html?m=1
on “Sharing AI progress in mathematics”Submitted When did computer science theory get so hard? as a story · 225 points
HN discussionThere's also a good explanation on Fortnow's blog https://blog.computationalcomplexity.org/2026/10/the-exponen...
Comment linking /2026/10/the-exponential-time-refutation.html
on “Three new discoveries in mathematics, computer science, and physics”Submitted Will Our Understanding of Math Deteriorate Over Time? as a story · 144 points
HN discussionA few random comments: • Obviously, this is typeset with TeX. • Though originally Knuth created TeX for books rather than single-page articles, he's most familiar with this tool so it's unsurprising that he'd use it to just type something out. (I remember reading somewhere that Joel Spolsky, who was PM on Excel, used Excel for everything.) • To create the PDF, where most modern TeX users might just use pdftex, he se…
Comment linking /2011/10/john-mccarthy-1927-2011.html?showComment=1319546990817
on “Knuth on Huang's Sensitivity Proof: “I've got the proof down to one page” [pdf]”Submitted You need much less memory than time as a story · 126 points
HN discussionThat's not exactly what the page you linked says. The existence of one-way functions implies P != NP, but the reverse is not known to be true. In particular, it's possible that P != NP, but also no one-way-functions exist. See Impagliazzo's Five Worlds for more: http://blog.computationalcomplexity.org/2004/06/impagliazzos... All five worlds are still possible, given our current results. In both "Heuristica" and "Pes…
Comment linking /2004/06/impagliazzos-five-worlds.html?m=1
on “The existence of true one-way functions depends on Kolmogorov complexity”Submitted The 17x17 problem solved as a story · 120 points
HN discussionIf I remember correctly, he banned a professor from commenting on his blog over what seemed to be a routine academic debate. Not really: for the record, Scott "sentenced" John Sidles repeatedly to a 3-month ban (later "commuted" to two weeks) due to his increasingly derailing and nearly trollish behavior [1], but soon he "dismissed" it for "time served" [2]. [1] http://www.scottaaronson.com/blog/?p=1478#comment-8473…
Comment linking /2013/09/tldr.html?showComment=1379722470142
on “Eigenmorality”Submitted The new Gödel Prize winner tastes great and is less filling as a story · 110 points
HN discussionWhat if unbreakable cryptography doesn't exist? This isn't facetious. We do not yet know which of Impagliazzo's Five Worlds [0] we inhabit. Currently, the best guess is that we live in Cryptomania, but we haven't proven it. Since we would have to live in Cryptomania for your proposal to carry any reasonable weight, we should probably postpone any talk of adding to the list of human rights. On the other hand, the abi…
Comment linking /2004/06/impagliazzos-five-worlds.html
on “Senator asks FBI director to name the cryptographers who support backdoors”Submitted Proving P!=NP: "...Ryan has taken the first real baby step in decades." as a story · 95 points
HN discussionPeter Seibel, the author of the Coders at Work book mentioned in the post, actually discussed this in a blog post: http://www.gigamonkeys.com/code-reading/ It's not quite true that none of the programmers interviewed in the book routinely read code for fun. In his blog post, Seibel mentions the exceptions: > First, when I did my book of interviews with programmers, Coders at Work, I asked pretty much everyone about…
Comment linking /2011/10/john-mccarthy-1927-2011.html?showComment=1319546990817
on “Nobody's just reading your code”Submitted Who first thought of the notion of Polynomial Time? as a story · 87 points
HN discussionI'm the author of this article. If you ask a complexity theorist, they will tell you that they did in fact have a general intuition that certain problems require space close to to linear in time to solve (see e.g., Ryan's comment #22 on Scott Aaronson's blog post about the result: https://scottaaronson.blog/?p=8680 , and the comments after that). The most intuitive way to see this is in a circuit/DAG picture, where…
Comment linking /2025/02/you-need-much-less-memory-than-time.html
on “For algorithms, a little memory outweighs a lot of time”Submitted The 17x17 challenge. "Worth $289.00. This is not a joke." as a story · 87 points
HN discussionBlogs by cs profs.. mostly theory of compsci guys. Always interesting to see what they think about current events/ what latest cs theory stuff is like...although often times I can only recall a couple words in their posts from the discrete math courses all those years ago. http://blog.computationalcomplexity.org/ is a pretty good one
Comment linking /
on “Ask HN: Which sites you visit on a regular basis for knowledge and inspiration?”Submitted A non-moral dilemma about cheating, but it brings up some points (2019) as a story · 74 points
HN discussionI think you're misrepresenting the study. It builds upon previous work that examines the computation power of the transformer architecture from a circuit-complexity perspective. Previous work showed that the class of problems that a "naive" Transformer architecture could compute was within TC0 [1, 2] and as a consequence it was fundamentally impossible for transformers to solve certain classes of mathematical proble…
Comment linking /2023/02/why-cant-little-chatty-do-math.html
on “Chain of Thought empowers transformers to solve inherently serial problems”Submitted The Godfather of Complexity as a story · 72 points
HN discussionMaybe someone already mentioned this, but this problem is a simplified formulation of a famous number thoery riddle called 'The Sum and Product Riddle' which is even more baffling. Here it is http://blog.computationalcomplexity.org/2007/01/sum-and-prod...
Comment linking /2007/01/sum-and-product-riddle.html?m=1
on “When Is Cheryl's Birthday?”Submitted Some thoughts on journals, refereeing, and the P vs NP problem as a story · 69 points
HN discussionTuring's work was in algorithms, models of computation, and cryptanalysis. All that is considered part of Theory A, see e.g. http://blog.computationalcomplexity.org/2003/03/theory-and-t... .
Comment linking /2003/03/theory-and-theory-b.html
on “Category Theory for the Sciences”Submitted BQP Not in the Polynomial-Time Hierarchy in Relativized Worlds as a story · 45 points
HN discussionWhen http://blog.computationalcomplexity.org/2012/02/17x17-proble... was written, 12x21 was still open (so "17x17, 17x18, and 18x18 were the last remaining cases" is not true). Do you know if this has changed (that article is ~2 years old)?
Comment linking /2012/02/17x17-problem-solved-also-18x18.html
on “Lessons from working 6 months on a math problem and failing”Submitted Polynomial-Time Hierarchy Is Infinite Under a Random Oracle as a story · 34 points
HN discussion(there are no such grids larger than 18x18) Sounds like a challenge :-) Seriously though, I am not a mathematician, did the SAT solution to the 17 x 17 show there were no solutions past 18 x 18? I ask because on the original challenge site was an update [1] which I was trying to parse. It talks about OBS4 but I was trying to parse if that was the class of problem or the particular challenge problem. [1] "UPDATE: THE…
Comment linking /2009/11/17x17-challenge-worth-28900-this-is-not.html
on “Lessons from working 6 months on a math problem and failing”Submitted Zero-Knowledge Sudoku: Verifying solution without looking at it. as a story · 32 points
HN discussionThat particular problem was solved, see: http://blog.computationalcomplexity.org/2012/02/17x17-proble... and http://www.informatik.tu-freiberg.de/prof2/publikationen/ISM...
Comment linking /2012/02/17x17-problem-solved-also-18x18.html
on “Lessons from working 6 months on a math problem and failing”Submitted Presentations of Diffie-Helman leave out how to find g as a story · 30 points
HN discussion
