All Questions
Tagged with sat computational-complexity
14 questions
3
votes
0
answers
255
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
3
votes
0
answers
125
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 ...
4
votes
1
answer
362
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,207
8
votes
0
answers
237
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,979
3
votes
1
answer
708
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.4k
1
vote
0
answers
36
views
Is there an algorithm for this constrained Hypergraph optimization problem?
I'm currently developing an algorithm for computing knot coloring invariants and got to the following question:
Given a set $S$ and a certain hyper-graph $H \subseteq S^3 $, find a decomposition $S = ...
- 133
16
votes
4
answers
1k
views
Representing mathematical statements as SAT instances
The following problem (call it THEOREMS) belongs to class NP.
Input: Mathematical statement $S$ (written in some formal system such as ZFC) and positive integer $n$ written in unary.
Output: "Yes" if ...
- 781
2
votes
0
answers
66
views
$3$SAT generation with prescribed number of solutions
Given $n,k\in\Bbb N$ with $0\leq k \leq 2^n$ can we generate an uniformly random instance among all possible solutions of an $n$ variable $3$-SAT instance and exactly $k$ solutions in $poly(n\log k)$ ...
- 13.9k
-1
votes
1
answer
445
views
What is wrong with the argument that zero permanent is polynomial?
This Lecture summarizes some well known facts about $\#P$ completeness of permanent.
Given a CNF formula $\phi$ on $n$ variables, they construct
matrix $A$ such that:
$$perm(A)=4^{3m} \#SAT(\phi)$$
...
- 25.4k
2
votes
0
answers
192
views
relationship of max-sat and min-cut in theory and practice [closed]
I have been using MAX-SAT solver to obtain the exact ground state of ising spin glass model:
For 1D periodic model, for systems with 50 binary variables and interaction range of 15th nearest ...
- 867
6
votes
0
answers
154
views
Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph
According to a conjecture:
Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common.
Equivalent statement here
Main question:
...
- 25.4k
10
votes
1
answer
675
views
How hard is Heyting satisfiability, i.e. the constructive version of SAT? In particular, is 2-HSAT NL-complete or is it harder?
First of all, is it clear what I mean by $k$-HSAT?
I'm assuming that for $k>2$, $k$-HSAT is NP-complete, but the details of the reductions between $k$-HSAT and $k$-SAT aren't obvious to me.
I'm ...
- 457
18
votes
7
answers
3k
views
SAT and Arithmetic Geometry
This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note ...
- 1,368
1
vote
0
answers
89
views
Deciding / Approximating Parity of Small Depth Decision Trees
Let C be a circuit such that:
C: $\{0,1\}^n$ to $\{0,1\}$
the top most gate is a parity gate
all the inputs to the parity gate are small depth decision trees
there is a total of $2^{ log^k n}$ ...
- 45