Download PDFOpen PDF in browserDense Complete Set For NPEasyChair Preprint 6893, version 28 pages•Date: October 21, 2021AbstractA sparse language is a formal language such that the number of strings of length $n$ is bounded by a polynomial function of $n$. We create a class with the opposite definition, that is a class of languages that are dense instead of sparse. We define a dense language on $m$ as a formal language (a set of binary strings) where there exists a positive integer $n_{0}$ such that the counting of the number of strings of length $n \geq n_{0}$ in the language is greater than or equal to $2^{n  m}$ where $m$ is a real number and $0 < m \leq 1$. We call the complexity class of all dense languages on $m$ as $DENSE(m)$. We prove that there exists an $\textit{NPcomplete}$ problem that belongs to $DENSE(m)$ for every possible value of $0 < m \leq 1$. Keyphrases: Complement Language, completeness, complexity classes, polynomial time, sparse
