Las Vegas algorithm
In computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates (is effective), but may output a symbol not part of the solution space to indicate failure in finding a solution. The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where ver
- Ability105616246
- Abstraction100002137
- Act100030358
- Activity100407535
- Algorithm105847438
- Cognition100023271
- Event100029378
- Know-how105616786
- Method105660268
- Procedure101023820
- PsychologicalFeature100023100
- Rule105846932
- software
- WikicatAlgorithms
- WikicatMonteCarloMethods
- WikicatRandomizedAlgorithms
- YagoPermanentlyLocatedEntity
- Comment
- enIn computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates (is effective), but may output a symbol not part of the solution space to indicate failure in finding a solution. The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where ver
- Has abstract
- enIn computing, a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. However, the runtime of a Las Vegas algorithm differs depending on the input. The usual definition of a Las Vegas algorithm includes the restriction that the expected runtime be finite, where the expectation is carried out over the space of random information, or entropy, used in the algorithm. An alternative definition requires that a Las Vegas algorithm always terminates (is effective), but may output a symbol not part of the solution space to indicate failure in finding a solution. The nature of Las Vegas algorithms makes them suitable in situations where the number of possible solutions is limited, and where verifying the correctness of a candidate solution is relatively easy while finding a solution is complex. Las Vegas algorithms are prominent in the field of artificial intelligence, and in other areas of computer science and operations research. In AI, stochastic local search (SLS) algorithms are considered to be of Las Vegas type. SLS algorithms have been used to address NP-complete decision problems and NP-hard combinatorial optimization problems. However, some systematic search methods, such as modern variants of the Davis–Putnam algorithm for propositional satisfiability (SAT), also utilize non-deterministic decisions, and can thus also be considered Las Vegas algorithms.
- Hypernym
- Algorithm
- Is primary topic of
- Las Vegas algorithm
- Label
- enLas Vegas algorithm
- Link from a Wikipage to an external page
- xlinux.nist.gov/dads/HTML/lasVegas.html
- Link from a Wikipage to another Wikipage
- Artificial intelligence
- Atlantic City algorithm
- Category:Randomized algorithms
- Combinatorial optimization
- Complexity class
- Computing
- Correctness (computer science)
- Davis–Putnam algorithm
- Decision problem
- Effective method
- Eight queens problem
- Expected value
- Graph isomorphism problem
- László Babai
- Markov's inequality
- Monte Carlo algorithm
- National Institute of Standards and Technology
- NP-completeness
- NP-hardness
- Operations research
- Partial function
- Probability
- Quicksort
- Randomized algorithm
- Randomness
- RP (complexity)
- Search problem
- Stochastic local search
- Zero-error Probabilistic Polynomial time
- SameAs
- Algorisme de Las Vegas
- Algorithme de Las Vegas
- Algoritmo de Las Vegas
- Algoritmo de Las Vegas
- Algoritmo Las Vegas
- Algoritmus typu Las Vegas
- H7sQ
- Las Vegas algoritam
- Las Vegas algorithm
- Las Vegas algorithm
- Las-Vegas-Algorithmus
- m.02mvmg
- Q1241487
- Q56354236
- Лас-Вегас (алгоритм)
- Лас-Вегас (алгоритм)
- אלגוריתם לאס וגאס
- الگوریتم لاس وگاس
- ラスベガス法
- 拉斯维加斯算法
- Subject
- Category:Randomized algorithms
- WasDerivedFrom
- Las Vegas algorithm?oldid=1117496650&ns=0
- WikiPageLength
- 17810
- Wikipage page ID
- 537519
- Wikipage revision ID
- 1117496650
- WikiPageUsesTemplate
- Template:Citation needed
- Template:Refbegin
- Template:Refend
- Template:Reflist