Dense Complete Set For NP

EasyChair Preprint 6893, version 2

Abstract

A 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{NP--complete}$ problem that belongs to $DENSE(m)$ for every possible value of $0 <  m \leq 1$.

Keyphrases: Complement Language, completeness, complexity classes, polynomial time, sparse

@booklet{EasyChair:6893,
  author    = {Frank Vega},
  title     = {Dense Complete Set For NP},
  howpublished = {EasyChair Preprint 6893},
  year      = {EasyChair, 2021}}