APC Science Union · Online Library

A deterministic comparison-based sorting algorithm requires Ω(nlg⁡n)\Omega(n\lg n)Ω(nlgn) comparisons on its worst-case input. But how many comparisons does a randomized algorithm make in expectation on its worst-case input? This article introduces Yao’s principle and uses it to derive a lower bound for randomized sorting. Author: silverxz Reviewed by: phy东西 Introduction   The Ω(nlg⁡n)\Omega(n\lg n)Ω(nlgn) lower bound on the worst-case number of comparisons made by a deterministic comparison-based sorting algorithm is a classic result. It appears in textbooks such as Introduction to Algorithms and in most algorithms courses, so many readers will already know it. (This article assumes only an introductory knowledge of algorithms and probability theory. Following the usual convention in ...

Will a bottle of mineral water chill faster in the refrigerator standing up or lying on its side? Laying it down seems to expose more surface area to the cold air, but does that actually help? Let’s find out. Author: 锅炉-251 Reviewed by: 薛定谔的猫 Introduction   Suppose you want to chill a room-temperature bottle of mineral water as quickly as possible. How would you place it in the refrigerator? Many people instinctively say, “Lay it on its side; that puts more of the bottle in contact with the cold air.” Others argue, “Stand it up, because cold air sinks.”   This ordinary question produces plenty of conflicting answers. An important idea from heat transfer, however, can help us sort them out: natural convection [1]. Figure 1. Which orientation—horizontal or upright—favors natural convect ...

Mathematics did not begin as a fully rigorous discipline. Throughout its history, Bertrand’s paradox and disputes over infinitesimals have both exposed the uncertainty that vague definitions can create. In response, mathematics gradually moved toward formal expression. Author: silverxz Reviewer: ΔδDelta\Delta\delta DeltaΔδDelta Introduction: Ask “What Is It?” First   Whether we are learning mathematics or solving a problem, it is natural to begin by asking, “What is it?”   A high school student encountering sets for the first time must begin by learning what a set is, even if the answer is only the informal statement that “a set is a whole formed by putting some objects together.” Only after grasping that idea can the student answer other questions about sets or move on to concepts suc ...

From the age of the steam engine to the nuclear power plant, humanity has spent centuries tinkering with technology and is still boiling water. Photovoltaics, wind turbines, fuel cells, magnetohydrodynamic generators—why have all these seemingly more advanced technologies failed to replace the same kettle we have kept boiling for three hundred years? Author: 锅炉-251 Reviewer: 赖渊 Introduction   A familiar joke says that human progress amounts to boiling water and throwing rocks. The first half refers to modern electricity generation, which relies mainly on thermodynamic cycles that use steam as the working fluid. The second says that humans still inflict damage mainly by projecting mass at a target. This article focuses on energy. By examining where energy comes from, how it is used, and ...

Author: 时光 Reviewed by: 阿氯 It Started with a Bulging Phone Back   One evening, a friend sent me a photo of their phone. The battery appeared to have swollen, forcing the back cover apart and leaving a truly sorry sight. Gone but not forgotten Image source: Provided by a friend of the author; not publicly available   This is hardly an unfamiliar sight. In 2017, barely a week after Apple’s iPhone 8 series went on sale, several incidents were reported around the world in which swollen batteries pushed the screens of newly unboxed or charging phones out of their frames. A user's post on the social-media platform Twitter, now called X Image source: Magokoro0511. Screenshot of a post[EB/OL]. X (formerly Twitter), 2016-09-25 [accessed 2026-03-03]. Photograph of a swollen battery Image sourc ...

Author: silverxz Proofreader: Acidmoon   In this article, we will prove that the Diophantine sets are exactly the recursively enumerable sets.   We have already noted that the direction from Diophantine sets to recursively enumerable sets is fairly straightforward. Let SSS be a Diophantine set with corresponding Diophantine equation D(x1,...,xn,y1,...,ym)=0D(x_1,...,x_n,y_1,...,y_m)=0D(x1​,...,xn​,y1​,...,ym​)=0. For (a1,...,an)∈Nn(a_1,...,a_n)\in \mathbb{N}^n(a1​,...,an​)∈Nn, we need only have a Turing machine MMM systematically try every possible y1,...,ymy_1,...,y_my1​,...,ym​ to see whether D(a1,...,an,y1,...,ym)=0D(a_1,...,a_n,y_1,...,y_m)=0D(a1​,...,an​,y1​,...,ym​)=0 holds. If (a1,...,an)∈S(a_1,...,a_n)\in S(a1​,...,an​)∈S, the machine will eventually halt. The candidates must, of ...

Author: silverxz Proofreader: Shiguang   We now turn to the proof itself. This is not the original proof, but Matiyasevich’s greatly simplified version from his book Hilbert’s Tenth Problem, so its approach differs somewhat from the historical route described earlier. We will simplify parts of the argument further and skip details that are laborious but add no new ideas. The exposition often works backward: it starts from a result, asks what tools are needed to prove it, and then supplies those tools one by one. I will also use ordinary language to build an intuitive picture of the proof and explain its motivation, an approach better suited to a popular introduction. What is Hilbert’s Tenth Problem?   Let us first restate the problem we want to solve.   A Diophantine equation is a multi ...

Trial of Xuan · Unity WebGL The game opens on its own page rather than inside this article. The initial download is about 115 MB, so Wi-Fi is recommended. On a phone, it plays best in landscape mode. Play Trial of Xuan

Author: silverxz Proofreader: Shiguang   Many years later, when Hilbert’s Tenth Problem had finally been laid to rest, Martin Davis would surely remember that distant afternoon when his teacher said, “Hilbert’s Tenth Problem begs for an unsolvability proof.”   We have already seen how Gödel, Turing, and others shattered the completeness, consistency, and decidability sought by Hilbert’s program. Hilbert’s Tenth Problem is simply a special case of the decision problem. The negative answer to that broader question transformed almost all optimism about Hilbert’s Tenth Problem into pessimism within a decade.   Emil Post was one of the founders of computability theory, but fortune rarely favored him. At twelve, he lost his left arm in a car accident, which led him to abandon astronomy for mat ...

Author: Shiguang Reviewed by: Mei Shida Publishing and Editing Publishing, or more fully “publishing activity,” is the professional practice of selecting, editing, reproducing, and distributing works to the public. It encompasses the many steps that take a work from raw manuscript to finished publication, with the goal of bringing worthwhile information to readers. In Chinese, the word for editing can refer both to the process of organizing and refining source material or an existing work and to the professional who does that work, such as a book editor at a publishing house. Editors organize, record, collect, arrange, compile, and review intellectual works and other documents before presenting them to the public. Editing is an essential part of publishing and must happen before a publi ...