Wednesday, May 16, 2012

Yet Another P vs. NP Proof

From the Saudi Gazette we read about the truly astonishing work of Dr. Rafee Ebrahim Kamouna, who claims to have resolved the P vs. NP question.

“The paper has been on the site of Cornell University to conform its academic standards. This means the paper is of relevance and of interest to the scientific community."


No, it means he put it on the arxiv, a preprint archive that happens to be housed at Cornell.

"Dr. Kamouna is currently writing a book that will be entitled “Bi-Polarism Theory: The Death of Computer Science, The End of Mathematics, and The Birth of Logical Physics.”

... which we are all looking forward to read with breathless anticipation.

If this silliness isn't enough to satiate you, you can look at Gerhard Woeginger's page.

58 comments:

Sniffnoy said...

You forgot to mention which way he claims to have resolved it. Which also means you left out the silliest part -- the abstract doesn't mention P vs. NP, but instead claims that SAT isn't actually NP-complete!

...and then in the paper itself he then goes and claims P=NP. Which would imply all problems in NP are NP-complete, but I guess expecting that sort of consistency is just not reasonable.

Anonymous said...

I'm here with my true identity for any public disputation and the new papers based on lambda calculus are on my blog.

I hope you will not run away!

Rafee Kamouna.

FM said...

A great P vs NP paper is Barbosa's: http://arxiv.org/ftp/arxiv/papers/0907/0907.3965.pdf

The best are the dialogues with the imaginary enemies that try to refute the proofs :)

Anonymous said...

Dear Jeffrey Shallit,

You are labeling my work as: bad mathematics, crank mathematics and silliness, may I know what you found wrong with my results and why. I find Scott Aaronson in your blog roll who is an editor of ToC which recently reviewed my work. I refuted all their arguments. So, don't run away! ToC (Aaronson) claims I'm not aware that I'm claiming that ZFC is inconsistent! They beleive that paradox recognition is unsolvable. That is their only way to refute SAT is not NP-complete. Which side do you take?

Best,

Rafee Kamouna.

Jeffrey Shallit said...

My position is that you are clearly an unrecognized genius who deserves every possible recognition from you government, the world, and the universe.

Thousands of years from now, the euphonious name of Rafee Ebrahim Kamouna will echo down the hallowed halls of mathematics.

Anonymous said...

So, you chose to be sarcastic because you have no objective argument against my work.

Rafee Kamouna.

Takis Konstantopoulos said...

If you look at the paper of R Kamouna, http://arxiv.org/pdf/0806.2947v8.pdf,
you get the impression, merely from the style of writing, that he hasn't written too many mathematical papers.

What is interesting is not so much the content of the paper, but the reason why it is written. I am talking about psychology: what makes certain people firmly believe they have the answer to some hard questions and, regardless of negative messages, failed attempts, etc., they insist in publishing (=publicizing) their "results".

The funniest part of his paper is the appendix (?) titled "A Spatio-Temporal Bi-Polar Disorder
Quantum Theory of Gravity
A Fuzzy Logic Programming Reconciliation". Sounds like material for a new edition of the Sokal & Bricmont classic.

A commentator said...

From the article:

"Days will either prove that Dr. Rafee Kamouna is no less than Albert Einstein or just like many other scientists who failed in their pursuit to prove their point."


This journalist seems determined not to be mealy-mouthed in his pursuit of journalistic fairness.

Jeffrey Shallit said...

Rafee:

What could I possibly say to detract from the evident merit of your paper?

Anonymous said...

You are following a fuzzy logic programming paper which has been superseded by 3 lambda calculus papers. The FLP paper was reviewed by JACM on the grounds:"A Turing machine cannot diagonalize against itself as the author claims...". The proof is my 2009 paper:"P=NP iff P!=NP, A Turing Machine that Diagonalizes Against Itslef", which is still being reviewed. If you are serious, you can read those papers on my blog and try to refute them which is impossible.

Best,

Rafee Kamouna.

Jeffrey Shallit said...

But Rafee, if it is "impossible", then I clearly cannot do it! Are you trying to suggest yet another paradox in your clever but waggish style?

Anonymous said...

In one paper, it is proved that SAT is both NP-complete and not NP-complete. In another, there is a language L in NP iff L not in NP. Those proofs are still being reviewed till the moment. If you input a paradox to a Turing machine, it constitutes a counter-example to NP-completeness after re-visiting Cook's proof of SAT being NP-complete.

Best,

Rafee Kamouna.

Jeffrey Shallit said...

I think we should bypass the referee process entirely and simply crown Mr. Kamouna king of the world.

Anonymous said...

Your sarcastic position just reveals that you are incomptent to discuss this.

Rafee Kamouna,

Jeffrey Shallit said...

Ah, but I know how to spell "incompetent"! Is that a paradox?

Anonymous said...

You are incompetent, and you know how to spell it, then that's your best.

Miranda said...

This is what I love about this blog!

Anonymous said...

I think we should bypass the referee process entirely and simply crown Mr. Kamouna king of the world.

Ben Stein should make a movie about him first.

Anonymous said...

I proved that SAT is both NP-complete (syntax) and not NP-complete (semantics) and that there exists L:L is in NP iff L is not in NP, can you refute any of these results?

Jeffrey Shallit said...

But Rafee, you've already said that refutation of your results is impossible. Therefore if I produce a refutation, you get another contradiction! You have too many contradictions already -- I don't think you need any more.

Anonymous said...

Yes, to refute my proofs, you have to refute yours. So, try. Any referee claims that paradox recognition is unsolvable, while it is trivial to solve. Check referee report on my blog.

Anonymous said...

Jeff,

It is clear that the schoold kids are more competent that you to discuss this. see: http://apps.topcoder.com/forums/?module=Thread&threadID=745115&start=0&mc=299

Best,

Rafee Kamouna.

Jeffrey Shallit said...

I agree entirely, Rafee! "Schoold kids" are exactly the right referees for your paper. Good show!

Anonymous said...

Be objective. there are 4 referees for the ToC journal where none of them superseded the school kids. Be objective: mention a specific issue.

Best,

Rafee Kamouna.

Jeffrey Shallit said...

What issue would you like to discuss? School busing, abortion, raising the retirement age? Please be specific.

Anonymous said...

You're sarcastic. If you were competent you would have demonstrated any flaw in my proofs. You are the one who posted about me while you cannot refute my results.

Jeffrey Shallit said...

But your results are impossible to refute -- you said so yourself! And yet you are angry because I cannot refute them!

This is a paradox of the highest order and clearly deserves your attention.

Anonymous said...

The ToC journal said that paradox recognition is an unsolvable problem, what so you think? I know you are incompetent to answer.

Jeffrey Shallit said...

Since I am incompetent to answer, any answer would not be trustworthy - am I right? So hoping to know my answer suggests a willingness to rely on untrustworthy sources. That seems like a paradox to me! Maybe the extremely wise Rafee Kamouna can help resolve it.

Anonymous said...

My proofs depend on CS undergraduate material only, do you cover that or....?

Jeffrey Shallit said...

You must be kidding. At Waterloo, all of the curriculum is devoted to studying Kamouna Theory. Why, we hosted the First International Conference on Mathematics is Inconsistent! If you were really Rafee Kamouna, you would have known that. I think you must be an imposter.

Anonymous said...

So, you covered CS undergraduate, great!

Rafee Kamouna said...

See my presentation at the Centre National de la Recherche Scientifique:

http://www.4shared.com/office/IezDgtsi/P_vs_NP_-_Presentation_4.html

Exposing 70 years of illusion!

Best,

Rafee Kamouna.

Jeffrey Shallit said...

Thanks, Rafee. I am writing a book on mathematical crackpots, and this will be helpful.

Rafee Kamouna said...

So, you regard the CNRS, which is on top of all French universities as crackpots? And after all these months you cannot make any objective argument against my work.

Best,

Rafee Kamouna.

Jeffrey Shallit said...

And after all these months you cannot make any objective argument against my work.

How could I? You have already told me many times it is irrefutable. Therefore, it is clearly a waste of time to attempt to do so.

Uli Fahrenberg said...

"Rafee Kamouna's work is refutable iff it is irrefutable."

Anonymous said...

Check my recent presentation at CNRS-Paris here:

http://kamouna.wordpress.com/

Check my posts here:

https://rjlipton.wordpress.com/2012/12/21/what-would-be-left-if/#comment-30369

I hope that you would comment constructively.

Best,

Rafee Kamouna.

Jeffrey Shallit said...

Rafee:

We are always amused by your waggish sense of humor. Your satire on a real academic paper is delightful and inspiring. Jon Stewart and Stephen Colbert have nothing on you!

Anonymous said...

The new paper:"The P versus NP Problem is Wrong:P=NP iff P!=NP" was recently submitted to JACM. It is available for download here: http://kamouna.wordpress.com.

Best,
Rafee Kamouna.

Jeffrey Shallit said...

And it has as much chance of being accepted there as a dog turd. Congrats, Rafee!

Anonymous said...

Luca Trevisan rejected my JACM 2011 submission in 2 weeks without review. On 20th June 2013, I submitted a new paper with a letter to him and the editor-in-chief Victor Vianu. After 10 days, the paper status became:"Waiting for Referee Selection" which is its status till now. This means Luca Trevisan was unable to refute my 2013 paper as he did in 2011. Boaz Barak is the associate editor handling my submission after Laszlo Babai's rejection of my 2010 two papers.

1. Luca proved to me that the Kleene-Rosser paradox must be undefined, hence uncdecidable.

2. I proved to him it is defined iff it is undefined. Hence, it is decidable iff it is undecidable over both the lambda calculus and Turing machines.

Best,

Rafee.

Anonymous said...

It is currently being discussed at the Foundations of Mathematics mailing list. This is an email that I have just received:
===============================
I skimmed through your exciting paper.
Do you, personally, believe that you have resolved the P vs. NP problem in it's intended meaning,(and you are going to win 1milion$)
or that contrary to this, there is a caveat, as it must seem to a novice, to that formulation in the lambda calculus?

Jeffrey Shallit said...

Let's have a friendly wager, o great one! If your "paper" is published in J. ACM within two years (that is, a paper by you, with the same title, on the same subject), I pay you $1000. If it is not published, you pay me $500.

Deal?

Anonymous said...

I do agree.

Anonymous said...

Because I'm quite sure I'm the winner and you are the loser.

Best,

Rafee Kamouna.

Anonymous said...

And the discussion goes on:
=================================
Dear Rafee
I believe that I can add some important consequence to your paper.

There cannot be a polynomial TM solving SAT which would yield P=NP, which is impossible by your paper.
==============================================================
My paper did not claim that this is impossible. On the contrary my proofs show that both sides of the conjecture is provable. One can have two correct proofs, one for P=NP, another for P!=NP, provided by the same person, or by two different persons perhaps at different times.
==============================================================
P=NP says that *there is* such a TM, not that we can *prove* about it that it is such (polynomially bounded and correctly solving SAT problem)
But also we cannot prove *formally* that there is no such a TM.
==============================================================
Again, a correct proof of P=NP can never rule out a later proof of P!=NP and vice versa. The same holds for the Riemann hypothesis and any other conjecture/theorem.
==============================================================
As a result, it is the case that P!=NP is true, but we cannot formally prove it.
==============================================================
I proved both P=NP and P!=NP, hence mathematics is inconsistent. Since it is mathematics, it is about theory. If you want to switch to computer science, so here is not only mathematics where inconsistency is possible, but also PHYSICS, as computers are Boolean machines. No computer can print something if and only if it does not print it. No such inconsistency can be attained in the realm of physics, unlike the realms of logic, language and mathematics. So, in practice, anybody at anytime can devise a polynomial-time algorithm for SAT that works correctly for a particular experiment in a typical situation/instance. No proof of either termination or correctness of such an algorithm is meaningful. After proving mathematics is inconsistent, both proofs and disproofs of all conjectures and/or theorems are possible.
However, his claims of Polynomial-time SAT solvability would only be supported by experimental evidence like exhaustive testing of the algorithm.
==============================================================
The same phenomenon occurs with Godel's sentence Con(PA): it is true but formally unprovable.
==============================================================
Godel's results can be stated in relation to Hilbert second problem as:"A system can prove its own consistency if and only if it is inconsistent". Godel's results are:"If PA is consistent, then PA is incomplete". Now all theories are inconsistent, then Godel's incompleteness theorems are redundant as its antecedant is no longer true as he assumed it to be.

So, it is not the same phenomenon at all. The P vs NP/SAT issue is a theory vs. practice conflicting situation where contradictions can be obtained in theory but not in pracitce, unless you believe in parapsychology which is pseudo-science. But if the language of science (mathematics) is inconsistent, so science is no better than pseudo-science. This is a serious social/public consequence of any proof of the inconsistency of mathematics. What do you think?
==============================================================

Jeffrey Shallit said...

Rafee:

Great! (Although in my experience, my chance of getting a payment once you lose in vanishingly small.)

Anonymous said...

Dear Rafee

who would not be interested when (s)he sees a solution of a claymilenium open problem :-)
So is it correct to say that you have found a finistic formal proof of a contradiction in ZFC?
If so, can this be further improved to find a concrete sentence phi such that phi and not phi are both derivable from ZFC
together with theirs formal proofs in ZFC?

==============================================================
Thanks a lot for your message and interest. The concrete sentence phi is there in the paper. There is a result:"SAT is NP-complete iff SAT is (NOT) NP-complete". Re-read it. As you may clearly see, the proof is a one step argument. Just simply consider stating Cook's theorem in the case of a paradoxical input, the contradiction is established. As I said in the paper, all the proofs are not in the form of:"A => B => C => D etc", rather it is a one step argument. The Kleene-Rosser paradox was historically misunderstood as an example of an undefined function, hence undecidable. Rather, it is proved that it is decidable iff it is undecidable. This is because it is defined iff it is undefined, rather than just undefined. This paradox is transformed from the lambda-calculus to Turing machines via a simple diagonalization argument.

I would like to emphasize to you that diagonalization is not about mathematics at all. It is about physics. You actually perform an experiement, which is a counting one. It is like counting on your fingers, but you don't have an infinite number of fingers. It is a counting experiment to logically reason about an infinite sequence. It establishes a missing element in the sequence via arguing:"It is missing, because if it is not missing, a contradiction is derived".

How can anyone ask me to formalize both the lambda-calculus & the Turing machine proofs in a formal system. I would tell them how the proof of the existence of uncomputable functions can be formalized in any standard proof system. If one reviews, e.g. Arora & Barak, the diagonalization table is drawn and the result follows from negating the diagonal. No definitions, no theorems nor proofs. No ZFC nor PA. Just a logically compelling counting argument that's simple but robust.


Best,
Rafee.

Anonymous said...

Your chance of winning is less than zero. If you know with whom I'm corresponding. He comes from a country that teaches differential and integral calculus at primary schools.

Best,

Rafee.

Anonymous said...

The Church-Rosser Argument

A Function which is TOTAL if and only if NOT TOTAL

Definition: The Kleene-Rosser paradox reads: ``The $\lambda$-calculus expression consisting of the $\lambda$ term (k) which may not be applied to itself, when combined with itself, negates itself (kk)".
$$k\ =\ (\lambda x.\neg (xx))$$
$$kk\ =\ (\lambda x.\neg (xx)) k\ =\ \neg (kk)$$

k_i may be applied to $k_i\ \equiv\ k_i$ may not be applied to k_i

k_ik_i is total $\Longleftrightarrow\ k_ik_i$ is not total

======================================================
Proofs:
======================================================
Theorem 2.1: Established Belief: The Church-Rosser Argument
\forall i, k_ik_i = \neg k_ik_i is undefined

It is the $\lambda$-calculus corresponding counter-part for the Turing machine halting problem. Hence, it is undecidable.

Proof: The proof is by contradiction. After universal quantification over $\Lambda$, a counter-example is constructed:

1. If all functions defined by $\lambda$-expressions in $\Lambda$ were total, then one would have [k_ik_i = \neg k_ik_i] for the diagonal function $k_i$.

2. This means that some functions, including the diagonal function, are not total.

3. Since one does not have k_ik_i = \neg k_ik_i, instead one has [k_ik_i=\neg k_ik_i] is undefined.

4. It is the $\lambda$-calculus corresponding counter-part for the Turing machine halting problem.
==========================================================================
Refutation:
A counter-example is constructed after universal quantification. Since the constructed counter-example (for established belief) is a contradictory expression, so if the universal quantification used an opposite property, still the same counter-example is derived.

Theorem: Refutation of Established Belief:
\forall i k_ik_i = \neg k_ik_i is defined

Proof: The proof is by contradiction. After universal quantification over $\Lambda$, a counter-example is constructed:

1. If all functions defined by $\lambda$-expressions in $\Lambda$ were not total, then one would have:

2. k_i may not be applied to k_i.

3. (2) \equiv k_i may be applied to k_i.

4. Implies: [k_ik_i = \neg k_ik_i]$ for the diagonal function k_i.

5. Implies: one has [k_ik_i = \neg k_ik_i]. Contradiction derived, (1) must be negated.

6. $\exists$ some functions, including the diagonal function, that are total.

7. The diagonal function [k_ik_i = \neg k_ik_i] is defined.

The Kleene-Rosser paradox can be articulated as in the following re-formulations:
[k_ik_i =\neg\ k_ik_i] is defined\ if and only if [k_ik_i=\neg\ k_ik_i] is undefined
[k_ik_i=\neg\ k_ik_i] is total\ if and only if [k_ik_i=\neg\ k_ik_i] is not total.
[k_ik_i=\neg\ k_ik_i] is decidable if and only if [k_ik_i=\neg k_ik_i]" is not undecidable.

================================================================================
Best,
Rafee Kamouna.



Jeffrey Shallit said...

Rafee:

I have a limited amount of patience for your incoherent babbling. Please make an effort to restrict your comments to one or two per week.

I am looking forward to my $500.

kamouna said...

Theorem: P=NP iff P!=NP.
The Kleene-Rosser paradox is a counter-example to NP-completeness.
================================================
Russell's Paradox: The set that contains all the sets that do not contain themselves. If you ask the question:"Does it contain itself?". The answer would be it contains itself iff it does not contain itself.

The Kleene-Rosser Paradox: Roughly, the function that may not be applied to itself, when combined with itself, it negates itself.

This function is a lambda expression as "k:= NOT (x x)" which reads: The meaning of k is: "x" may not be applied to "x". Then deriving "kk" results in the paradox:
kk= NOT kk
If you assume that this function is total, you derive a contradiction, then it is not total. Then, if you assume that it is not total, again, a contradiction is derived, then it is total. So, it is total iff it is not total. The Church-Rosser argument shows that this function is undefined. Here,
http://kamouna.wordpress.com/2013/08/16/all-mathematical-systems-are-inconsistent/
it has been shown as defined iff it is undefined and decidable iff it is undecidable, both on the lambda-calculus and Turing machines. Below is a proof sketch.

================================================
Step 1. Cook_Levin: For all w in L in NP,
M accepts w iff \exists A(w)=SAT.

Step 2. Assume M_KR Kleene-Rosser Paradox Recognizer Turing machine, then:
M_KR accepts w_KR iff e^-1(w_KR)= NOT e^-1(w_KR).

Step 3. Put M=M_KR and w=w_KR.
==> L.H.S. of (1) = L.H.S. of (2).
==> R.H.S. of (1) = R.H.S. of (2).
==> There is no SAT(w_KR).
==> L_KR={w_KR_i} is in NP and NOT NP-complete.
==> L_KR is a counter-example for NP-completeness.
==> SAT is (NOT) NP-complete.
==> SAT is NP-complete <==> SAT is (NOT) NP-complete,
Cook's proof is still correct despite the contradiction.
==> P=NP iff P!=NP.
================================================

best,
Rafee Kamouna.

Jeffrey Shallit said...

Fascinating drivel! Did your paper get rejected yet? I'm looking forward to my money.

kamouna said...

It will never get rejected. That's why Scott Aaronson doesn't allow the above proof at his blog.

Van you refute it? or can he?
the Theory of Computing Journal rejected on the grounds that KR is undecidable. I proved KR is decidable iff it is undecidable.

JACM rejected on the grounds that KR is undefined. I proved it is defined iff it is undefined. The decision took them 10 days only. The new paper is now 9-months pending.

Refute it, or tell me why Scott is banning me.

best,

Rafee Kamouna.

Jeffrey Shallit said...

Let's see, you already admit one good journal rejected your silly paper. But you claim rejection is impossible! I think that's yet another contradiction.

Get your checkbook ready, Rafee!

Joe Felsenstein said...

I do not know why you did not discover the truth, that P = NP, but only under particular conditions. Specifically, P = NP when either N=1 or P=0.

I expect lots of acclaim for this insight, which has escaped all computer scientists.

;-)

liav teichner said...

Less than a year remains for the bet to be settled.
Rafee, any progress?