# Questions tagged [sat]

Questions about the Boolean satisfiability problem from computability and complexity theory. If your question is about the college entrance exam called the SAT, you are on the wrong site.

22 questions
Filter by
Sorted by
Tagged with
1 vote
63 views

### Is it possible to find UNSATisfiable solutions to a SAT problem with a SAT problem?

I'm working with several problems, which can have special unsatisfiable configurations. For example, consider the simple function $f(x,y)=x+y+2$ with $n$-bit unsigned inputs and $(n+2)$-bit unsigned ...
140 views

### Lower bound on the number of solutions of 2SAT

To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...
• 1,059
227 views

### Size of 3-SAT assignments

Let $F(N,M)$ be the set of 3-SAT formula with $N$ variables and $M$ clauses. For a given formula $f\in F(N,M)$, we can ask for the set $s_f$ of truth assignments that satisfy $f$. (If $f$ is ...
• 3,396
232 views

### Sum of perfect matching construction

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...
• 13k
1 vote
51 views

### Reduction maximum independent set to MIS in a very dense graph

We got a reduction maximum independent set to MIS in a very dense graph, or alternatively negative monotone 2-CNF to MAX-ONEs with a formula with many clauses. Let $G$ be graph of order $n$ and ...
• 23.5k
571 views

### Is strictly harder than NP-hard cryptography possible?

Looks like there is cryptography based on NP-hard problem, e.g. McEliece cryptosystem. The algorithm is an asymmetric encryption algorithm and is based on the hardness of decoding a general linear ...
• 23.5k
870 views

### Does this prove Collatz is a $\Sigma_1$ problem?

So I got an email from one of my colleagues on the Collatz Conjecture with a link to the article Computer Scientists Attempt to Corner the Collatz Conjecture by Kevin Hartnett in Quanta Magazine. On ...
• 13k
200 views

### Mapping problems to Boolean formulas for SAT solvers

I came across Marijn Heule and Oliver Kullmann's paper on recent techniques in highly efficient SAT solvers. In particular they describe the Pythagorian Triple Problem, which they solved using that ...
• 115