For questions on the subject of "satisfiability", that is, whether there exists an interpretation/model in which a given (logical) formula is true.
1
vote
0answers
36 views
Simplify Fibonacci Power Series
I am working on an algorithm to count the number of models for Exactly One in Three SAT (X3SAT) instances. It is known that a chain of X3SAT clauses of length $c$ has $F(c+3)$ satisfying assignments ...
4
votes
2answers
61 views
Can SAT instances be solved using cellular automata?
I'm a high school student, and I have to write a 4000-word research paper on mathematics (as part of the IB Diploma Programme). Among my potential topics were cellular automata and the Boolean ...
0
votes
0answers
20 views
Simplex unusual tableau - how does it correspond to the usual one?
This is an example of simplex, I know a diffrent way with max/min functions and a more handy way to calculate it. How does this method correspond to the usual one, and could somebody find a more handy ...
0
votes
0answers
33 views
Special case of the Weighted Constraint Satisfaction Problem (WCSP)
Solvng the WCSP is NP-hard. Suppose a WCSP instance had only one variable and only contained unary constraints. I have an $O(n^2)$ algorithm for this (where $n$ is the number of unary constraints), ...
2
votes
2answers
132 views
Proving non satisfiability of the barbers paradox with tableau method
The barbers paradox:
In a town there is only one barber. For every man in town, either the barber shaves him or he shaves him self.
I need to formalize this: The barber shaves exactely those who ...
1
vote
0answers
89 views
Prove that a problem is NP-Complete with a reduction from 3-SAT
Here is an instance of a problem:
Instance: {U, S1, . . . Sn, k|U is a set of elements, the Si are diļ¬erent subsets of U, and k is a nonnegative integer}.
A YES instance is defined as follows: There ...
0
votes
1answer
174 views
Converting each formula into Conjunctive Normal Form?
How hard is it to translate an arbitrary well-formed formula into CNF formula? It seems it can get exponential in some occasions like $(a\wedge b)\vee (c\wedge d)$ is transformed into $(a\vee ...
0
votes
1answer
51 views
software for numerical constraint satisfaction problems
Let $m$ be an even integer greater than $8$. Is there any software I can use to determine for some small $m$ whether the following constraints on $t_0,\ldots,t_{m-1}$ and $w$ have solutions?
...
6
votes
1answer
121 views
Deciding a problem: is it in $NP$, $NPC$ or $P$?
I'd like your help with understanding whether the following problem is in $P$, $NP$, $NPC$.
The problem $B$:
Input: a $3CNF$ formula which contains more than one clause.
output: Can we divide the ...
3
votes
1answer
101 views
Potentially stupid question about the Boolean Satisfaction Problem
So I recently learned about the boolean satisfaction problem in an article that linked it to super mario brothers. Anyways, I was wondering why you can't solve the problem in the following way.
...
0
votes
1answer
56 views
Modelchecking on Automata, $\phi$ not SAT and $\phi \models$ False
Given a formula $\phi$
Is $\phi \models FALSE$ equivalent to $\phi$ not SAT?
Or does $\phi \models FALSE$ means that $\phi$ is never $TRUE$ and $\phi$ not SAT means, that there existst at least one ...
4
votes
0answers
106 views
Connect 4 - SAT
My question is about how the Hasbro game Connect4 can be viewed as a SAT problem.
My initial guess is that it would actually be QSAT, and that the 'problem' would be something along the lines of: "Is ...
1
vote
1answer
208 views
What does this notation mean? (Satisfiability / set notation)
I am studying a satisfiablity course as a part of my computer science degree. My lecturer introduced some notation without explaining it and I can't seem to find out through Google.
Let F be a clause ...
2
votes
1answer
322 views
In Satisfiability, what is the difference between the empty clause and the empty set?
The empty clause is a clause containing no literals and by definition is false.
c = {} = F
What then is the empty set, and why does it evaluate to true?
Thanks!
