Find link

language:

Find link is a tool written by Edward Betts.

searching for Pigeonhole principle 14 found (112 total)

Proof complexity (3,737 words) [view diff] exact match in snippet view article find links to article

and the pigeonhole principle. Ajtai (1988) proved a superpolynomial lower bound for the constant-depth Frege system and the pigeonhole principle. This was

Universe 3 (Silverberg anthology) (211 words) [view diff] case mismatch in snippet view article

A. DiChario) "The Only Thing You Learn" (Barry N. Malzberg) "The Pigeonhole Principle" (David Ira Cleary) "Going West" (Phillip C. Jennings) "McGregor"

Sandu Popescu (1,577 words) [view diff] exact match in snippet view article find links to article

quantum paradoxes, such as the quantum Cheshire cat, and the quantum pigeonhole principle. They also introduced the idea of superposition of time evolutions

Turán graph (1,248 words) [view diff] exact match in snippet view article find links to article

Turán's theorem, an important result in extremal graph theory. By the pigeonhole principle, every set of r + 1 vertices in the Turán graph includes two vertices

Semi-deterministic Büchi automaton (1,299 words) [view diff] exact match in snippet view article find links to article

accepting run of A run(q0,0)⋅run(q1,1)⋅run(q2,2)⋅... Hence, by infinite pigeonhole principle, w is accepted by A. Proof: The definition of projection function

Parikh's theorem (1,865 words) [view diff] exact match in snippet view article find links to article

proof is essentially the same as the standard pumping lemma: use the pigeonhole principle to find k{\displaystyle k} copies of some nonterminal symbol A{\displaystyle

Induction, bounding and least number principles (1,125 words) [view diff] exact match in snippet view article find links to article

φ{\displaystyle \varphi }, ψ{\displaystyle \psi }. The infinite pigeonhole principle is known to be equivalent to BΠ1{\displaystyle {\mathsf {B}}\Pi _{1}}

Straight-line program (1,565 words) [view diff] exact match in snippet view article find links to article

Now suppose for a contradiction that |K(i+1)| < 2|K(i)|. By the pigeonhole principle there are k1,k2 ∈ K(i+1) with k1 = z1α1·z2α2·...·zi+1αi+1 = z1β1·z2β2·

Proofs of convergence of random variables (2,335 words) [view diff] exact match in snippet view article find links to article

\varepsilon /2\right)\end{aligned}}} where the last step follows by the pigeonhole principle and the sub-additivity of the probability measure. Each of the probabilities

Lonely runner conjecture (3,275 words) [view diff] exact match in snippet view article find links to article

\{v_{i}t\}\in (1/n,1-1/n)} for all i {\displaystyle i} . By the pigeonhole principle, there exist distinct i {\displaystyle i} and j {\displaystyle j}

Algorithmically random sequence (4,774 words) [view diff] exact match in snippet view article find links to article

encoding". Conversely, if the sequence is compressible, then by the pigeonhole principle, only a vanishingly small fraction of sequences are like that, so

Brouwer fixed-point theorem (8,372 words) [view diff] exact match in snippet view article find links to article

\sum _{i=0}^{n}{P_{i}}=1=\sum _{i=0}^{n}{f(P)_{i}}} Hence, by the pigeonhole principle, for every P ∈ Δ n , {\displaystyle P\in \Delta ^{n},} there must

Algorithmic problems on convex sets (3,992 words) [view diff] exact match in snippet view article find links to article

membership queries; this is a valid sequence of answers, since by the pigeonhole principle, there is an interval of length 2 that does not contain any querired

Maximin share (11,167 words) [view diff] exact match in snippet view article find links to article

1-out-of-n MMS w.r.t. the original set O. This is because, by the pigeonhole principle, at least one MMS part of each agent must contain two or more objects