About: Las Vegas algorithm

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Las Vegas algorithm Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Software, within Data Space : el.dbpedia.org associated with source document(s)

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

Attributes	Values
rdf:type	software
rdfs:label	Las Vegas algorithm (en)
rdfs:comment	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 (en)
sameAs	Las Vegas algorithm Las Vegas algorithm
dbp:wikiPageUsesTemplate	dbt:Citation_needed dbt:Refbegin dbt:Refend dbt:Reflist
Subject	Randomized algorithms
gold:hypernym	Algorithm
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Las_Vegas_algorithm?oldid=1055331744&ns=0
Wikipage page ID	537519 (xsd:integer)
page length (characters) of wiki page	17717 (xsd:nonNegativeInteger)
Wikipage revision ID	1055331744 (xsd:integer)
Link from a Wikipage to another Wikipage	Local search (optimization) NP-completeness NP-hardness Probability Artificial intelligence Atlantic City algorithm Monte Carlo algorithm Randomized algorithms Davis–Putnam algorithm Search problem Decision problem Combinatorial optimization Complexity class Computing Correctness (computer science) Effective method Eight queens puzzle National Institute of Standards and Technology Operations research Partial function Graph isomorphism problem Expected value ZPP (complexity) László Babai Markov's inequality Quicksort RP (complexity) Randomized algorithm Randomness
has abstract	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 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. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Las_Vegas_algorithm
is Wikipage redirect of	Las vegas algorithm Las Vegas method
is Link from a Wikipage to another Wikipage of	List of terms relating to algorithms and data structures Aanderaa–Karp–Rosenberg conjecture Algorithm Algorithmic Lovász local lemma Atlantic City algorithm BPP (complexity) Bogosort Monte Carlo algorithm Catalog of articles in probability theory Gilbert–Varshamov bound for linear codes Decision tree model Decoding methods List of probability topics Counting points on elliptic curves List of algorithm general topics List of computability and complexity topics Graph isomorphism problem Factorization of polynomials over finite fields Labouchère system Lucas–Lehmer–Riesel test Las Vegas (disambiguation) Las vegas algorithm Lateral computing László Babai Maze-solving algorithm Las Vegas method
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/Las_Vegas_algorithm

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (71 GB total memory, 2 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software