The P versus NP ProblemReportar como inadecuado

The P versus NP Problem - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Datys

Abstract : The $P$ versus $NP$ problem has become in one of the most interesting and crucial questions for many fields such as computer science, mathematics, biology and others. This outstanding problem consists in knowing the answer of the following incognita: Is $P$ equal to $NP$? Many computer scientists have believed the most probable answer is $P eq NP$. A key reason for this belief is the possible solution of $P = NP$ would imply many startling results that are currently believed to be false. Besides $P$ and $NP$, another major complexity class is $coNP$. It is a known result if $P=NP$, then $NP=coNP$. Therefore, if we prove $P eq coNP$, then this would be sufficient to show $P eq NP$. Indeed, in this work we have demonstrated the existence of a $coNP$ problem that is not in $P$, and thus, $P eq coNP$. In this way, we show the belief of almost all computer scientists was a truly supposition.

Keywords : Turing machine coNP NP P

Autor: Frank Vega -



Documentos relacionados