# 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.

29 questions
Filter by
Sorted by
Tagged with
1 vote
71 views

### Complexity of solving system of binary quadratic equations modulo $3$

A special case of this question and another question What is the complexity of solving system of binary quadratic equations modulo $3$? $f_i(x_i,x_j)=0 \bmod 3, \deg{f_i}=2$. Modulo $2$ can be ...
• 25.1k
1 vote
77 views

### On binary constraints defined by vanishing of bivariate polynomials modulo $n$ [duplicate]

In an answer here Dima Pasechnik showed that constraints of the form $x_i x_j + a_{ij}x_i + b_{ij}x_j + c_{ij}$ are efficiently solvable modulo $2$ using Groebner basis. In comments he suggested that ...
• 25.1k
250 views

### Is there a version of 3-SAT that is NP-complete but grows like $2^n$ instead of $2^{n \choose 3}$?

If I have $n$ variables and I want to write down all 3-SAT problems, the number of problems is $2^{8{n \choose 3}}$, since each clause has 3 variables and each variable can be negated or not. But ...
• 31
71 views

### Fast checking that a system of polynomial equations is satisfiable over $\mathbb{F}_2$

I have a (fairly large) system of polynomial equations, of the form $$c_1d_1=0,\ c_1d_2+c_2d_1=0,\ldots$$ (In case it is relevant, all the polynomials are homogeneous of degree 2, except for exactly ...
• 18.4k
124 views

### Efficiency of Groebner basis for constraints of the form $(a_i x_i+b_i)(a_j x_j+b_j)$

This is based on numerical experiments in sage. Let $K$ be a ring and define the ideal where each polynomial is of the form $(a_i x_i+b_i)(a_j x_j+b_j)$ for constant $a_i,b_i,a_j,b_j$. Q1 Is it true ...
• 25.1k
112 views

### Positive boolean satisfiability problem : finding minimal solutions

Consider, over a finite set of boolean variables $X$, a Boolean system in CNF (conjunctive normal form) whose clauses only contain non-negated literals. For every assignment of the variables which ...
1 vote
1k views

### Possible cardinalities of the sets tautologically implied by minimal sets

Question Consider the set $V$ of all unordered 3-clauses $(l_1, l_2, l_3)$, where $l_i$ is a literal (i.e. a variable $x$ or its negation $\neg x$), and no clause contains two literals having the same ...
• 11
1 vote
231 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 ...
352 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,169
236 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,919
243 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 ...
• 13.8k
1 vote
71 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 ...
• 25.1k
692 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 ...
• 25.1k
987 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 ...
• 13.8k
296 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 ...
• 155