Find link

language:

Find link is a tool written by Edward Betts.

Longer titles found: Nondeterministic algorithm (view)

searching for Deterministic algorithm 66 found (116 total)

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

Lucas–Lehmer–Riesel test (1,066 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

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

3SUM (2,676 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 (931 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 Shuichi

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

quantities are equal: The optimal performance that can be obtained by a deterministic algorithm on a random input (its average-case complexity), for a probability

Stochastic optimization (1,071 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

Random sample consensus (4,146 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

Smale's problems (882 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

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

Pseudorandomness (858 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

Matching (graph theory) (3,032 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

Key (cryptography) (1,517 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

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

Boolean circuit (1,365 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

Page replacement algorithm (6,238 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

Implicit graph (2,839 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

List update problem (1,339 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,330 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

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

Savitch's theorem (1,094 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

Even–Paz protocol (986 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

SL (complexity) (1,793 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,116 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,456 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

Knapsack problem (7,744 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

Graphic matroid (2,283 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

Routing (3,766 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

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

Bounding sphere (1,736 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 runs in O ( d ( 1 2 + o ( 1 ) ) d n ) {\displaystyle

Factorization of polynomials over finite fields (4,636 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

Cipolla's algorithm (3,042 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

Top tree (3,226 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,739 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

Envy minimization (1,314 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,090 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

Average-case complexity (3,058 words) [view diff] exact match in snippet view article find links to article

problems, average-case complexity for a hard input distribution and a deterministic algorithm adapted to that distribution is the same thing as expected complexity

Tonelli–Shanks algorithm (3,751 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,388 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

K-set (geometry) (2,270 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

Diameter (computational geometry) (982 words) [view diff] exact match in snippet view article

doi:10.1007/BF02187740, MR 1014736 Ramos, E. A. (2001), "An optimal deterministic algorithm for computing the diameter of a three-dimensional point set", Discrete

Elliptic curve primality (4,793 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

Minimum spanning tree (5,460 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

Ski rental problem (1,822 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

Quadratic residue (5,575 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

Proportional cake-cutting (3,416 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

Travelling salesman problem (11,604 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,410 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,287 words) [view diff] exact match in snippet view article find links to article

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

History of logic (13,255 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,530 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,934 words) [view diff] exact match in snippet view article find links to article

shown to perform close to optimally. Polynomial Pools (PP) is 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,386 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}

Universal multiport interferometer (4,174 words) [view diff] exact match in snippet view article find links to article

N\times N} (discrete) unitary mode transformation. Using their deterministic algorithm to decompose a given unitary into a triangular network of these