tag:blogger.com,1999:blog-6768013380692425809.post1199850530541076916..comments2020-10-31T08:04:42.482-07:00Comments on WeakNet Labs: P vs. NP ProblemDouglas Berdeauxhttp://www.blogger.com/profile/16926757154611040708noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-6768013380692425809.post-61420245025879253952015-12-18T13:41:33.949-08:002015-12-18T13:41:33.949-08:00THE P VERSUS NP PROBLEM
We define an interesting ...THE P VERSUS NP PROBLEM<br /><br />We define an interesting problem called $MAS$. We show $MAS$ is actually a succinct version of the well known $\textit{NP--complete}$ problem $\textit{SUBSET--PRODUCT}$. When we accept or reject the succinct instances of $MAS$, then we are accepting or rejecting the equivalent and large instances of $\textit{SUBSET--PRODUCT}$. Moreover, we show $MAS \in \textit{NP--complete}$.<br /><br />In our proof we start assuming that $P = NP$. But, if $P = NP$, then $MAS$ and $\textit{SUBSET--PRODUCT}$ would be in $\textit{P--complete}$, because all currently known $\textit{NP--complete}$ are $\textit{NP--complete}$ under logarithmic-space reduction including our new problem $MAS$. A succinct version of a problem that is complete for $P$ can be shown not to lie in $P$, because it will be complete for $EXP$. Indeed, in Papadimitriou's book is proved the following statement: ``$NEXP$ and $EXP$ are nothing else but $P$ and $NP$ on exponentially more succinct input". Since $MAS$ is a succinct version of $\textit{SUBSET--PRODUCT}$ and $\textit{SUBSET--PRODUCT}$ would be in $\textit{P--complete}$, then we obtain that $MAS$ should be also in $\textit{EXP--complete}$.<br /><br />Since the classes $P$ and $EXP$ are closed under reductions, and $MAS$ is complete for both $P$ and $EXP$, then we could state that $P = EXP$. However, as result of Hierarchy Theorem the class $P$ cannot be equal to $EXP$. To sum up, we obtain a contradiction under the assumption that $P = NP$, and thus, we can claim that $P \neq NP$ as a direct consequence of the Reductio ad absurdum rule.<br /><br />You could see more on (version 3)...<br /><br />https://drive.google.com/file/d/0B3yzKiZO_NmWZ1M1MkNuYVBreXc/view?usp=sharing<br /><br />Best Regards,<br />Frank.Frankhttps://www.blogger.com/profile/15257641208909866601noreply@blogger.com