# Conjunctive Normal Form SAT (Boolean Satisfiability)

(Redirected from CNF-SAT)

## Description

CNF-SAT restricts the boolean formula to conjunctive normal form (CNF), meaning it is the AND of ORs.

## Related Problems

Generalizations: SAT

Subproblem: All-Equal-SAT, k-SAT, XOR-SAT, Horn SAT, MaxSAT

## Parameters

$n$: number of variables

## Table of Algorithms

Currently no algorithms in our database for the given problem.

## Reductions TO Problem

Problem Implication Year Citation Reduction
k-OV If: to-time: $N^{(k-\epsilon)} poly(m)$ where $m$-dimensional vectors, $k$-OV, $N$ vectors per set
Then: from-time: ${2}^{(n-\epsilon')} \poly(m)$ where $\epsilon' = \epsilon/k > {0}$, $n$ variables, $m$ clauses
Frechet Distance If: to-time: $O({2}^{({2}-\epsilon)}$ for any $\epsilon > {0}$
Then: from-time: $O({2}^{({1}-\delta/{2})N}$ where $N$ is s.t there are $n=\tilde{O}({2}^{N/2})$ vertices on each curve
Local Alignment if: to-time: $N^{2-\epsilon}$ for some $\epsilon > {0}$ on two binary strings of length $N$
then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$
Longest Common Substring with don't cares if: to-time: $N^{2-\epsilon}$ for some $\epsilon > {0}$
then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$
Multiple Local Alignment if: to-time: $N^{k-\epsilon}$ for some $\epsilon > {0}$ on $k$ binary strings of length $n$ with $k$-wise scoring
then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$
Approximate Diameter if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$ for a $({3}/{2} - \epsilon)$-approximation
then: from-time: $O*(({2}-\delta)^n)$ for constant $\delta > {0}$
Positive Betweenness Centrality if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$
then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$
2015 https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Theorem 4.3 link
Approximate Betweenness Centrality if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$
then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$
2015 https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Corollary 4.2 link
Approximate Reach Centrality if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$
then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$
2015 https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Corollary 4.2 link
Approximate Reach Centrality if: to-time: $O(m^{2-\epsilon})$
then: from-time: $O*({2}^{({1}-\epsilon/{2})n})$
2015 https://epubs.siam.org/doi/10.1137/1.9781611973730.112, Theorem 4.4 link
#SSR if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing
then: SETH is false
SC2 if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing
then: SETH is false
Dynamic MaxSCC if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing
then: SETH is false
Dynamic Connected Subgraph if: to-time: $O(m^{1-\epsilon})$ amrotized update and query times on sparse graphs, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing
then: SETH is false
Dynamic 4/3-Diameter if: to-time: $O(m^{2-\epsilon})$ amrotized update and query times, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing
then: SETH is false
Dynamic ST-Reach if: to-time: $O(m^{2-\epsilon})$ amrotized update and query times, for any $\epsilon > {0}$, even after arbitrarily long polynomial time preprocessing
then: SETH is false
then: there is no algorithm for solving incremental (or decremental) st-max-flow on a weighted and directed graph with $n$ nodes and $\tilde{O}(n)$ edges with amortized time $O(m^{1-\epsilon})$ per operation for any $\epsilon > {0}$
then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$
then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$
then: let $\epsilon > {0}$, $t \in \mathbb{N}$, there exists no algorithm for target with preprocessing time $O(n^t)$, update time $u(n)$ and query time $q(n)$, such that $max\{u(n),q(n)\}=O(n^{1-\epsilon})$ with constant sensitivity $K(\epsilon,t)$