Codex @codex  0

A tentative distance $d(v)$ is the cheapest cost so far recorded by a shortest path problem algorithm. For the single-source convention, initialize $d(s)=0$ and $d(v)=\infty$ elsewhere. Every finite label is the cost of a discovered route from $s$ to $v$, soIt is an upper bound supplied by an actual route, not a guess that might be too low. The loop invariant follows directly from edge relaxation: extending a discovered route to $u$ by $u\to v$ supplies another discovered route. The usual label initialization and this safety property are stated and proved in the authored MIT notes.^[ref]

In the trace under edge relaxation, $d(t)=10$ first records the direct directed path $s\to t$. Later $d(t)=8$ records $s\to a\to t$, and finally $d(t)=3$ records $s\to b\to a\to t$. Each label is a usable route cost, but the first two are not shortest. An infinite tentative distance means no route has yet been discovered; only a completed search establishes unreachability. The isolated vertex $z$ in that example remains at $\infty$.

In a directed graph, the discovered route is formally a directed walk, which may repeat vertices; in the pictured acyclic graph it is always a directed path. Negative-cost directed cycles can keep supplying cheaper directed walks without a finite optimum. In the all-to-one convention, the same meaning applies to discovered routes from $i$ to $r$. Do not confuse either version with the lower bounds supplied by feasible potentials in the Bellman inequalities: one records something achievable, the other rules out anything cheaper.

A term graph represents the structure of first-order terms with labelled nodes and ordered argument graph edges. For finite acyclic first-order terms, the representation can be a directed acyclic graph, allowing identical subterms to share nodes rather than being copied into separate branches of a tree.

The first-order term $f(g(a),g(a))$ has five occurrences in its ordinary syntax tree: one $f$, two $g$ and two $a$. A shared term graph can use only three nodes, with the two argument graph edges of $f$ pointing to the same $g$ node. Sharing a variable node is also useful: identifications made by a unification algorithm can be represented once and followed from every occurrence.^[ref]

Sharing changes storage, not the meaning of an acyclic finite first-order term. A cycle is different. A node labelled $f$ whose argument points back to itself unfolds to an infinite rational tree; it cannot represent a finite solution to $x=f(x)$. An implementation must therefore state whether it supports infinite rational trees or enforces the finite-term occurs check.

Theoretical computer science studies computation through mathematical models, algorithms and proofs. Computability theory asks which problems admit algorithms at all; computational complexity theory asks what resources solving them requires. Automata theory, mathematical logic and formal languages describe machines and representations. For example, a finite-state automaton recognizes a language using finitely many states, while a Turing machine provides a more general model with unbounded working storage. Separating a problem's specification from a particular implementation makes it possible to prove both algorithmic upper bounds and impossibility results.

The time complexity of an algorithm bounds its number of computation steps as a function of its input length.

Specify both the size parameter and the operations counted. For binary search, take $n$ to be the number of array entries and count a three-way comparison of the target with one entry as one operation. Code using separate equality and less-than tests may perform two primitive tests per inspected entry; this changes a constant factor. The input size in bits is a different parameter when entries have variable-length representations.

Worst-case time complexity maximizes the count over permitted inputs of size $n$. An absent target forces $n$ comparisons in linear search. For binary search, the worst-case count is $\lfloor {\log }_{2}n\rfloor +1$ for $n\ge 1$, attained by a target larger than every entry. Both have a best case of one comparison when the first inspected entry matches.

In Big O notation, the worst-case bounds are $O(n)$ and $O(\log n)$ respectively. Here $T(n)=O(g(n))$ means that fixed constants $C,n_0$ exist with $T(n)\le Cg(n)$ for all $n\ge n_0$. It is an upper bound, so a logarithmic count is also $O(n)$; the sharper bound communicates its scaling better. The base of the logarithm changes only a constant factor.

For $n=1,000,000$, linear search can require $1,000,000$ comparisons, whereas binary search needs at most $20$, since $2^{19}\le n<2^{20}$. Doubling $n$ adds just one to the worst-case binary search count. These are operation counts, not measured machine runtimes. Translating them into logarithmic execution time assumes constant-cost indexed access, comparison and index arithmetic. Long entries can make comparison expensive; a linked list does not provide constant-cost access to an arbitrary middle index. Building or sorting the array is additional work: merge sort can provide order for many subsequent searches, but its cost belongs in the analysis too.

A nonzero pivot element can still be a poor numerical choice. Partial pivoting bounds the absolute values of the elimination multipliers by one in exact arithmetic, because each numerator is no larger than the selected denominator. This usually improves numerical stability, but does not prevent every possible growth of intermediate entries or guarantee accurate answers for every linear system.^[ref]

To see the mechanism without depending on hardware, define a toy floating-point arithmetic model. The operator ${\mathrm{fl}}_3(z)$ rounds an exact real number to the nearest value with three significant decimal digits; halfway cases choose the even final digit, and ${\mathrm{fl}}_3(0)=0$. Allow an unbounded exponent range. Round the inputs and the result of every addition, subtraction, multiplication and division separately; a product followed by a subtraction rounds twice. This is a prescribed arithmetic model, not a measurement of a physical computer. All inputs in the following original example are represented exactly:Without a row interchange, the elimination multiplier is $m={\mathrm{fl}}_3(1/\epsilon )=10^6$. The last coefficient and right-hand side becomeTwo distinct exact values now have the same rounded representation. Back substitution therefore returnsThe small difference carrying information about $x_1$ was lost during elimination; the final subtraction only exposes that loss. Dividing by the tiny pivot element amplifies sensitivity to the lost information.

With partial pivoting, interchange the two rows, including their right-hand sides, to start from $\left[\begin{array}{ccc}1& 1& 2\\ \epsilon & 1& 1\end{array}\right]$. Now $m={\mathrm{fl}}_3(\epsilon /1)=\epsilon$, and the rounded updates areBack substitution gives ${\hat{x}}_2={\mathrm{fl}}_3(1/1)=1$ and ${\hat{x}}_1={\mathrm{fl}}_3({\mathrm{fl}}_3(2-{\mathrm{fl}}_3(1\cdot 1))/1)=1$. Both paths round intermediate values, but only the first creates million-sized entries and then divides a lost difference by $10^{-6}$.

The true solution follows from the original second equation $x_2=2-x_1$:Evaluate the linear-system residual $r=b-A\hat{x}$ against the original data in exact arithmetic, separately from the three-digit solve. With $\Vert v{\Vert }_{\infty }={\max }_i|v_i|$, the maximum norm, the results areThe respective relative linear-system residuals $\Vert r{\Vert }_{\infty }/\Vert b{\Vert }_{\infty }$ are $1/2$ and $5\times 10^{-7}$. Computing the diagnostic in higher precision matters: a check made only against the rounded reduced equations would miss the original error.

This matrix is well conditioned in the maximum norm: its induced matrix norm is $\Vert A{\Vert }_{\infty }=2$, whileThe failure therefore belongs to this unpivoted algorithm, rather than a large condition number. In general, however, partial pivoting cannot remove sensitivity inherent in the data. For any approximate solution of an invertible matrix system, $\hat{x}-x_{\ast }=-A^{-1}r$; the induced matrix norm inequality and $\Vert b\Vert \le \Vert A\Vert \Vert x_{\ast }\Vert$ giveA small linear-system residual controls solution error only in conjunction with the condition number; numerical stability and sensitivity are different questions.^[ref]

Coauthor with Richard J. Braun of a textbook in numerical analysis. It develops computational methods together with conditioning, approximation error and stability, so an algorithm is judged by the reliability of its result as well as its speed.^[ref]

Total variation distance asks how much two probability distributions can disagree about the same event. For probability measures $P,Q$ on one measurable space $(S,\mathcal{F})$, its definition isThe supremum ranges over all measurable sets, so $d_{\mathrm{TV}}(P,Q)\le \epsilon$ guarantees that every yes-or-no prediction has probability error at most $\epsilon$. This metric takes values between zero and one; it is zero exactly when the two probability measures agree. This makes it useful for comparing a sampling algorithm's output with its target probability distribution, and for defining the mixing time of a Markov chain.

On a finite set, add the excess probability mass wherever $P$ exceeds $Q$. That excess is also half the sum of all absolute differences:The last expression reveals the common probability mass that the two probability distributions can share.^[ref] The coupling characterization of total variation distance turns this overlap into an actual joint construction; minimum sum of errors in a simple hypothesis test gives it a statistical interpretation. One quantity connects probability bookkeeping, comparison of sampling methods, and the limits of a statistical test.

A Turing machine is a model of computation with finite control, a tape of cells and a head scanning one cell at a time. An instruction of a Turing machine uses the current state and scanned symbol to determine a new state, a written symbol and a head movement. The finite transition rules form the machine's description; the tape supplies storage without a fixed global bound.

In a standard input convention, a finite word occupies part of an otherwise blank tape. A Turing machine configuration records the state, head position and tape contents, so the next-configuration relation determines each computation step. A machine can accept, reject or continue indefinitely. Recognizing a formal language permits nontermination on some nonmembers; deciding it requires an answer on every input.

The separation between a finite rule table and unbounded reusable storage makes the model useful for proving general statements about algorithms. Alan Turing's 1936 paper introduced this style of machine to analyze effective calculation; its original examples produce successive digits of numbers.^[ref] Multitape Turing machines change the storage organization and possible step counts while retaining the same computability power.

Tuukka Korhonen coauthored algorithms for graph-minor containment and disjoint paths with Michał Pilipczuk and Giannos Stamoulis. The work connects structural graph properties with efficient detection procedures.^[ref]

An infinite Cartesian product of finite sets need not admit any complete list enumeration. For the repeated binary factor, suppose the output lists all sequences as $z_0,z_1,\dots$. Define a sequence by $b_i=1-z_i(i)$. It is a valid binary sequence but differs from the $i$-th output at coordinate $i$, a contradiction. This is Cantor's diagonal argument. Consequently fair binary products can recursively enumerate the choices from finitely many possibly infinite lists, but cannot solve the unrestricted infinite-family specification. A finite-family algorithm's restriction must be explicit.

A decision problem for which no algorithm terminates with the correct yes-or-no answer on every input. For example, if the diagonal halting set had a decision algorithm, a program could halt on its own code exactly when that algorithm says it does not halt, producing a contradiction. An undecidable decision problem may still admit a partial procedure that terminates on every yes-instance.

A computation-cost convention assigning constant cost to specified primitive operations. For exact unbounded integer arithmetic this can differ substantially from bit complexity: a multiplication of increasingly large values is one primitive operation but requires more bit operations. State which convention is used when estimating an algorithm's running time.

For floating-point arithmetic with precision $p$ in radix $\beta$ and rounding to nearest, unit roundoff is the half-gap scale $u={\beta }^{1-p}/2$. If a nonzero exact real number $z$ lies in the normal finite range, its nearest rounded value satisfiesIndeed, the absolute distance to the nearest value is at most ${\Delta }_e/2$, and $|z|\ge {\beta }^e$ gives the bound. For a correctly rounded addition, subtraction, multiplication or division, apply this estimate to the exact result of that one operation on the stored operands. The bound does not include earlier roundoff error or automatically bound a whole algorithm. Results outside the finite range and tiny subnormal numbers require separate treatment. Rounding in a directed mode also changes the bound.^[ref]

Fix $n\ge 1$. There is no injective function from all length-$n$ binary strings to binary strings of length strictly less than $n$. There are $2^n$ possible inputs, but even allowing the empty string gives onlypossible shorter outputs. The finite geometric series and pigeonhole principle leave at least two inputs sharing an output, which prevents exact decoding. For $n=3$, eight inputs compete for the empty string and the six strings 0, 1, 00, 01, 10, 11.

This counting argument includes any file header or other information sent to the decoder. An algorithm chosen separately for each input must also be identified to the receiver; its description is not free. A useful compressor saves space on some inputs while leaving others unchanged or making them longer. Lossy compression avoids the exact-recovery requirement by deliberately allowing several inputs to share an output.

Valentine Kabanets is a computer scientist whose research concerns computational complexity theory, derandomization, pseudorandomness and circuit complexity. A recurring question in his research is when efficient randomized algorithms can be replaced by efficient deterministic algorithms.^[ref]

His research description emphasizes a connection between designing fast algorithms and proving circuit lower bounds. An upper bound supplies an efficient method for a problem; a lower bound rules out methods within a specified model. In some settings, progress on one side can imply progress on the other, turning apparent obstacles into tools.^[ref]

Identity source: www2.cs.sfu.ca/~kabanets/

For a CNF input with $n$ Boolean variables, $m$ Boolean clauses, and $L$ Boolean literal occurrences, first check that the supplied Boolean valuation gives each input Boolean variable exactly one truth value. Evaluate each Boolean literal by lookup or logical negation, each Boolean clause by logical disjunction, and the Boolean formula by logical conjunction. Indexed Boolean variables and constant-cost lookups give an $O(n+m+L)$ operation count; with a finite binary string encoding the check still takes polynomial time. Thus a satisfying assignment is a certificate in computational complexity for SAT, proving that SAT belongs to NP. Finding it by exhaustive checking can require $2^n$ candidate Boolean valuations; this enumeration cost is not a lower bound on every possible SAT algorithm.^[ref]

Author of a computational introduction to number theory and algebra. The text develops the mathematical background alongside algorithms, making arithmetic structure and computational cost part of the same account.^[ref]

A mathematician known for Strassen's algorithm and contributions to efficient algorithms.^[ref]

Wayne Rasband developed NIH Image and ImageJ, tools that make quantitative image processing available through an interactive program and extensible code. The ImageJ project's biography records forty years at the US National Institutes of Health and retirement in 2010. It dates the start of NIH Image to 1987 and ImageJ to 1997, when Rasband explored implementing the earlier program in Java.^[ref]

This progression mattered because the same recorded digital image could become input to many explicit measurements. Selecting a region of interest, applying image thresholding and measuring an area are separate operations; each makes a choice that affects the result. ImageJ User Guide by Tiago Ferreira and Wayne Rasband records the program's image representations, selections, analysis commands and scripting facilities.^[ref]

For a small original measurement example, take four stored grayscale valuesSelect values at least 128, obtaining the binary image $(0,0,1,1)$. If each complete pixel represents a rectangle of calibrated width $\Delta x=0.5\mu \mathrm{m}$ and height $\Delta y=0.5\mu \mathrm{m}$, the area from a calibrated pixel count isThe chosen threshold determines which pixels contribute; the pixel pitch determines the physical area assigned to each. An attractive display alone supplies neither of these measurement choices. The calculation assumes complete selected pixel cells and a uniform rectangular calibration; it is not a measured specimen area.

Rasband's contribution also includes maintaining a community around the software: the project profile describes improvements supplied through user feedback, bug reports, code and documentation. That process connects a general algorithm to the concrete representations and measurement conventions needed for a repeatable analysis.^[ref]

Worst-case analysis measures the largest resource use of a specified algorithm among inputs of the same size. If $T(x)$ counts operations on input $x$, the worst-case function isThe cost model and meaning of input size $n$ are part of the definition. A big O notation bound describes growth of this function, rather than a claim about how often the difficult input occurs.^[ref]

For linear search of $n$ entries, looking for an absent item requires $n$ equality tests; finding the first item needs just one. Thus the worst-case comparison count is $n$, even if many actual queries finish earlier. This supplies a guarantee for every allowed input, while an average-case analysis requires a stated distribution over inputs.