Delphi.science

A Las Vegas algorithm for satisfiable SAT formulas, with an application to timetabling

Source: arxiv.org/abs/2611.18720

Fabio Dias

arXivarxiv/2611.18720Nov 8, 2026math.GMscore 0

Many scheduling problems need many different feasible timetables, and a view of how much freedom each event has. We study a Las Vegas algorithm that samples satisfying assignments of a Boolean formula one variable at a time: it draws each value from an estimate of its conditional probability, propagates, and restarts on a contradiction. Every output is a checked solution and comes with the exact probability of producing it. We prove that a run succeeds with probability at least $2^{-K}$, where $K$ is the expected Kullback--Leibler divergence between the true and estimated conditional…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.18720
curl -X POST /api/v1/records/arxiv/2611.18720/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.18720/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'