Enzyklopädie > M > Markierungsalgorithmus
Markierungsalgorithmus
Der Markierungsalgorithmus ist ein Algorithmus zur Überprüfung von Horn-Formeln auf Erfüllbarkeit. Im Unterschied zu allgemeinen aussagenlogischen Formeln, für die vermutet wird, dass kein Polynomialzeit-Algorithmus existiert (siehe Erfüllbarkeitsproblem der Aussagenlogik), ist mit dem Markierungsalgorithmus auf der Menge der Horn-Formeln, die eine Teilmenge der aussagenlogischen Formeln darstellen, ein Polynomialzeit-Algorithmus bekannt (eine Implementierung in linearer Zeit ist möglich).
Mehr Informationen (Wikipedia)
Die Informationen wurden von Wikipedia übernommen, einer offenen Enzyklopädie in welche Freiwillige ihre Beiträge beisteuern.
Die Texte sind unter den Bedingungen der GNU Free Documentation License zugänglich.Encyklopedie (cz) Encyklopédia (sk) Encyclopedia (en)