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.
Subscribe to:
Post Comments (Atom)
96 comments:
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.
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.
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 :)
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.
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.
So, you chose to be sarcastic because you have no objective argument against my work.
Rafee Kamouna.
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.
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.
Rafee:
What could I possibly say to detract from the evident merit of your paper?
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.
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?
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.
I think we should bypass the referee process entirely and simply crown Mr. Kamouna king of the world.
Your sarcastic position just reveals that you are incomptent to discuss this.
Rafee Kamouna,
Ah, but I know how to spell "incompetent"! Is that a paradox?
You are incompetent, and you know how to spell it, then that's your best.
This is what I love about this blog!
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.
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?
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.
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.
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.
I agree entirely, Rafee! "Schoold kids" are exactly the right referees for your paper. Good show!
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.
What issue would you like to discuss? School busing, abortion, raising the retirement age? Please be specific.
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.
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.
The ToC journal said that paradox recognition is an unsolvable problem, what so you think? I know you are incompetent to answer.
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.
My proofs depend on CS undergraduate material only, do you cover that or....?
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.
So, you covered CS undergraduate, great!
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.
Thanks, Rafee. I am writing a book on mathematical crackpots, and this will be helpful.
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.
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.
"Rafee Kamouna's work is refutable iff it is irrefutable."
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.
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!
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.
And it has as much chance of being accepted there as a dog turd. Congrats, Rafee!
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.
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?
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?
I do agree.
Because I'm quite sure I'm the winner and you are the loser.
Best,
Rafee Kamouna.
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?
==============================================================
Rafee:
Great! (Although in my experience, my chance of getting a payment once you lose in vanishingly small.)
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.
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.
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.
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.
Fascinating drivel! Did your paper get rejected yet? I'm looking forward to my money.
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.
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!
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.
;-)
Less than a year remains for the bet to be settled.
Rafee, any progress?
Yes, JACM rejeted based on out-of-scope.
best,
Rafee Kamouna.
Great!
When can I expect my check for $500? You can send it to
Jeffrey Shallit
School of Computer Science
University of Waterloo
Waterloo, ON N2L 3G1
Canada.
I'm looking forward to it!
Prove to me that the paper is not a computer science paper.
That was not the terms of our bet. I quote, "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."
Now if you want to wait for the full two years before paying, that would be reasonable.
But changing the terms of the bet is not. It is exactly what I expected, though.
Since this is what you expect, can you tell me the topic of the paper as perceived by JACM.
First, tell me whether you intend to pay up or not. A clear "Yes, I will pay" or "No, I intend not to pay" will suffice.
I now feel embarrassed for having published 2 papers on arxiv.org. After I uploaded, I grimace at the mistakes I made. Luckily, none that were fatal to the math. But, I had asserted more than I had proved.
Now, after reading some of THESE doozies, I don't think there's anything reputable about posting papers there.
I now feel embarrassed for having published 2 papers on arxiv.org. After I uploaded, I grimace at the mistakes I made. Luckily, none that were fatal to the math. But, I had asserted more than I had proved.
Now, after reading some of THESE doozies, I don't think there's anything reputable about posting papers there.
Ok. Now I feel embarrassed that I posted twice somehow, accidentally.
But, seriously - theorems such as Godel's and other theorems proving the impossibility of doing something, such as Matiysevich's resolution of Hilbert's 10th problem, make me very depressed & hopeless. And, I know, that there are other such "impossibility theorems" out there, that I have no idea how to formulate, since I have never taken a formal course in Turing machines & logic, that may (hopefully not) make my attempts to solve certain math problems a certain way impossible.
But, I wouldn't even know if I am working on such a problem.
Anybody else see the great news at http://vixra.org/combgt/?
"Best news. After over 30 years of debating, the debate is over. Yes, P is equal to NP."
(cough, ahem)
"The CMI Millennium Prize requirements have been satisfied."
Whew. I was afraid there for a moment that they hadn't been satisfied.
Oh, and, I may not be a robot, but apparently I'm as fire-able as one.
Don't ever think that I'm not paying you your $500. The 2013 JACM paper had the result:
SAT is NP-complete iff SAT is (NOT) NP-complete
Boaz Barak (after a complete year of refereeing) wrot to me that this result is in mathematical logic.
Obviously, it is not in complexity theory. What is your opinion.
What about you invite Stephen Cook and me for a Skype-CNN-televised PUBLIC DISPUTATION?!?!
best,
Rafee Kamouna.
Why on earth would I be interested in debating with any person who refuses to pay up? A person who makes a bet and refuses to pay is not an honorable person. Therefore such a person's word could not be considered reliable. Speaking hypothetically, of course.
The payment was subject to the JACM decision which said:
SAT is NP-complete iff SAT is (NOT) NP-complete
is a result in mathematical logic and not complexity theory.
best
Rafee Kamouna.
There were no conditions on the wager at all, other than your paper appearing.
Your paper did not appear.
Therefore, by the terms of our wager, you owe me $500.
You have not paid.
It's as simple as that.
Since you have no any technical comment, so you are not serious. Below is the (funny) review of another journal: They ask me for a proof of ALL mathematical problems; both in the affirmative and the negative.
===============================
Reviewers' comments:
There is no merit to this paper.
The author claims to have proved mathematics is inconsistent.
In particular the author claims to have proved SAT is NOT NP-complete.
Then the author has also proved NP is = P.
(In fact if, as the author claims to have proved, that
mathematics is inconsistent, then the author can prove everything,
including all the Millennium problems like the Riemann Hypothesis (and their negations!))
Hence, among other things, the author claims to have a provable
P-time algorithm for factoring. To take the claimed proof seriously,
the author should first produce some factorizations of the RSA challenge
problems that are available on line.
https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
Unless and until correct answers are obtained, no referee effort should
be wasted in helping the author to find the mistakes in the paper.
The paper should be rejected.
===============================================
best,
Rafee Kamouna.
Rafee, what do you call a person who makes a bet, loses, and refuses to pay in your native language?
You may not bet in Islam. Please re-check with others.
It is among non-allowable financial transactions.
Best,
Rafee Kamouna.
So then why did you bet?
I never bet. It is a sort of gambling. Yes, I offered a prize of one million dollar for whoever will refute Bi-Polarism Thery with its both sides:"Computer Science & Physics".
The relationship between syntax & semantics is Fuzzy Logic Programming is the same as between space & time in General Relativity.
The prize was declared at topcoder.com, thousands there know very well about it.
Eight years passed with failure to refute any claim; the prize was cancelled.
best,
Rafee Kamouna.
So when you said "I do agree" above you were lying?
agree about what?
Rafee.
You agreed to the wager above, when you said "I do agree" in your comment of August 17, 2013.
Were you lying then?
And are you really unable to do a text search on the page to find the words "I do agree"?
That was on the assumption of a sound technical discussion which never happened.
So, you engaged in wagering which is against your religion, and you agreed to a bet without conditions, which you then proceeded to lose, but refused to pay. Did I summarize the situation correctly?
Cook-Levin states that for every string w in any language L in NP, a SAT formula is derived.
Tell me what happens if the string w represents a paradox.
This is the question that is BANNED by many complexity theorists.
On the other hand, is paradox recognition possible or impossible?
This is the question that is BANNED by many computability theorists.
Please address these questions and be serious, nt funny.
Rafee.
First pay me what you owe me.
You're funny!
Why is it funny? If you had won the bet, you would have expected me to pay, right?
No, at all. Please answer the above questions and/or invite colleagues for that.
Too bad, because I expect you to pay if you wish to be considered as an honorable person.
It seems that you are in a financial crisis and you don't care about your own research.
I'm ready to confront you (as well as anyone) on the BBC.
All that verbiage, and still weaseling out of the bet!
I'm ready to pay you your $500 if you invite me for a cup of coffee at Waterloo. I shall pay all the travel expenses.
best,
Rafee Kamouna.
Why are you silent?
Rafee Kamouna.
There were no conditions on our bet. First, pay the $500. Then we'll talk.
You lost because the paper is being re-considered again.
There were no conditions about "reconsideration". Read the terms of the bet. You lost. You will pay up if you have integrity.
Given a number x and a set S of n positive integers, MINIMUM is the problem of deciding whether x is the minimum of S. We can easily obtain an upper bound of n comparisons: find the minimum in the set and check whether the result is equal to x. Is this the best we can do? Yes, since we can obtain a lower bound of (n - 1) comparisons for the problem of determining the minimum and another obligatory comparison for checking whether that minimum is equal to x. A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer i if and only if i is in S. Given a positive integer x and a Boolean circuit C, we define SUCCINCT-MINIMUM as the problem of deciding whether x is the minimum bit integer which accepts C as input. For certain kind of SUCCINCT-MINIMUM instances, the input (x, C) is exponentially more succinct than the cardinality of the set S that represents C. Since we prove that SUCCINCT-MINIMUM is at least as hard as MINIMUM in order to the cardinality of S, then we could not decide every instance of SUCCINCT-MINIMUM in polynomial time. If some instance (x, C) is not in SUCCINCT-MINIMUM, then it would exist a positive integer y such that y < x and C accepts the bit integer y. Since we can evaluate whether C accepts the bit integer y in polynomial time and we have that y is polynomially bounded by x, then we can confirm SUCCINCT-MINIMUM is in coNP. If any single coNP problem cannot be solved in polynomial time, then P is not equal to coNP. Certainly, P = NP implies P = coNP because P is closed under complement, and therefore, we can conclude P is not equal to NP.
You could read the details in:
http://vixra.org/pdf/1704.0335v1.pdf
P versus NP is considered one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by John Nash to the National Security Agency in 1955. Since that date, all efforts to find a proof for this huge problem have failed.
I show a solution to that problem as follows:
Given a number x and a set S of n positive integers, MINIMUM is the problem of deciding whether x is the minimum of S. We can easily obtain an upper bound of n comparisons: find the minimum in the set and check whether the result is equal to x. Is this the best we can do? Yes, since we can obtain a lower bound of (n - 1) comparisons for the problem of determining the minimum and another obligatory comparison for checking whether that minimum is equal to x. A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer i if and only if i is in S. Given a positive integer x and a Boolean circuit C, we define SUCCINCT-MINIMUM as the problem of deciding whether x is the minimum bit integer which accepts C as input. For certain kind of SUCCINCT-MINIMUM instances, the input (x, C) is exponentially more succinct than the cardinality of the set S that represents C. Since we prove that SUCCINCT-MINIMUM is at least as hard as MINIMUM in order to the cardinality of S, then we could not decide every instance of SUCCINCT-MINIMUM in polynomial time. If some instance (x, C) is not in SUCCINCT-MINIMUM, then it would exist a positive integer y such that y < x and C accepts the bit integer y. Since we can evaluate whether C accepts the bit integer y in polynomial time and we have that y is polynomially bounded by x, then we can confirm SUCCINCT-MINIMUM is in coNP. If any single coNP problem cannot be solved in polynomial time, then P is not equal to coNP. Certainly, P = NP implies P = coNP because P is closed under complement, and therefore, we can conclude P is not equal to NP.
You could read the details in the link below...
https://hal.archives-ouvertes.fr/hal-01509423/document
Post a Comment