Reports on an alleged solution to the P vs NP problem
Brian Park
A number of Korean media outlets have been reporting the claim by Kim
Yang-gon, mathematics professor at Chonbuk University, to have solved
the P vs NP problem. I have not been able to find reports of this in
languages other than Korean; for those of you who can read Korean, the
university's homepage has its own report on it:
I myself am very skeptical about this (why is Kim and the university
so eager to publicise a result that has yet to be checked by the
mathematical community?), but to summarise, the claim is that Kim has
found the solution, which will be published in the March 2004 issue of
the Journal of Applied Algebra and Discrete Structure (JAADS).
I have never heard of the journal, and searches on Google and
Harvard's library catalogue have yielded no results. This does not
necessarily mean that it is not a reputable journal and that the paper
will not go through a thorough refereeing system, but it certainly
does not inspire credibility. Moreover, the articles I've read betray
a complete ignorance of the mathematical concepts involved, and tend
to focus on the fact that the problem was one of Clay Mathematical
Institute's $1 million problems. And no report I've seen has any
mention of what Kim's solution was: P = NP or P != NP..
If a solution has been proposed to the P vs NP problem, it is indeed a
monumental achievement, but for the reasons I've mentioned, I think
the claim is entirely too fishy. If anyone has any information on the
alleged solution (approach, or even whether it was P = NP or P != NP),
then it would be appreciated.
Thanks,
Brian
LIHM Hwasop
I am a journalist at Yonhap News Agency, South Korea's mainstay wire
service, which happened to be the first news organization to file a
news report on Prof. Kim's claim.
I am not the story's author; it was written by another guy at a
regional Yonhap office near Chonbuk Univ.
However, since I became personally and professionally (I mean, in my
capacity as a journalist) interested in the issue, I decided to do
some fact-finding myself.
I managed to contact Prof. Kim through his mobile phone and he told
me:
1) he and his co-authors have established the inequality of P and NP.
(This vital piece of information was conspicuously absent from all
local media's articles on his claim so far.)
2) their paper has been accepted by the Journal of Applied Algebra and
Discrete Structure (JAADS) and will be published on its March 2004
issue.
3) they have found a construction for a certain class of NP problems
which are non-P.
I had a bunch of questions bubbling in my mind during the conversation
(who wouldn't?), but I thought a five-minute cell-phone talk was not
an appropriate occasion to risk offending him with more questions.
(Perhaps later...)
By the way, he is listed as a co-author in a preprint titled "Linear
Algebra, Lie Algebra and their applications to $P$ versus $NP$", which
is available at
http://www.mathpreprints.com/math/Preprint/shuanhongwang/20030424/2/?message%5Fid=0&display%5Fmessage=1&include%5Fform=#discussion
.
I don't know wheter this is a draft of the very paper submitted to the
JAADS, but its abstract explicitly claims relevance to the P vs NP
problem:
"Let $L$ be any $B_l$-type Lie algebra with $l\geq 2$ over an
algebraically closed field $F$ of characteristic $p>5$. Let $V$ be an
irreducible $L$-module corresponding to some points and let $\rho :
u(L)\lr End_F(V)$ be its corresponding representation. In this paper,
in order to prove that the equality about the $P$ versus $NP$ problem
out of the $7$ Clay problems [Ja] does not hold, the Kernel ${\frak
m}=Ker \rho $ of $\rho $ and the coset of $u(L)/{\frak m}\cong
End_F(V)$ will be investigated. Furthermore, given a particular
element $x$ of $u(L)$, we consider the expression formulae of $x$ in
the cosets of $u(L)/{\frak m}$. The expression gives rise to a
nonhomogeneous system of linear equations, and this system has an
algorithm by the Crammer's formula. We consider a counting problem
asking whether a given particular element $x$ of $u(L)$ belongs to a
coset of the form $\phi (S'_i)+{\frak m}$ and how many coefficients
are there in $e\in {\frak m}$ modulo $\sum u(L)(x_i^p-x_i^{[p]})$
having their absolute values equal to $v(x)$."
I don't think I'm entitled to my own judgement on his efforts at this
stage, but the circumstances certainly don't inspire credibility, as
you have pointed out.
Regards,
LIHM Hwasop
Brian Park <ilma...@hanmail.net> wrote in message news:<malwk9zq6mkr@legacy>...
Sterten
Doesn't sound, as if he really claims to have solved
P=?NP.
Dear respectable who and who;
I am so busy that I may only say that many many SCI papers are wrong referring
to our paper (A remark on Lie algebra and its module) at
http://www.mathpreprints.com
Please don't speak ill of the wrong authors.Happy new year to all of you.
Best,
Kim
tc...@lsa.umich.edu
>the Journal of Applied Algebra and Discrete Structure (JAADS).
>I have never heard of the journal, and searches on Google and
>Harvard's library catalogue have yielded no results.
I don't know this journal either, but Zentralblatt does, and seems to
indicate that volume 1 was published in 2003. But the website that
Zentralblatt and Google point to seems to be, as you hint above, dead.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
tc...@lsa.umich.edu
>I don't know this journal either, but Zentralblatt does, and seems to
>indicate that volume 1 was published in 2003. But the website that
>Zentralblatt and Google point to seems to be, as you hint above, dead.
This seems to have been a temporary problem. I just checked again and
the website seems to be back up.
http://business.vsnl.com/sasip/JAADS_MAIN.html
MathSciNet also knows this journal and some of the reviews are already
available.
tc...@lsa.umich.edu
Nathan Penton <npe...@hotmail.com> wrote:
>Has anybody with the relevant knowledge had a chance to look at that
>preprint somebody posted the link to? At a quick glance, it looks
>like a serious attempt.
Here is my understanding of the structure of the argument. The alleged
member of NP\P asks for the solution of a system of linear equations,
some of whose coefficients are "nondeterministic" in that their values
are allowed to range over certain sets. The argument is that (1) the
problem is in NP because the sets of permissible values of the coefficients
are small enough, and (2) the problem is not in P because in order to be in
P the solubility of the system should depend only on the "deterministic"
coefficients, and it does not.
It is possible that I have misunderstood the argument, because there
are portions of the paper that I do not follow. If the above sketch is
essentially correct, though, then part (2) does not come anywhere near
proving that the problem is not in P.
V.Z.Nuri
early may 2003. we have a little bit of commentary on it
from some experts. here is my pointer msg to some info.
http://groups.yahoo.com/group/theory-edge/message/9083
I encourage further comment at the theory-edge yahoo group:
http://groups.yahoo.com/group/theory-edge/
my personal nanosecond opinion: some of the theory in the paper
is relevant to P!=NP & very imaginative, but very unlikely to
have actually proven P!=NP. its a very nonstandard/unconventional
approach to the problem given the existing theoretical framework
behind it.
it annoys me that the authors do not seem to have claimed anywhere
openly that they have proven P!=NP, its not in the abstract or title
of the article, or the introduction (as I recall from reading a long
time ago). however it does seem to be claimed buried deep in
the paper.
I would like an open statement by all 3 authors, in english,
as to whether they think they have proven P!=NP. based on g.sterten's
post of the kim email & other aspects, such as going to the press to
publicize their work without anyone endorsing it yet, they seem to be playing
coy or evasive or something-- one of the few sins in mathematical research.
Brian Park <ilma...@hanmail.net> wrote in message news:<malwk9zq6mkr@legacy>...
Chan-Ho Suh
<vzn...@yahoo.com> wrote:
> I would like an open statement by all 3 authors, in english,
> as to whether they think they have proven P!=NP. based on g.sterten's
> post of the kim email & other aspects, such as going to the press to
> publicize their work without anyone endorsing it yet, they seem to be playing
> coy or evasive or something-- one of the few sins in mathematical research.
What evidence do you have that they went to the press first? The media
can be very aggressive in following leads, and strange as it may seem,
nowadays solving a famous math problem can be a hot story.
An open statement would be nice, but I doubt we'll get one anytime
soon. After all, their paper is supposed to be published in the near
future. They may appear evasive to you, but I'm sure they are busy and
have better things to do than enlighten sci.math.research readers.
Clementia99
1. Professor Yang-gon Kim (55) has said :
"my paper has been rejected by two US Journals (Perhaps SCI) and
by another SCI Journal of China"...
So
2.He has described Mathematical Society as
"Conservative"
3. Two Anonymous Korean Mathematicians have said
"It is exaggerated"...
"He doesn't understand basic concept of P/NP"
4. Preprint (mathpreprints.com)is the last version of paper.
If JAADS(?) publishes paper, though, then it is just the preprint of
mathpreprints.com (Nothing to be changed)
.......
** My Opinion : What's going on ????
** The Original article :
(http://news.naver.com/news_read.php?oldid=2004010500003082097, KOREAN)
(You can see the picture of him)
tc...@lsa.umich.edu
Clementia99 <cleme...@hanmail.net> wrote:
>3. Two Anonymous Korean Mathematicians have said
>"It is exaggerated"...
>"He doesn't understand basic concept of P/NP"
>** My Opinion : What's going on ????
If you want to try to read the paper and understand something of what
is going on, my recommendation is this. Don't be frightened by the Lie
theory (P-B-W theorem, Casimir operator, etc.). Turn directly to the last
two pages of the paper, where the alleged member of NP\P is described,
and it is argued firstly that it is in NP, and secondly that it is not
in P. Naturally, these arguments appeal to earlier portions of the paper,
with all the scary Lie theory. However, it is fairly clear where the
high-powered Lie theory is appealed to: It is used to define a certain
system of linear equations, whose coefficients are "nondeterministic"
(i.e., their values can range over a certain set), to show that the set of
values of the nondeterministic coefficients is small enough to allow the
system to be solved by a nondeterministic polynomial-time Turing machine,
and to show that the solution of the system depends on the values chosen
for the nondeterministic coefficients. ("Nondeterministic coefficients"
is my term, not the authors', but if you look at their paper, you will
see what I am referring to.) The authors are obviously experts in Lie
theory, so I am willing to grant all the above without needing to check
their arguments in detail.
However, to conclude that solving the system is not in P, one needs
more than this; in fact, here is the whole crux of the P = NP problem.
Yet on this point, the authors are cryptic, saying only something to the
effect that for the problem to be in P, it has to depend only on the
deterministic parts of the system, not on the nondeterministic parts
(which they call "random"). No appeal seems to be made at this point to
the heavy machinery earlier in the paper, even though this is exactly
where you would expect heavy machinery to be needed. So either the
authors misunderstand what is really needed to show that a problem is
not in P, or they are somehow appealing to some heavy machinery at this
point but in an obscure and cryptic manner. Not being completely sure
which is the case, even though I have some knowledge of Lie theory and
can follow at least the general outline of the earlier portions of the
paper, I cannot make a definitive judgment, but I bet that this is what
the evaluators you mentioned found to be the sticking point.
Clementia99
Prof. Kim yang-gon doesn't stop to contact media.......
In SBS (Korean Major Broadcasting System) Program "Seven Days" ,
Prof. Kim Yang-gon has said (with his own voice)
(2003/12/28)
"P means Class of existences of ordinary-organizing process"
"NP means Class of All Matters in the Universe"
"Then NP Includes P"
"In the set -NP but not P- , there are GOD and UFO"
"It is theoretically possible to prove existence of GOD and UFO"
"So I wanna to say -we can prove existence of GOD by mathematics"
This isn't Joke. It was his own voice.
Now I believe he doesn't understand P/NP Problem.
Ignat Soroko
contradict the recent result of da Costa and Doria:
N.C.A. da Costa, F.A. Doria, "Consequences of an exotic definition for
P=NP", Applied Mathematics and Computation, vol. 145 (2003), pp.
655-665.
These authors claim to have proven that "P!=NP" is unprovable in ZFC.
So no counterexample is possible within the "mainstream" mathematics.
Ignat Soroko,
Institute of Mathematics,
National Academy of Sciences of Belarus,
Minsk, Belarus
Gerry Myerson
Ignat Soroko <Ignat....@islc.NOSPAM.org> wrote:
> If the alleged Kim Yang-gon's proof of P!=NP were true then it would
> contradict the recent result of da Costa and Doria:
>
> N.C.A. da Costa, F.A. Doria, "Consequences of an exotic definition for
> P=NP", Applied Mathematics and Computation, vol. 145 (2003), pp.
> 655-665.
>
> http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TY8-48V96KT-4&_user
> =10&_handle=W-WA-A-A-CD-MsSAYWA-UUW-AUZZDECDCY-CAUVUZWY-CD-U&_fmt=summary&_cov
> erDate=12%2F25%2F2003&_rdoc=40&_orig=browse&_srch=%23toc%235612%232003%2399854
> 9997%23447579!&_cdi=5612&view=c&_acct=C000050221&_version=1&_urlVersion=0&_use
> rid=10&md5=ed52ad6a2af365f78832855c42480679
>
> These authors claim to have proven that "P!=NP" is unprovable in ZFC.
> So no counterexample is possible within the "mainstream" mathematics.
A negative review by Ralf Schindler of the da Costa & Doria paper
can be found at
wwwmath.uni-muenster.de/math/inst/ logik/org/staff/rds/review.ps
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)