Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Nondeterministic algorithm (view)

searching for Deterministic algorithm 66 found (112 total)

Yao's principle (786 words) [view diff] exact match in snippet view article find links to article

worst-case input is at least as large as the cost of the best deterministic algorithm on a random input from this distribution. Thus, to establish a

Nitin Saxena (393 words) [view diff] exact match in snippet view article find links to article

and the 2006 Gödel Prize. They provided the first unconditional deterministic algorithm to test an n-digit number for primality in a time that has been

Tarski–Kuratowski algorithm (184 words) [view diff] exact match in snippet view article find links to article

and mathematical logic the Tarski–Kuratowski algorithm is a non-deterministic algorithm that produces an upper bound for the complexity of a given formula

Pseudorandom binary sequence (1,064 words) [view diff] exact match in snippet view article find links to article

pseudorandom bitstream is a binary sequence that, while generated with a deterministic algorithm, is difficult to predict and exhibits statistical behavior similar

Bernard Chazelle (395 words) [view diff] exact match in snippet view article find links to article

heap data structure and the most asymptotically efficient known deterministic algorithm for finding minimum spanning trees. Chazelle was born in Clamart

NL-complete (659 words) [view diff] exact match in snippet view article find links to article

are the most "difficult" or "expressive" problems in NL. If a deterministic algorithm exists for solving any one of the NL-complete problems in logarithmic

Lucas–Lehmer–Riesel test (1,111 words) [view diff] exact match in snippet view article find links to article

is based on the Lucas–Lehmer primality test. It is the fastest deterministic algorithm known for numbers of that form.[citation needed] For numbers of

3SUM (2,672 words) [view diff] exact match in snippet view article find links to article

models of computation (Erickson 1999). It was conjectured that any deterministic algorithm for the 3SUM requires Ω ( n 2 ) {\displaystyle \Omega (n^{2})}

Nosé–Hoover thermostat (909 words) [view diff] exact match in snippet view article find links to article

The Nosé–Hoover thermostat is a deterministic algorithm for constant-temperature molecular dynamics simulations. It was originally developed by Nosé and

Stochastic optimization (1,083 words) [view diff] exact match in snippet view article find links to article

have argued that randomization can only improve a deterministic algorithm if the deterministic algorithm was poorly designed in the first place. Fred W.

Competitive analysis (online algorithm) (794 words) [view diff] exact match in snippet view article

algorithm's internal state at any point during its execution. (For a deterministic algorithm, there is no difference; either adversary can simply compute what

Smale's problems (786 words) [view diff] exact match in snippet view article find links to article

4007/annals.2011.174.3.8. S2CID 706015. Lairez, Pierre (2016). "A deterministic algorithm to compute approximate roots of polynomial systems in polynomial

Random sample consensus (4,157 words) [view diff] exact match in snippet view article find links to article

can be interpreted as an outlier detection method. It is a non-deterministic algorithm in the sense that it produces a reasonable result only with a certain

Adversary model (285 words) [view diff] exact match in snippet view article find links to article

adaptive offline adversary then there also exists an α-competitive deterministic algorithm. If G is a c-competitive randomized algorithm against any adaptive

Symmetric Turing machine (610 words) [view diff] exact match in snippet view article find links to article

the graph. In 2004, Omer Reingold proved that SL=L by showing a deterministic algorithm for USTCON running in logarithmic space, for which he received

Matching (graph theory) (2,938 words) [view diff] exact match in snippet view article

edges). Algorithms for this problem include: For general graphs, a deterministic algorithm in time O ( V E ) {\displaystyle O(VE)} and a randomized algorithm

Pseudorandomness (852 words) [view diff] exact match in snippet view article find links to article

Seemingly random, difficult to predict bit stream created by a deterministic algorithm Pseudorandom ensemble Pseudorandom number generator – Algorithm

Key (cryptography) (1,496 words) [view diff] exact match in snippet view article

applications such as securing information in storage devices. Thus, a deterministic algorithm called a key derivation function (KDF) uses a password to generate

Implicit graph (2,756 words) [view diff] exact match in snippet view article find links to article

for a given implicit graph. Rivest and Vuillemin proved that any deterministic algorithm for any nontrivial graph property must test a quadratic number

Page replacement algorithm (6,235 words) [view diff] exact match in snippet view article find links to article

competitive analysis perspective in the sense that the optimal deterministic algorithm is known. Page replacement algorithms were a hot topic of research

Boolean circuit (1,355 words) [view diff] exact match in snippet view article find links to article

algebra. They are complete in sense that they can perform any deterministic algorithm. However, it just happens that this is not all there is. In the

Neeraj Kayal (391 words) [view diff] exact match in snippet view article find links to article

of arithmetic complexity theory including the development of a deterministic algorithm for primality testing, the resolution of the constant fan-in conjecture

Jean Vuillemin (364 words) [view diff] exact match in snippet view article find links to article

proved the Aanderaa–Rosenberg conjecture, according to which any deterministic algorithm that tests a nontrivial monotone property of graphs, using queries

List update problem (1,286 words) [view diff] exact match in snippet view article find links to article

elements occurring in opposite order in the lists of MTF and OPT. Any deterministic algorithm has a lower bound of 2 − 2 l + 1 {\displaystyle 2-{\frac {2}{l+1}}}

Generalized Riemann hypothesis (1,318 words) [view diff] exact match in snippet view article find links to article

guaranteed to run in polynomial time. The Ivanyos–Karpinski–Saxena deterministic algorithm for factoring polynomials over finite fields with prime constant-smooth

Even–Paz protocol (866 words) [view diff] exact match in snippet view article find links to article

proportionality with contiguous pieces, and it is the fastest possible deterministic algorithm for achieving even partial proportionality and even with disconnected

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

-edge path from s {\displaystyle s} to t {\displaystyle t} , a deterministic algorithm can iterate through all vertices u {\displaystyle u} , and recursively

Propositional proof system (1,121 words) [view diff] exact match in snippet view article find links to article

a fixed tautology. One can view the second definition as a non-deterministic algorithm for solving membership in TAUT. This means that proving a superpolynomial

Accumulator (cryptography) (2,795 words) [view diff] exact match in snippet view article

and that Wit otherwise returns ⊥ {\displaystyle \bot } . Ver: a deterministic algorithm that takes in a key k {\displaystyle k} , a value y {\displaystyle

SL (complexity) (1,779 words) [view diff] exact match in snippet view article

In 1992, Nisan, Szemerédi, and Wigderson finally found a new deterministic algorithm to solve USTCON using only log1.5 n space. This was improved slightly

Computational geometry (2,101 words) [view diff] exact match in snippet view article find links to article

Randomized algorithms that take O(n) expected time, as well as a deterministic algorithm that takes O(n log log n) time, have also been discovered. The

Non-commutative cryptography (1,807 words) [view diff] exact match in snippet view article find links to article

well-studied. The word problem in G should have a fast solution by a deterministic algorithm. There should be an efficiently computable "normal form" for elements

Randomized rounding (4,052 words) [view diff] exact match in snippet view article find links to article

approximation ratio. We next describe a different approach that yields a deterministic algorithm that is guaranteed to match the approximation ratio of the existence

BPP (complexity) (2,427 words) [view diff] exact match in snippet view article

operating on inputs of bounded length can be derandomized into a deterministic algorithm using a fixed string of random bits. Finding this string may be

Bounding sphere (1,516 words) [view diff] exact match in snippet view article find links to article

demonstrating its practicality in higher dimensions. A more recent deterministic algorithm of Timothy Chan also runs in O ( n ) {\displaystyle O(n)} time

Graphic matroid (2,263 words) [view diff] exact match in snippet view article find links to article

representations. The fastest known time bound that has been proven for a deterministic algorithm is slightly superlinear. Several authors have investigated algorithms

Online fair division (3,318 words) [view diff] exact match in snippet view article find links to article

T / n ) {\displaystyle O({\sqrt {T/n}})} . They also present a deterministic algorithm with a similar envy-bound, using the method of pessimistic estimators

Routing (3,729 words) [view diff] exact match in snippet view article find links to article

some other path is better. A few routing algorithms do not use a deterministic algorithm to find the best link for a packet to get from its original source

List of protein tandem repeat annotation software (748 words) [view diff] exact match in snippet view article find links to article

definition for tandem repeats over the edit distance and an efficient, deterministic algorithm for finding these repeats no no TRAL 2015 downloadable Detects

Factorization of polynomials over finite fields (4,620 words) [view diff] exact match in snippet view article find links to article

an equal-degree factorization algorithm. Unlike them, it is a deterministic algorithm. However, it is less efficient, in practice, than the algorithms

Randomized weighted majority algorithm (2,401 words) [view diff] exact match in snippet view article find links to article

The randomized algorithm is better in the worst case than the deterministic algorithm (weighted majority algorithm): in the latter, the worst case was

Cipolla's algorithm (3,035 words) [view diff] exact match in snippet view article find links to article

− n {\displaystyle a^{2}-n} is not a square. There is no known deterministic algorithm for finding such an a {\displaystyle a} , but the following trial

Quasi-Monte Carlo method (1,741 words) [view diff] exact match in snippet view article find links to article

but deterministic, quasi-Monte Carlo method can be seen as a deterministic algorithm or derandomized algorithm. In this case, we only have the bound

Top tree (3,335 words) [view diff] exact match in snippet view article find links to article

bridge separating them. Holm, de Lichtenberg, and Thorup give a deterministic algorithm with amortized update time O ( log 4 ⁡ n ) {\displaystyle O(\log

Maximally matchable edge (1,268 words) [view diff] exact match in snippet view article find links to article

maximum matching M that contains e. Currently, the best known deterministic algorithm for general graphs runs in time O ( V E ) {\displaystyle O(VE)}

Greatest common divisor (4,674 words) [view diff] exact match in snippet view article find links to article

asymptotically faster than the Euclidean algorithm exist; the fastest known deterministic algorithm is by Chor and Goldreich, which (in the CRCW-PRAM model) can solve

Edmonds–Pruhs protocol (1,583 words) [view diff] exact match in snippet view article find links to article

the pieces must be contiguous, and it is the fastest possible deterministic algorithm for achieving even partial proportionality and even when the pieces

K-set (geometry) (1,877 words) [view diff] exact match in snippet view article

K. (1990). "Partitioning arrangements of lines I: An efficient deterministic algorithm". Discrete & Computational Geometry. 5 (1): 449–483. doi:10.1007/BF02187805

Envy minimization (1,233 words) [view diff] exact match in snippet view article find links to article

the product of the envy-difference. With general valuations, any deterministic algorithm that minimizes the maximum envy-ratio requires a number of queries

Schoof's algorithm (4,098 words) [view diff] exact match in snippet view article find links to article

are used, which makes this a Las Vegas algorithm rather than a deterministic algorithm. Under the heuristic assumption that approximately half of the

Tonelli–Shanks algorithm (3,730 words) [view diff] exact match in snippet view article find links to article

a quadratic nonresidue z {\displaystyle z} . There is no known deterministic algorithm that runs in polynomial time for finding such a z {\displaystyle

Stochastic approximation (4,147 words) [view diff] exact match in snippet view article find links to article

then define a recursion analogously to Newton's Method in the deterministic algorithm: θ n + 1 = θ n − ε n H ( θ n , X n + 1 ) . {\displaystyle \theta

Minimum spanning tree (5,421 words) [view diff] exact match in snippet view article find links to article

time. If the graph is dense (i.e. m/n ≥ log log log n), then a deterministic algorithm by Fredman and Tarjan finds the MST in time O(m). The algorithm

Elliptic curve primality (4,810 words) [view diff] exact match in snippet view article find links to article

reached where q is considered small enough to apply a non-recursive deterministic algorithm. Atkin and Morain state "the problem with GK is that Schoof's algorithm

Ski rental problem (1,820 words) [view diff] exact match in snippet view article find links to article

break-even algorithm. The break-even algorithm is known to be the best deterministic algorithm for this problem. A person can flip a coin. If it comes up heads

Knapsack problem (7,647 words) [view diff] exact match in snippet view article find links to article

O^{*}(2^{0.249999n})} (see Corollary 1.4). In contrast, the best known deterministic algorithm runs in O ∗ ( 2 n / 2 ) {\displaystyle O^{*}(2^{n/2})} time with

Proportional cake-cutting (3,383 words) [view diff] exact match in snippet view article find links to article

proportionality with contiguous pieces, and it is the fastest possible deterministic algorithm for achieving even partial proportionality and even with disconnected

Quadratic residue (5,557 words) [view diff] exact match in snippet view article find links to article

finding a quadratic nonresidue modulo n, and there is no efficient deterministic algorithm known for doing that. But since half the numbers between 1 and

Travelling salesman problem (11,464 words) [view diff] exact match in snippet view article find links to article

symmetric, then the longest tour can be approximated within 4/3 by a deterministic algorithm and within ( 33 + ε ) / 25 {\displaystyle (33+\varepsilon )/25}

Leader election (4,419 words) [view diff] exact match in snippet view article find links to article

system has the same state machine for every processor. There is no deterministic algorithm to elect a leader in anonymous rings, even when the size of the

Matroid oracle (4,332 words) [view diff] exact match in snippet view article find links to article

permutation of M ′ {\displaystyle \scriptstyle M'} . But in order for a deterministic algorithm to do so, it must test every one of the n / 2 {\displaystyle \scriptstyle

History of logic (13,242 words) [view diff] exact match in snippet view article find links to article

Turing. These results led to the Church–Turing thesis that any deterministic algorithm that can be carried out by a human can be carried out by a Turing

List of eponymous laws (10,347 words) [view diff] exact match in snippet view article find links to article

worst-case random probability distribution on the inputs, of the deterministic algorithm that performs best against that distribution. Named for Andrew

Group testing (9,937 words) [view diff] exact match in snippet view article find links to article

simulations, SCOMP has been shown to perform close to optimally. A deterministic algorithm that is guaranteed to exactly identify up to d {\displaystyle d}

Maximum disjoint set (4,745 words) [view diff] exact match in snippet view article find links to article

success and run time O ( n 3 ) {\displaystyle O(n^{3})} , or a deterministic algorithm with a slower run time (but still polynomial). This algorithm can

Karmarkar–Karp bin packing algorithms (6,385 words) [view diff] exact match in snippet view article find links to article

packing, using at most m configurations. The total run-time of the deterministic algorithm, when all items are larger than g ⋅ B {\displaystyle g\cdot B}