Známé a nové třídy zobecněných Hornovských formulí s rozpoznáváním a SATem v polynomiálním čase

Abstrakt

V tomto článku zkoumáme několik tříd Booleovských formulí, které zobecňují Hornovské formule a přitom mají také tu vlastnost, že je pro ně SAT testovatelný v polynomiálním čase. Známé třídy jsou porovnány vzhledem k inkluzi a dále je definována hierarchie nových tříd, která obsahuje některé ze známých tříd jako vlastní podmnožiny.

Klíčová slova

• Known
• classes
• generalized
• formulae
• polynomial
• recognition
• testing