This is so tangentially related to the P vs NP problem that the title is basically pure clickbait. Remove every sentence relating to polynomial anything and the information content of the write-up doesn't change at all.
This seems to suffer from a finite-size effect. Wolfram's machines have a tiny state space (s ≤ 4, k ≤ 3). For some class of NP problems, this will be insufficient to encode complex algorithms and is low dimensional enough that it is unlikely to be able to encode hard instances ("worst case") of the problem class. The solution space simply cannot support them.
In this regime, hard problem classes only have easy solutions, think random k-SAT below the satisfiability threshold, where algorithms like FIX (Coja-Oghlan) approximate the decision problem in polynomial time. In random k-SAT, the "hardness" cannot emerge away from the phase transition and by analogy (watch my hand wave in the wind so free) I can imagine that they would not exist at small scales. Almost like the opposite of the overlap gap property.
Wolfram's implicit counter-claim seems to be that the density of irreducibility among small machines approximates the density in the infinite limit (...or something? Via his "Principle of Computational Equivalence"), but I'm not following that argument. I am sure someone has brought this up to him! I just don't understand his response. Is there some way of characterizing / capturing the complexity floor of a given problem (For an NP-hard Problem P the reduced space needs to be at least as big as S to, WHP, describe a few hard instances)?
I find that the "ruliological approach" is very similar to feasible mathematics by Jiatu Li (https://eccc.weizmann.ac.il/report/2025/086/). In the last section before the Personal Notes, "In effect, we’re seeing that theoretical computer science can be done not only “purely theoretically”—say with methods from traditional mathematics—but also “empirically”, finding results and developing intuition by doing explicit computational experiments and enumerations." Where regular mathematics is "purely theoretical" and "empirically" is what Jiatu Li also describes in his paper sometimes referred to reverse mathematics like from Quanta magazine.
I appreciated the great explanation of space complexity and it eludicated why some scientific authors don't include it in their analysis of algorithms. However, Wolfram found that "by successively investigating both larger inputs and longer runtimes, one can develop reasonable confidence that—at least most of the time—one is correctly identifying both cases that lead to halting, and ones that do not." There are exceptions like Machine 600720 that have exceptionally long runtimes but I gain a much better understanding about an algorithm if I'm provided the space complexity. It's still an open question in pure theory but it could be understood from empirical results.
Most of the difficulty arises from conflating discreet and continuous values which a la dirichlet function cannot be integrated whereas discrete values do not physically exist in real computation. Both the physical boundary of the transistor is a probabalistic field as is obviously the analog signal it (probabilistically) discretizes. When you ask ill posed questions in math you get to debate the answer for decades.
18 comments
[ 3.0 ms ] story [ 28.2 ms ] threadI don't understand why new accounts, heavily downvoted and flagged, have higher higher quotas for post rate-limiting than well-reputed commenters.
I look forward to your disproportionately rude response.
This seems to suffer from a finite-size effect. Wolfram's machines have a tiny state space (s ≤ 4, k ≤ 3). For some class of NP problems, this will be insufficient to encode complex algorithms and is low dimensional enough that it is unlikely to be able to encode hard instances ("worst case") of the problem class. The solution space simply cannot support them.
In this regime, hard problem classes only have easy solutions, think random k-SAT below the satisfiability threshold, where algorithms like FIX (Coja-Oghlan) approximate the decision problem in polynomial time. In random k-SAT, the "hardness" cannot emerge away from the phase transition and by analogy (watch my hand wave in the wind so free) I can imagine that they would not exist at small scales. Almost like the opposite of the overlap gap property.
Wolfram's implicit counter-claim seems to be that the density of irreducibility among small machines approximates the density in the infinite limit (...or something? Via his "Principle of Computational Equivalence"), but I'm not following that argument. I am sure someone has brought this up to him! I just don't understand his response. Is there some way of characterizing / capturing the complexity floor of a given problem (For an NP-hard Problem P the reduced space needs to be at least as big as S to, WHP, describe a few hard instances)?
I appreciated the great explanation of space complexity and it eludicated why some scientific authors don't include it in their analysis of algorithms. However, Wolfram found that "by successively investigating both larger inputs and longer runtimes, one can develop reasonable confidence that—at least most of the time—one is correctly identifying both cases that lead to halting, and ones that do not." There are exceptions like Machine 600720 that have exceptionally long runtimes but I gain a much better understanding about an algorithm if I'm provided the space complexity. It's still an open question in pure theory but it could be understood from empirical results.