Yesterday morning the subject of P vs NP was discussed on BBC Radio 4's In Our Time.
"Melvyn Bragg and guests discuss the problem of P versus NP, which has a bearing on online security. There is a $1,000,000 prize on offer from the Clay Mathematical Institute for the first person to come up with a complete solution. At its heart is the question "are there problems for which the answers can be checked by computers, but not found in a reasonable time?" If the answer to that is yes, then P does not equal NP. ..."
You might like to listen to the programme. It is entertaining to hear the experts guests, including Tim Gowers of DPMMS, struggle to explain the mathematical concepts of algorithm, P, NP and complexity to layman Melvyn Bragg. Tim suggests one should think of P=practical and NP=not practical. Leslie Ann Goldberg explains the problem of finding a maximal matching, but does not go as far as explaining a polynomial time algorithm. Tim talks of NP-complete problems and calls it "a miracle, not at all obvious", that there is a class of difficult problems that are all equally difficult.
"Melvyn Bragg and guests discuss the problem of P versus NP, which has a bearing on online security. There is a $1,000,000 prize on offer from the Clay Mathematical Institute for the first person to come up with a complete solution. At its heart is the question "are there problems for which the answers can be checked by computers, but not found in a reasonable time?" If the answer to that is yes, then P does not equal NP. ..."
You might like to listen to the programme. It is entertaining to hear the experts guests, including Tim Gowers of DPMMS, struggle to explain the mathematical concepts of algorithm, P, NP and complexity to layman Melvyn Bragg. Tim suggests one should think of P=practical and NP=not practical. Leslie Ann Goldberg explains the problem of finding a maximal matching, but does not go as far as explaining a polynomial time algorithm. Tim talks of NP-complete problems and calls it "a miracle, not at all obvious", that there is a class of difficult problems that are all equally difficult.
Logging you in...
Frank · 486 weeks ago
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}$.
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}$.
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.
You could see more on (version 3)...
https://drive.google.com/file/d/0B3yzKiZO_NmWZ1M1...
Best Regards,
Frank.