This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Statistics Low‑importance This article is within the scope of WikiProject Statistics, a collaborative effort to improve the coverage of statistics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.StatisticsWikipedia:WikiProject StatisticsTemplate:WikiProject StatisticsStatistics Low This article has been rated as Low-importance on the importance scale. Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

User MrOllie has recently removed my contributions about the probabilistic classes, the No Free Lunch theorem, and the Turing-completeness of stochastic local search algorithms arguing citation spam. I would like to ask a volunteer to review the relevance to these contents, which were reverted by MrOllie at 23:03, 20 February 2024‎ (UTC). EXPTIME-complete (talk) 23:47, 20 February 2024 (UTC)Reply

In particular, this is the text I would like to introduce again:

In fact, some important open problems in Complexity involve finding out whether randomness allows to solve problems in shorter time (e.g. the P = BPP problem). Sometimes the convergence of stochastic local search algorithm to the optimal solution comes as a direct consequence of the fact that, at each iteration, the algorithm has a probability greater than zero of jumping from any solution to any other solution in the search space, so the optimal solution will eventually be found. If no additional conditions can be taken into account, then the average time to find the solution of that random search is the same as if an exhaustive search were performed. The No free lunch theorem for optimization establishes conditions under which the computational cost of finding a solution, averaged over all problems in the class, is the same for any solution method. Moreover, it has been proved that essential semantic properties of stochastic local search algorithms such as e.g. whether they will find the optimal solution or a solution at some distance of the optimal value are undecidable in general. The reason for this is that these algorithms can simulate any program (i.e. they are Turing-complete) —in particular, also if their basic ingredients (e.g. fitness function, crossover and mutation operators, etc.) are required to be very simple.^[1]

This text was introduced right after the following paragraph, which remains in the current version:

In contrast, some authors have argued that randomization can only improve a deterministic algorithm if the deterministic algorithm was poorly designed in the first place.[21] Fred W. Glover[22] argues that reliance on random elements may prevent the development of more intelligent and better deterministic components. The way in which results of stochastic optimization algorithms are usually presented (e.g., presenting only the average, or even the best, out of N runs without any mention of the spread), may also result in a positive bias towards randomness.