Download PDFOpen PDF in browser

Dense Complete Set For NP

EasyChair Preprint no. 6893, version 2

Versions: 12history
8 pagesDate: October 21, 2021

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

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@Booklet{EasyChair:6893,
  author = {Frank Vega},
  title = {Dense Complete Set For NP},
  howpublished = {EasyChair Preprint no. 6893},

  year = {EasyChair, 2021}}
Download PDFOpen PDF in browser