Timeline for Positive boolean satisfiability problem : finding minimal solutions
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 21 at 2:36 | comment | added | Christopher-Lloyd Simon | @CommandMaster Thank you for the links, this is a good start. Indeed, inclusion minimal is easy to find, but for this question i wish to know the number of minimal solutions : given k, are there more than k inclusion-minimal solutions ? I'm am actually much more interested in the cardinal-minimal question: given k, is there a solution with < k variables set to true. According to the answers of the CS question, it is equivalent to the vertex cover set problem, which is NP hard even for planar graphs, and multigraphs. That answers QB, and hints towards my "plane-connected" conditions. | |
| Jan 19 at 10:38 | comment | added | joro | Vertex cover in graph and "one in three sat" are examples for NP-hardness. | |
| Jan 19 at 5:52 | history | edited | Daniele Tampieri | CC BY-SA 4.0 |
Minor formatting (question mark etc.)
|
| Jan 19 at 5:25 | comment | added | Daniel Weber | @RobertIsrael it doesn't, it gives a set minimal with respect to inclusion. The CS SE question I linked shows that minimum cardinality is NP-hard | |
| Jan 19 at 4:36 | comment | added | Robert Israel | @CommandMaster I don't see how the simple linear algorithm achieves minimum cardinality. For example, if the system is $(x_1 \vee x_2) \wedge (x_1 \vee x_3)$, and you start by setting $x_1$ to $0$, you get the solution $(0,1,1)$ rather than the minimum $(1,0,0)$. | |
| Jan 19 at 3:41 | comment | added | Daniel Weber | For QA.2 see this CS stack exchange question. For QA.1 there's a simple linear algorithm: start with all variables set to 1, go over them in some order, and if they can be set to 0 while still satisfying the formula do that. | |
| Jan 19 at 0:11 | history | edited | Christopher-Lloyd Simon | CC BY-SA 4.0 |
deleted 2 characters in body
|
| S Jan 19 at 0:04 | review | First questions | |||
| Jan 19 at 5:52 | |||||
| S Jan 19 at 0:04 | history | asked | Christopher-Lloyd Simon | CC BY-SA 4.0 |