Satsisfiability and Systematicity | Zendy

Matthew L. Ginsberg | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Satsisfiability and Systematicity

Author(s) -

Matthew L. Ginsberg

Publication year - 2015

Publication title -

journal of artificial intelligence research

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.79

H-Index - 123

eISSN - 1943-5037

pISSN - 1076-9757

DOI - 10.1613/jair.4684

Subject(s) - factoring , satisfiability , computer science , flex , boolean satisfiability problem , systematic review , polynomial , theoretical computer science , algorithm , mathematical optimization , mathematics , telecommunications , mathematical analysis , finance , economics , medline , political science , law

We introduce a new notion of systematicity for satisfiability algorithms with restarts, saying that an algorithm is strongly systematic if it is systematic independent of restart policy but weakly systematic if it is systematic for some restart policies but not others. We show that existing satisfiability engines are generally only weakly systematic, and describe FLEX, a strongly systematic algorithm that uses an amount of memory polynomial in the size of the problem. On large number factoring problems, FLEX appears to outperform weakly systematic approaches.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research