For questions about the mathematical notion of satisfiability.
Questions tagged [satisfiability]
4 questions
4
votes
1 answer
Is there something like Cook's Theorem for Machine Learning?
Cook's Theorem* says that any problem in NP can be reduced to a SAT problem.
*Cook, Stephen A. “The Complexity of Theorem-Proving Procedures.” In Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151–58. STOC ’71. New York, NY,…
Geremia
- 555
- 1
- 5
- 12
3
votes
0 answers
Can Q-learning and other RL algorithms solve CNF SAT?
I encountered a question about solving CNF SAT using reinforcement learning: A state is a partial substitution to the variables, and each action is choosing an empty variable and set its value (to True or False). If the formula is satisfied the…
Dani
- 131
- 2
2
votes
1 answer
What are daily life examples of SAT problems?
What are (good) daily life examples of SAT problems?
I've thought about this one. The problem of placing a bunch of different kinds of glasses in a shared cabinet in such a way that some constraints would be satisfied, such as putting the longer…
Jay Critch
- 343
- 1
- 7
1
vote
0 answers
Write Constraint Satisfaction Formulation for problem
Given $F_1,F_2,..,F_n$ as set of final exams of subjects taken by students $S_1,..,S_k$ in h slots such that no student takes two exams in a single slot.Here the objective is to maximize the number of exams taken by a student in a single slot.
I…
ten do
- 145
- 5