Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Method that returns an arbitrary model (.solve()) #15

Closed
blyxxyz opened this issue Aug 5, 2020 · 1 comment · Fixed by #19
Closed

Method that returns an arbitrary model (.solve()) #15

blyxxyz opened this issue Aug 5, 2020 · 1 comment · Fixed by #19
Assignees
Labels
enhancement New feature or request good first issue Good for newcomers
Milestone

Comments

@blyxxyz
Copy link
Collaborator

blyxxyz commented Aug 5, 2020

It would be useful to have a .solve() method that returns an arbitrary model for the sentence.

At its simplest, this could be:

def solve(self) -> t.Optional[Model]:
    for model in self.models():
        return model
    return None

But this would be inefficient, because some of the .models() implementations don't start yielding models until all of them have been computed (they aren't lazy).

  • If kissat is enabled, then nnf.kissat.solve() already implements this for CNF.
  • If it isn't, then the naive SAT solver is already lazy, and the above solution will be efficient.
  • ._models_deterministic() isn't lazy, but can easily be (and should be) adjusted so that it is.
  • ._models_decomposable() isn't lazy and can't trivially be made lazy, so it should be complemented by a new method.
  • The fallback implementation is lazy, but otherwise very inefficient. Converting to CNF first and solving that may be better, but you have to take care to remove the newly-introduced aux variables from the model.
@haz
Copy link
Collaborator

haz commented Aug 5, 2020

Depends on #7 to do properly (to handle the aux vars).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request good first issue Good for newcomers
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants