Slashdot Mirror
Does P = NP?
Morabbin writes: "A paper claiming to present a polynomial time algorithm for the minimal clique partition problem has been put up on Stas Busygin's Repository for Hard Problems Solving. It seems to be a genuine attempt (i.e. non-crackpot). Since the minimal clique partition problem is NP-hard, the existence of a polytime algorithm would imply that P = NP. The jury is still out." All right, I'm super skeptical, but its been 2 years since I messed with np complete, np hard, and all that stuff. But I do know enough to doubt it. Where are the CS grad students in the audience?
NP does not stand for NON polynomial, it stands for nondeterministic polynomial.
Every problem in P is in NP.
Decryption brute force by definition could not be accomplished in polytime; the problem is if you can always guess right in polytime, then it's a different story (essentially how a nondeterministic turing machine works).
</rant
As everyone else has pointed out, way too obvious. I mean, come on - divide by 0?? Not to mention the deliberate (sp.?) and shallow misunderstanding of the subject.
But, seeing as you changed the subject to phoney math, how about this:
1 = 1 (right?)
1 = 1 * 1
1 = -1 * -1
so:
1 * 1 = -1 * -1
now x = y => sqrt(x) = sqrt(y),
so:
sqrt( 1 * 1 ) = sqrt( -1 * -1 )
and as we all know, sqrt( x * x ) = x,
so:
1 = -1!
Much more satisfying - no divide by 0! Just the cavalier assumption that sqrt is a single valued function and some blythe disregard for the domain of the values discussed.
My intelligent way of solving traveling salesman involved slapping a regular grid on the area such that an average of seven stops were in each gridbox (cube, n-cube, . .). Use an identical basic plan, basic circle then across the diameter, with orthogonal distance from the paths determining which veered to pick up the odd stops. Start in one corner and work in one basic direction. It gives you a path in P time, that is moderately close to optimal. By virtue of the transformation it can work on all NP problems. Is it conventional? No. Is it algorithmic? No.
So long and thanks for all the fish . . . !!!
"Minimum clique partition" refers to the minimum number of complete subgraphs into which the subject graph can be partitioned, not the smallest subgraphs (which is trivial).
Floating face-down in a river of regret...and thoughts of you...
All algorithms that run on modern computers have runtimes that can be described in terms of polynomial functions. Some examples of these are:
... (Incidentally most sort algorithms are O(NLogN) in case you wanted an example...) Anyhow, I know my algorithm is O(NLogN) which means as N, or the size of the input, increases... my runtime increases according to this function.
:-)
N,N^2,LogN,NLogN,N^N
The "N" in all of these describes in some fashion the size of the input. Generally when one discusses algorithm speed, the terminology O(N) or O(logN) is used as opposed to just stating the polynomial. You should read "O(N)" as "Big-Oh of N" or "Order N". There is also a "little-oh of N" which describes lower limits on the algorithms runtime and there is "Omega of N" which is a waste of time.
Now you may be asking what is the f*ing point... I know I did in my sophomore year of Computer Science classes...
Basically the point is only apparent when dealing with difficult problems. Before you go and code a solution to a difficult problem, you want to ensure that you wont be wasting your time. So you formalize your algorithm into polynomial form. (This can be difficult...) You can then tell by the form of the polynomial just how long the algorithm will take to run as the size of the input increases. So, if I formalize my Algorithm to be O(NLogN)
In case you are wondering how the hell logarithms get into computer algorithms, its a by-product of recursion.
Back to the point. Any algorithm described as having the form O(x^N) is considered to be "NP" which stands for Non-Polynomial... which you can see is plainly the case. The "N" is in the exponent, and therefore the runtime grows exponentially, not polynomially.
Algorithms that have NP forms suck because they just take too damn long to with inputs above certain thresholds. NP alogorithms are grouped into two seperate groups that have differening properties. One is NP-complete, and the other is NP-hard. Lets leave it at: "NP-complete problems have better solutions that are more practical than NP hard problems". There are of course more formal definitions, but this should suffice for now.
Basically NP problems are some of the most infamous in computer science and were there polynomial solutions to these problems the world would be a better place. Some of these are: Minimum Spanning Trees, The Travelling Salesman Problem, Convex Hulls (Somebody check me on that one ???), and many more including decryption brute forcing and some of the problems that go with it such as large number factoring and prime-tests...
Some scientists believe that the set of NP-complete problems can all be mapped into polynomial algorithms, others do not. Some scientists believe that _some_ of the NP-complete problems can have a polynomial map and others don't and that therefore not all the algorithms that are considered to be NP complete actually are. Basically at this point the subject digresses into a bunch of academic hooey.
You should come away with this: There are some problems that people would like to solve that todays computers can't solve with practical input sizes in a million years. Computer Science has developed a formalism for working with these problems and it is of interest to some mathematically minded programmers to read about these things and play with the solutions. It helps programmers keep their minds sharp and usually helps us keep our own algorithms efficient.
I hope that I have sated your curiosity to some degree. I have glossed over and simplified some very complex subjects, partly because I would embarass myself and get thing s wrong if I went into more detail. I am a software engineer, not a theoretician. The difference is: theoreticians are smarter, but software engineers make more money.
Actually it is even more general than that. Any NP complete problem can be written as a special case of any other NP complete problem; this is why it is such a big deal to do NP in P time. Once someone finds an algorithm for a single NP problem, they have solved *ALL* NP problems in polynomial time.
This is also why proving an isomorphism proves x in {NP}.
Fscking Submit buttons is way too close to the "No Score +1 Bonus" check box!
--
--
E_NOSIG
Oh we're out here in the audience, but know better than to get involved with that stuff. I learned enough to get past my PhD comprehensives and will be happy to leave P/NP at that.
I take it that you're saying you don't believe in Turing's thesis. could you specify a bit more what you mean by "intelligent way" as opposed to "analytical way"? specifically, do you see this 'intelligent way' as being specifiable by a good old formal-language algorithm?
So the statement "A problem is said to be within the classof complexity P if ... Otherwise the problem is said to be in complexity class NP." is not strictly accurate.
True. Thanks.
:wq
Prof. Cook is a respected authority on complexity theory, so if he is doubtful about this paper, I'd take an extra large grain of salt with it...
Poll Mastah
It has been while since I did the complexity cource, and I have not read the complete paper, but I found a small mistake (but it might be a big one).
quote:The running time of the algorithm is equal to O(n6), where n is the number of graph vertices.
n should be the number of graph vertices and graph edges together (think of Turing Machines).
It's actually much simpler than that. If a solution H to the halting problem existed, it would fail to properly predict whether the following algorithm B:
- Given A as input, use H to determine if the program A halts on input A
- If A halts on A, go into an infinite loop, otherwise output 0 and halt
halts when given input B.In short, it doesn't just contradict years of math, it contradicts itself.
Basically, the issue is are there any problems (which have solutions at all) that can't be solved in, at worst, polynomial time? Ie, the time taken to solve for a "sample" of n is proportional to n^(some constant). I seem to recall that's it anyway.
TWW
"Encyclopedia" is to "Wikipedia" what "Library" is to "Some people at a bus stop"
If P=NP, you STILL HAVE TO FIND an efficient polynomial time algorithm for the problem! I suspect that working from one P-time solution to an NP-complete problem will only yield an algorithm with huge polynomial terms. The difficulty in finding such algorithms anyhow will surely mean that such a P-time algorithm will still be hard to improve upon...
John
John_Chalisque
If you could do NP in P time, it would probably be worth a lot more than a million dollars to you.
Yes, there are. To say that a problem is solvable in NP-time is equivalent to saying that its solution is verifiable in polynomial time, and that's not true for all problems. IIRC double-exponential-time problems tend to fall into this category.
There are problems that can be solved but not in any time bounded by O(2^(2^(2^(...^n)))), that is not exponential, double-exponential, triple-exponential, or anything like that. They're known as nonelementary problems (understatement of the year). I imagine those are always outside NP, but I don't have the references to hand at the moment.
as a non-cs guy, I find this discussion very interesting and informative. several people have done a good job explaining the difference between P, NP, and NP complete -- but all the definitions are based on a term that makes no sense to me at all 'polynomial time'. Can anyone help?
thanks.
sorry, my physics degree is only a BA...
I'm not sure (don't remember). The Halting Problem came to mind first. Anything that involves enumerating all possible solutions is solvable in polynomial time on a non-deterministic computer. Perhaps something where the cardinality of the solution space is aleph-one or above. Depends on a good definition of a non-deterministic computer (which, in my experience, has always had a degree of fuzziness).
Floating face-down in a river of regret...and thoughts of you...
Unfortunately, quantum computers only help you with a single exponential factor. You still won't be able to solve double-exponential problems (those with a lower bound of 2^(2^n)) in polynomial time with them, so they aren't omnipotent.
Some of these algorithms can be tricky to deduce where the time is spent.
....
For instance, a poster posted a program that factored numbers in linear time. But the catch was that it took polynomial (or whatever) time to compile the program
So, always count the time to compile as well as the time to run.
Gary
you're right, I misspoke. I meant to say "All algorithms that run on modern computers have runtimes that can be expressed in terms of mathematical functions" The rest of my post bears out this thinking. Sorry about the confusion.
RSA is based on the difficulty of factoring.
Factoring is provably in NP.
If P=NP, then there is a polynomial time factoring algorithm.
A polynomial time factoring algorithm would significantly reduce the computation required to break RSA.
The point you're missing is that if there is a polynomial time algorithm for an NP-complete problem, then there is a polynomial time algorithm for every problem in NP.
Those kind of articles appear every 3 months on sci.maths...
It's also worth noting that a sufficiently parallel machine is equivalent to a nondeterministic one, for this kind of stuff.
Trees can't go dancing
So do them a big favor
Pretend dancing stinks!
Not to nit-pick, but linear time is a subset of polynomial time.
Theoretically, a program is an algorithm. An algorithm's description is independent of the input size, so the corresponding implementation should be take a constant time to compile.
Now a sub-linear time algorithm is what we're really waiting for.
I agree completely. I think why people find these things so hard to accept though is that much of the academic community believes NP!=P; they are searching for a proof of that, not the reverse.
I don't think all NP problems are decision problems. Factoring an integer is NP, verifying that a factoring is correct is P.
Yes, the original definition was correct, but the parenthetical comment negated whatever limited insight the original definition provided.
If this does, in fact, prove that P=NP, perhaps the biggest open question in computer science, then why is it being published on a website and not in a peer-reviewed academic journal?
There are problems when "science" is reported in the media before it is peer-reviewed: Fleishman and Pons, anyone?
Then again, perhaps I shouldn't speak so quickly... the site is being Slashdotted and I can't download the paper to see for myself!
The P=NP problem has been the death of many a young researcher because it is such a hard problem and there are many subtleties involved in such a proof. Every year there are genuinely smart people who propose a proof one way or another and it requires a significant amount of peer review and analysis to spot the mistake in their proof.
:)
Yep. I'm one of them (graph colorization, which is why this article interested me). Never submitted my work for review, though, cause I don't understand why, or if, it works. I just don't have the graph theory background.
All I know is I have something that looks like it works, it gives correct answers on the, admittedly, small subset of graphs I've tested it on, I just can't prove it.
And, damn, don't I wish I could prove it, one way or the other... If I could prove it wrong, then I could stop working on the damn thing...
I like you, Stuart. You're not like everyone else, here, at Slashdot.
Ok, we prove that 0.999... (with an infinit number of nines) equals 1.
10 x 0.999... = 9.999...
1 x 0.999... = 0.999...
Substracting these two equations, we find that
9 x 0.999... = 9.
Dividing this equation by 9, we obtain
0.999... = 1. QED
Sendy
GNU guru and mainframe hacker
If everything above the level of waveforms in deterministic, as it seems to be, then the brain can still be deterministic as well.
QM has been used in the question of freewill on both sides since it was formulated.
I would have given you a funny comment for that, although I am not sure you are aware of your comic genius!
It's been so long since I was a CS grad student, even Hello World looks NP-complete to me.
-- The Hollow Man
-- The Hollow Man
Non illegitimati carborundum
Actually, P is a subset of NP. NP is the set of problems that, given an answer, that answer can be verified in poly-time (very rough definition). Every member of P is also a member of NP. The question is whether there is any member of NP that is not in P. So the fact that we can't think of a poly-time soln doesn't put the problem in NP--it's the fact that we can produce a poly-time verification algorithm. Once something is proven to be in NP, you could later find a poly-time algorithm and show it's in P also, but that doesn't mean it isn't still in NP.
Visit me on #weirdness on the Galaxynet.
The only difference is that an NP-complete
problem is in NP -- NP-hard problems might
not be. If you can solve an NP-hard problem
in P-time that is a good enough proof to show
that P=NP (it's actually a stronger proof).
BTW, this is not boring. This has serious
implications (e.g. in cryptography). I figured
someone at the NSA has already proved either
P NP or P = NP. Probably the only way P=NP
is if the degree of the companion
polynomial time solutions are of high degree.
If you can solve that, you can solve them all and you're THE MAN. Or - preferably - THE WOMAN offcourse.
Or the slime mold.
I just tried an experiment where I laid out a maze in the classic Traveling Salesman problem. Then I put my smartest slime mold "Silly Green Putty" on it and it was solved in about 18 hours.
I totally agree. This must be a joke (and yes, I'm a CS grad, too)
Sorry, dude, but you should be adding these. If it takes O(n^6) time to convert each way, and we go through 3 conversions, then the cost is 7*O(n^6) (six conversions, one solution).
And as we all know, 7*O(n^6) = O(n^6). So you're off by a back-of-envelope factor of n^1254....
This is a little harder than it seems: first, factoring is not in NP-complete. Ok, so let's take graph colouring - lots of people would be happy to see a P-time algorithm for any of the NP-complete graph problems.
The problem is that a P-time algorithm is not necessarily useful. If I give you a O(n^10^100) algorithm, you can't use it for anything but the smallest problems, like maybe a graph with 4 nodes.
Proving P=NP might not be useful in a practical sense.
Unlimited growth == Cancer.
Just to clarify, Cook showed it for 3SAT. 2SAT is NOT NP-complete. There is a poly-time (perhaps even linear? don't remember) algorithm to solve it.
___
___
If you think big enough, you'll never have to do it.
When discussing indepedent vertex sets on a graph, Plotnikov seems to say that the set of all points in the graph is such a set. (An independent vertex set is a set of vertices in the graph with no edges among the vertices in the set; thus, the whole graph is an independent set if and only if there are no edges in it.)
This is on page 7, when he talks about partitioning the vertex set X.
When I saw this, plus all the minor errors in the paper up to that point, I gave up on reading the rest. Maybe he doesn't use that result later on or something, but I have other things to do today.
There is no recursive solution to the halting problem. It
may be that there is a physically possible, non-recursive solution,
which would invalidate Church's Thesis, but no mathematics.
It's not just your opinion: there's a sense in which you can prove it's one of the hardest problems in computer science.
In one of my complexity theory textbooks (I'll post title/author after I get off work), it's proved that a proof of P!=NP cannot be done with diagonalization, which is the traditional means of proving two classes distinct (think of the proof that there are more real numbers than rational numbers, or the proof that the halting problem cannot be solved by a Turing machine).
So if you're going to prove that P!=NP, you're going to have to come up with a whole new method of proof. (Note: this was around four years ago, and complexity theory is a rapidly-moving field, so there may be some advances I'm not aware of.)
Of course, proving P=NP will be easy, if it's true. Just find a polynomial time solution to a NP-complete problem. :) Which is what this paper claims to do.
Expanding on the under-modded previous reply, Cook showed that 3sat is able to solve any problem that was in NP. He did this by constructing a 3sat problem from the turing machine(*) that would solve the NP problem. This construction can be performed in P time (important!).
Thus, Cook showed that if we are able to solve 3sat, then any problem in NP can be solved by constructing a 3sat problem in P time and then solving that.
The completeness part comes from the fact that 3sat is itself in NP -- this is fairly easy to show. All you need to show is that you can in P time verify that a proposed 3sat answer is correct. this is easy.
(*) I should probably admit that I am a bit hazy on this detail; obviously we can't use this construction to solve the halting problem, so the construction can only work for problems in NP, but turing machines can also solve Non-NP problems. Can anyone clarigy
This would only be true if you could prove that RSA or any other public key algorithm is NP *complete*, i.e. there exists an algorithm that would convert RSA into a known NP-complete problem (like TSP) in polynomial time.
AFAIK such algorithm is unknown to date.
Hamal is an yellow star in the constallation Aries.
It is 66ly away, so it doesn't alter your personality.
I have discovered a solution to the stationary salesman problem that takes polynomial time, however it is too stupid to fit in this post.
Trees can't go dancing
So do them a big favor
Pretend dancing stinks!
Or that's what I thought.
Then I discovered hashing. It performs lookup (which I would SWEAR I could prove must take at least log(n)) in constant time. Yeah, yeah, I know... it's not a fancy advanced technique, but something taught in a first or second level computing course.
But sometimes it's worthwhile to step back and look at things and admire the amazing beauty of the world. That such a thing could exist!
-- Michael Chermside
The blow comes from transforming an exponential complexity
k^n
problem (where k is a constant -- say 2 or 4096) into a polynomial problem
n^k.
We can always grow n to suit our security needs, but if the problem is polynomial, the problem complexity just won't grow fast enough to keep up with the exponential growth of our computing resources.
Johan
Check out the article in Scientific American this month on that great game minesweeper. Someone has proved that the problem of determining whether a position in the game is consistent is NP-complete and it gives an idea of how the proof goes. Neat!
--
-- SIGFPE
Some years ago Cook showed how ANY problem in NP can be reduced to SAT. SAT is the problem to show if for a given boolean formula there is an assignment of values to the variables in it which makes the formula true.
For the gory details see chapter 7 of
Michael Sipser "Introduction to the Theory of Computation" (PWS, Boston 1997)
There as a 3rd possible outcome...however unlikely. 3) NP = P. This would change quite a few notions about computing complex problems however.
I guess I must be in the 10% that think that his viewpoint is okay.
Actually my biggest gripe with Richman is his use of the term "real numbers" to denote entities like 0. The term "real number" in standard mathematics unquestionably refers to an element of the unique (up to isomorphism) complete ordered field. Adding infinitesimals like 0 and calling them real numbers is perfectly fine on a technical level; everything remains consistent and all. Problem is, it doesn't lead to real numbers as most people know them, since for example bounded sequences such as
suddenly fail to have any least upper bound.The issue is not mathematical, it's linguistic. What Richman calls real numbers are not what other mathematicians call real numbers.
There are some algorithms with a high exponent that are usable in practice. LLL w/ backtracking and pruning is hueristically O(n^4.5). Schoof's algorithm for counting the number of points on an eliptic curve is O(n^6); Atkin's algorithm is O(n^5). Welsher-Parks (resolution of minimal spanning sets) is O(n^8) (actually O(n^7) if you are willing to accept a certain minimal probability of error). The Adleman-Huang algorithm for proving primality is O(n^11).
No, Factoring an integer is NP Hard, NP problems are, by definition, decision problem. NP Hard problems are general problems with the property that an NP Complete problem can be transformed into it.
Mail it to me (via an anonymous remailer, if you like), and I'll critique it and reference it from
http://mter.enki.net/. I'm a non-degreed CS geek who has studied this stuff for fun, but I do know how these proofs work.
I guess we (I) have a semantic problem here.
I thought the notion "non-deterministic" in relation a quantum computer is based on the fact that it is, well, a quantum computer...
If we define determistic as "computable", i.e. given a process, we are able to define "measures" (possibilites in QM) which can be predicted by a theory, and therefore call this given process determistic, then I fail to name non-deterministic processes.
I just spent an hour looking at this and related pages -- thanks for posting the link.
willis/
there is no thing
what else could you want?
Offtopic sure is better than "informative"...
HOWEVER, during all those dozins of years Computer Scientists have been trying to show P!=NP(with no success) they achieved success in showing another thing: they showed that if P=NP everything(well, almost everything) is easy.
In(not so) short, there is an infinite "pyramid" of complexity classes built one on top of the other called Polynomail Hierarchy(or PH). This includes problems starting from P(easiest) and going higher and higher to "infinitely hard" problems. I should say they are not really "infinitely hard" because you can solve them all in Polynomial Space(if you don't know what it is, just ignore this sentence) but they are very hard(polynomial space is also known as the class of "all interesting problems").
Now, what they showed is that if you "collapse" one layer of the pyramid, it all collapses to that layer. And showing P=NP is collapsing the very first layer.
What's my point? Wait a second, there is one on the way(assuming I don't forget it).
All right, says Mr. Slash D. Wiz, so what if P=NP makes all current cryptography obsolete? They can now(with the new computation power) come up with new cryptographic tools and such. Well, if P really equals NP, this means that it is going to be very hard(I don't want to say impossible) to find a cryptographic model that won't be easy to crack.
You see where I was getting with all that math mumble? Not only current cryptography is obsolete if P=NP, the whole field of cryptography might go in the ways of alchimestry...
So, you'd better hope this isn't true. It might put an end all all those nasty complexity courses in the Computer-Science department but you could use the time of the class to show your privacy the way out of your life.
---
Oh yeah???
As far as I can tell, his first algorithm (p. 5-6) contains a simple array-indexing error. Here's my paraphrase:
INPUT: M, an n x n array of booleans.
If the "else" branch is ever taken, then index i will reference a location outside of array M before the procedure halts, right? Here he is just reviewing a 40-year-old algorithm for bipartite matching, but it is disturbing that his very first algorithm contains a basic error .
Or am I missing something? :-)
Somehow I think God is saddened at his creation's attempts to pretend to be bigger than he is.
Well I put my tongue in my cheek as you advised me to do, and, strangely enough, it looked like I was sucking an invisible dick! How embarassing, at work!
Even if the exponent is quite large but fixed, there is always the hope of throwing more
hardware at the problem. If the problem
is in exponontial-time, then all hope is gone.
But how many years would be enough? Should you wait for that new faster chip? Better have a rack for hot-pluggable disks, and be sure that you can adapt to switch in larger ones when you start running out of disk space.
Sometimes directly testing a theory isn't the easy way.
Caution: Now approaching the (technological) singularity.
I think we've pushed this "anyone can grow up to be president" thing too far.
...at least in the theoretical CS context. A deterministic machine can only be in one state at a time; a non-deterministic machine is thought of as simultaneously taking all of the (possibly many) possible branches. A deterministic machine can simulate a nondeterministic one in exponential time, so the set of problems they can solve is equivalent, but obviously exploring all branches at once is going to be faster. Essentially, it's as though you had an infinite number of processors and could fork() another process with zero overhead every time you wanted to explore a new avenue.
Actually, aside from your math mistake that someone else pointed out :), the ability to get a polynomial time algorithm for an NP-complete problem could be quite problematic for cryptography, even if the terms are in the range you specified. The reason is that a polynomial time algorithm can often be transformed into a parallel algorithm with lower coefficients. So, it could be possible, ideally, to take your O(n^1260) and transform it into an O(n) algorithm running on 1260 processors. Of course, that's the absolutely best case, but the fact is that polynomial time algorithms can be made to benefit from parallel processing, which is quite cheap these days (ie, "We could make a Beowulf cluster of these!" ;), making less efficient algorithms useful.
I dunno. I would be hard pressed to think of any case where the worst-case polynomial doesn't simplify down to one of order \leq to the lenght of the input. Still not so good, but a limit. Sheer speculation.
Another avenue is that perhaps a partial solution would be useful from a cryptographic point of view. Perhaps we do O(n^10) units of work and use the partial result to construct a 2^60 bit brute force attack against a key. also speculation, but I'd appreciate your thoughts.
A: John C-ARR-nack
Actually, neither one of these statements is correct. First of all, noone has come up with a quantum algorithm for solving even one of the NP-hard problems in polynomial time. Yes, there is a quantum algorithm for factoring, but factoring is not NP-hard. I know a bit about this since I worked on a quantum algorithm for solving SAT (an NP-hard problem), and studied a good bit of the previous literature on this.
Second, your statement that it can't be proven that NP-hard problems can't be solved in polynomial time on a classical computer is also false. If one day, it is proven that P != NP, then this is exactly what will be proven: NP-hard problems have no polynomial time solutions.
"Ask again later"
Glückwünsche, haben Sie Slashdot ermordet, indem Sie zum korporativen Druck beugten und Subskriptionen einlei
Take graph isomorphism, for example. It is provably NP hard, however there is a linear
time algorithm which works well in practice. This is used, for example, in a CAD system where you are comparing the electrical circuit network of
your schematic or procedural description with an extracted network from the VLSI mask, to verify that your physical layout implements the same circuit as your higher level description.
In practice, a hashing algorithm will give you
the answer in linear time, with almost any degree of certainty. There is a small probability of a false positive, however.
It seems like in many cases a probablistic algorithm like this gives practically certain
results. I don't know about factoring numbers, but I sometimes think that a probabilistic algorithm such as the graph isomorphism one could be applied to the factoring problem.
Sorry, but strictly speaking, it's:
... or" here since
:-)
P = N * P
if and only if
P = 0 or N = 1
You must not use "either
it is not an exclusive or.
Matthias (CS Graduate
Ceci n'est pas une sig
oracle giving us an O(n^6) solution to a particular NP complete
graph-theoretic problem might yield an O(n^12) factorisation
algorithm (since numbers of size n might map onto graphs of size n^2).
The use of the word "transformation" here is misleading. In some cases, we might solve an NP-c problem with input size n as "the result returned by this other NP-c problem with input size n^2", but more often, we'll use the NP-c with the known solution n or n^2 times with input size n. This still increases the time, but not by as much (+1 or +2 vs. *2 in the exponent, I think).
--
The shareholder is always right.
> there are some problems (such as the Halting
> Problem) that are formally undecidable - not
> solvable in polynomial time even on a
> non-deterministic computer
The Halting Problem is unsolvable on any computer, by any computation model, exponential time or not, to my knowledge (I haven't taken the class my school offers in automata, but I've done a bit or reading).
Dave
You're thinking of something more along the lines of the Travelling Salesman problem. Given an undirected, weighted graph, the problem is to find the lowest-cost Hamiltonian cycle (a path that visits all the nodes on the graph without taking the same edge twice, ultimately returning to its beginning).
;)
Finding a Hamiltonian cycle alone is NP-Complete. Adding the weighted edges in there doesn't help.
Dave
Your argument makes an invalid assumption... that there is a fundamental difference (time-complexity wise) between a non-deterministic Turing Machine, and a deterministic one. This is the undetermined theoretical problem here, and its not as obvious as one thinks. Any non-deterministic Turing machine can be converted a deterministic one, however, all KNOWN algorithms to do this produce a deterministic Turing Machine that arrives at a solution in super-polynomial time. This does not mean that an algorithm to do this does not exist. In fact, Cooke's theorem clearly implies that if a Polynomial time solution to an NP-complete problem exists, then such an algorithm must also exist. (i.e. if a Non-deterministic TM can solve a problem in Polynomial time, there exists a deterministic TM which can also solve that problem in Polynomial time).
Just my $0.02
-- Rich
Free your mind and your Ass will follow -- George Clinton
All algorithms that run on modern computers have runtimes that can be described in terms of polynomial functions. Some examples of these are: N,N^2,LogN,NLogN,N^N
As you allude to later in your posting, N^N is not a polynomial function.
--Sam
Actually, there original version was flawed. See this page for more information. Check out the "Post Script: An Attack on the CP Algorithm" section.
But for every Wiles, there are thousands of crackpots, and also a few intelligent types who made a very subtle mistake. The point of skepticism is to keep you from swallowing malarky. In the case of something like a claimed algorithm for an NP-complete problem, the person making the claim has a relatively easy way to demonstrate credibility: just implement the thing and use it solve some hard problems such as the RSA factoring challenges. Anyone unwilling or unable to make such efforts almost certainly is making a bogus claim, either intentionally or because they just don't understand what they're doing.
David
I studied CS (graduated 2 years ago) and my first thought upon reading this post was along the lines of "NP-complete .. that sounds familiar" .. :)
Your second proposition isn't necessarily true. In principle all sub-atomic particle physical entities are subject to the laws of Quantum Mechanics but not ALL physical entities (that modulo relativity is very important). Once you acheive atoms the outcomes are more along the lines of deterministic. However, there is that immeasurable value of small variations over time in the quantum side that would have some sort of impact on the "real-life"* side.
The reason one can't measure the effects of those unpredictabilities, and therefore can't determine whether or not it has a direct impact on "real-life" is the same law that governs the unpredictability, the Heisenberg Uncertainty.
So whether or not your second proposition is true is governed still only by phylosophy and not science.
*"real-life" would be the area where Classic Mechanics looks correct.
People who quote themselves bug the crap out of me -- Me.
Coming up with a polynomial time parital solution to an NP problem happens all the time. Complexity bounds apply to a problem in general, not partial solutions. From Mr. Busygin's quote, it looks like this might be a partial solution. In which case, even if the algorithm is polynomial, it doesn't show that P=NP. Whew.
In related news, reduced ordered binary decision diagrams can be cleverly used to solve SAT in polynomial time some of the time. This has nice applications in circuit verification and equivalence checking. However, in some cases (such as multiplier circuits), its provably impossible to get a P solution using BDDs.
By definition, a language L is NP-complete if it is both in the class NP and is NP-hard.
So a language that is NP-complete is always NP-hard. Not all languages that are NP-hard are NP-complete, since they may not be in the class NP.
Roughly speaking, NP-hard means that it is as hard as any other language in NP. Put another way, if you can solve an NP-hard problem quickly, you can solve any problem in NP quickly.
In the case of this article, this clique partitioning problem is known to be NP-hard, but I don't think it is known to be in NP, which explains why they aren't referring to it as NP-complete.
Of course the paper is almost certainly bogus, but if it turned out to be legitimate, it would lead to algorithms with practical complexity. Take a few thousand smart computer scientists, get them pointed in the right direction on a problem of immense practical importance, and the order will probably drop quickly into the O(n^2) or O(n^3) range.
David
Well, certainly noone has ever proven that P != NP, which should be easier. If P != NP, however, there is a non-empty set of problems which are not in P, are in NP, and not NP-complete. None of these has ever been found without mathematically generating a problem based on P != NP. Of naturally occuring problems, no NP (remember P is a subset of NP) problem has been found which was not either in P or NP-complete. While it is certainly counter-intuitive, this may mean that there is simply something we don't understand (Could it Be ??? ;-) about the mathematics of NP-Completeness which bars us from solving NPC problems.
-- Rich
Free your mind and your Ass will follow -- George Clinton
People have applied probabilistic algorithms to factoring, but RSA encryption is still considered safe.
Exactly...one would think that a TRUE discovery of such a proof would be published in a more well recognized journal.
But what do I know
If you liked this thought maybe you would find my blog nice too:
Hashing does take O(ln(n)) time for the most general case (n is the number of objects stored).
If the guy says "you can't fill it beyond x%" then he's not permitting you to have arbitrary n, and the order expression means nothing - i.e. his O(1) expression means nothing. He asks for your maximum, calculates a lowest upper bound, and creates an algorithm which always works with time less than that upper bound. Voila, constant time. But not O(1)!
I know I'm not beiong coherent, but I've had a long day.
In order to decide between (i.e. hash) N objects, at least lg(N) bits must be calculated for the hash value. No you can't do them all at once, as I'm chosing N=2^1048576. When you fix that, I'll increase N again. I'm allowed to do that, you're not allowed to stop me.
FatPhil
Also FatPhil on SoylentNews, id 863
Well it is not a paper, but a book on the subject of "Flows and networks". Out of print.
ISBN:0691079625
I remember there were a bunch of neat books mentioned in some CS-Theory class. All of them were out of print...
Computer scientists such as Mr. Platnikov are going to very complex lengths to prove that P=NP, but their approach is much too circuitous.
A true mathematician would realize that we only need to establish that P=0, or that N=1.
Corby
I'm a CS/CE student and I know about the N and NP stuff. I've also taken an Applied Graph Theory course (that's starting to slip away), so I know about the minimum clique problem too. However, the one thing I haven't figured out yet is how is this problem useful in the real world? What are the applications of this? I'm assuming some sort of networking applications, but right now I can't think of any.
Does anyone know how this algorithm and finding the minimum clique will be useful in the real world?
This kind of seems like one of those worthless computer science problems that have no real usefulness ouside of academia.
Things you think are in the Constitution, but are not.
can anyone please put a readable version of this document on a fast mirror?
Other people already pointed out your major mathematical error here (you multiplied together the exponents, you should be adding together work-operations, i.e. O(n^6)+O(n^2) == O(n^6) not O(n^8) and REALLY not O(n^12)). I just wanted to point out that while certainly the polynomial order of any potential P==NP reduction is relevant (and the constants embedded in that O are usually significant too), the overall result of any (hypothetical) such reduction will probably slaughter things like 4096 bit factoring NP-Hard problems, since they fundamentally rely on the exponential scaling of difficulty.
In your example a 4096-bit key would be require something like, at worst, C*4096^7 operations to factor for some C. This is tiny compared to 2^4096. And you only gain security in some polynomial of the number of bits you now have to use, so doubling the number of bits doesn't exponentially increase the search space for solutions.
Any details on this? I'm aware of von Neumann stealing the credit for linear programming from Kantorovich, but would be interested in another example of Cold War Mathematics.
-- the most controversial site on the Web
Just read the F'in paper -- Then comment intelligently math-boy. What a cop-out.
Many people are talking about how the conversion from NP form A to NP form B would be O(n^2), and the solution would be O(n^6), and thus the whole process would be O(n^8). This is unfortunately wrong. If I remember correctly from Descrete math, each of these are a single step in the function which first coverts to form B, then solves. The correct format is O(max(n^2, n^6)), which in this case is still O(n^6)!
Think of it this way: If we had something of O(n + n^5), as n got arbitrarily large, the n term would be practically negligable(sp?), and thus it could be rewritten O(n^5).
Hope this clears up the issue.
Save a life. Eat more cheese
So there I was, juggling apples and small animals, when I accidentally bit into the wrong one...
I should have added "for smallish N". really what I meant though is that current E(N) techniques of solving NP complete problems paralelize well. But the reason I bring it up is that there were some posts earlier talking about people's brains doing NP complete problems 'quickly', and that was my guess as to why.
Trees can't go dancing
So do them a big favor
Pretend dancing stinks!
I'd like to mention a few facts about the problem, the papers, maths, and all those posts in general :
->Thousands of false proofs of either P=NP or P!=NP have been submitted.
->Because it hasn't been either proved or disproved doesn't mean it is false. In fact, either answer has to be true, and both are unproved !!!
->P and NP are sets of algorithms, not real or natural numbers, so P and NP cannot be 0 or 1, and besides, even if it was the case, then it could be many other values (correct answer would be 0 and x).
->Earth is populated by 90% morons who don't know what they're talking about, and most of them post on Slashdot. Conversely, 90% of posts are from morons.
->One must have much time to loose to reply here instead of just reading the paper, and besides, it is plenty of obvious errors.
I think the definition is simply this: a nondeterministic computer is one that can simultaneously verify all possible solutions. If a solution is verifiable in polynomial time, then the nondeterministic computer can solve the problem in polynomial time. Hence the problem is in NP. I think that's about as clear as the definition gets.
Ever since I fumbled with NP completeness and NP hard problems, I've believed that it should be possible to solve several of these problems (including the one in the paper) in a P method, but only by being intelligent about the problem and not solving it cold analytically. This paper seems to present an algorithm that can do it. It's very interesting if it would work but I am skeptical as well.
So long and thanks for all the fish . . . !!!
we need an infinite tape to put data onto.
As far as I know, I do not have an infinite tape going through my body. One could argue that the universe is our infinite tape, I suppose, but that relies on the assumption that the universe is infinite.
I in fact might argue that we are no more powerful than DFAs. Very large, very convoluted DFAs, but still DFAs. That is a statement that I can be sure of.
arvind rulez
The size of the graph description is quadratic in the number of vertices, not exponential. That's O(n^2), not O(2^n). Big difference. By the way, this particular mistake makes a good pet peeve -- it's in the same class as saying that RSA encryption depends on the difficulty of factoring large prime numbers. I think I've seen Brooks' Law justified by the argument that "the number of communication links between people grows exponentially with the number of people"? NO! QUADRATICALLY! NOT EXPONENTIALLY!
This is even worse, though, because it indicates a real misunderstanding of the concepts. A lot of people seem not to appreciate the difference between the equations y = x^2 and y = 2^x: they seem to think the two are almost the same because their graphs look so similar (they both curve sharply upward, right?). Well, that's true if you only look at them for small y, like y < 10 or 20 (and, of course, positive x). But try relabelling your axes to use x values from 0 to 33 and y values from 0 to 1000 and graph the two functions again: y = 2^x looks a lot steeper, doesn't it? Now, try x values to 1000 and y values to 1,000,000: y = x^2 still looks about the same, but you can hardly draw y = 2^x as anything but a (nearly) vertical line, since, if the width of the paper is 1000, 20 is so close to zero. See the difference yet?
David Gould
David Gould
main(i){putchar(340056100>>(i-1)*5&31|!!(i<6)<< 6)&&main(++i);}
Post = Ninth Post?
By the way, there is now $1,000,000 prize available for proving that P is or is not equal to NP. Of course, this could produce more correct, well-intentioned but wrong, and nutty solutions.
11.0010010000111111011010101000100010000101101000
The supposed NBT before the web was multimedia. Remember all computers were being advertised as "MPC2"?
High temperature superconductors were and are real. The problem is the mass-medias ignorance of what was meant by "high temperature." That is, you merely need liquid nitrogen to get ceramics to superconduct, as opposed to the colder liquid oxygen for metallic materials.
Any sufficiently advanced civilization is indistinguishable from Gods.
Conversely, if you've read Roger Penrose, you'll know that he argues that human intelligence is non-computable.
While this is all a very interesting debate, the original point I was making still applies, I think - that how human thought relates to computability isn't really relevant to a discussion on P=/!=NP.
Thank you for your correction, though - it's nice to see that people with clue still read /. occasionally.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
It was already proved on that Homer 3D Simpsons Halloween episode :)
I was under the impression that "were" was the 2nd person singular subjunctive. Is is also the 3rd?
Quick definition for others: NP-hard means every problem in NP can be transformed in polynomial time into an instance of this problem, but it doesn't necessarily mean that it's itself in NP. NP-complete = NP-hard + is in NP.
Are you sure? I don't think that this is the case - while some algorithms for currently-intractable problems have been proposed for a theoretical quantum computer, none of these algorithms is for an NP-hard problem. References appreciated if I'm horribly wrong (which I may well be).
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
Part of the reason for the extreme skepticism is that thousands of brilliant people have tried to come up with a solution to this problem.
Although I agree with you completely, I find your lack of faith...disturbing. If I strip out all references to NP, your post could just as easily apply to the proof of Fermat's theorem. Your statements imply that the guy who proposes the proof today is less smart than the people who went before and has access to exactly the same knowledge. BZZZT! He may be smarter, and he has more mathematical tools to work with. Or are you implying that mathematics does not
advance?
Empirical evidence (namely, failures to prove the conjecture in the past) is completely irrelevant.
If you guys keep on with these mathmatical enigmas, one day you are going to prove black is white and white is black then the whole universe is going to disapear in a puff of smoke. That's really going to piss God off.
What I meant by my second point was that by having a P solutoin, we inherently have some structure to the problem. If we are able to exploint that structure, we might be able to apply it to the brute force approach and cut down the search space.
The implicity assumption there is that we get diminishing returns in our solution. Take sorting as an example. If we have a quick sort running over an almost sorted list, we get diminishing returns -- after just a few iterations, the list may be completely sorted except for one element, but we'll be running O(n^2) iterations just to move that element to where it was supposed to be.
If we have an O(n^4096) solution to 3sat, then we might be able to run it for a few hundred iterations and analyse the partial result. Say that 75% of the time, we learn something useful about the structure of the answer (enough to practically apply a brute force approach, say). Since this a probablistic result, we couldn't use it to improve the O() time of the algorithm, but it would be a very effective attack against cryptography.
Hashing isn't really constant time. It's still logarithmic, just with a very small constant (if done well).
To see why, look at the length of the hash key. In order for an element to hash to a unique value the space of hash keys must be at least as large as the number of elements in the table. Therefore, to achieve a perfect hash the number of bits in the hash key must be at least log(elements).
Now, how about the computation of the hash key? Suppose we do something really simple, like xor the bytes (or log n chunks of bits) in the value. This isn't a constant time operation; it's linear in the number of bits in the key, or logarithmic in the number of elements, assuming a constant amount of hardware (obviously, if you assume an unbounded amount of hardware, the time could be constant, but that's not really very interesting).
Hash lookup is no better. You still have log n bits to recognize.
Maybe there are ways of performing lookup in less than log n time, but hashing is not one of those. In practice, hashing takes a small constant amount of time because we don't or can't optimize very well for very small hash tables. Computing a 16-bit hash isn't usually cheaper than computing a 32-bit hash, so we think of it as constant, but that's really not the case.
Remember what O(log n) really means. It means that as the problem size grows the amount of work grows asymptotically and proportionately (or maybe it's at worst proportionately, I don't remember all the notation details and I'm too lazy to fetch my copy of Cormen/Leiserson/Rivest from my bookshelf) to log n. It says nothing, however, about what the proportionality constant is. You could have one algorithm that's O(e^n) (exponential complexity) and another algorithm that's O(1) (constant complexity), and in practice the former could be more efficient -- the constant factor of the constant time algorithm may overwhelm the exponential (or worse) blowup for the problem sizes that will actually be encountered.
This brings up another point -- most practical algorithms and implementations have more than one limiting factor. The O notation only expresses the dominating limit (or limits, if a particular problem has multiple inputs) as the problem size gets arbitrarily large. So it is with hashing.
Just in case... YHBT, YHL, HAND...
Now, get on with your lives, I already knew about the x=y=0 issue... geez.
In Soviet Russia, Jesus asks: "What Would You Do?"
Why? Because every problem in P has a polynomial time for determining if the 'guess' is correct.
--
Ben Kosse
--
Ben Kosse
Remember Ed Curry!
"In other words, Slashdot is just as bad as any other forum, but the knee-jerk garbage here is more in agreement with your own preconceived and ill-considered notions"
No, you misread my post.
Not necessarily. There are problems there is no solution for, the canonical example being the Halting Problem (look it up in Google). We know there's no solution to that. In fact, if a solution were to pop up, it would invalidate a couple hundred years worth of math, which would be a great surprise.
Sometimes you can know there's no other way. Should someday a proof emerge that P!=NP, then for all NP-complete problems, it will have been proved that there are no easier ways, no matter how long you search for one.
Just because a domain is infinite (such as the domain "solutions to problems") does not mean that it MUST contain an element that has any particular set of particular charecteristics. Just because there are an infinite number of integers does not mean that one of them MUST have a fractional component, if we just look hard enough!
Well, aren't we just incredibly honoured that all of us lowly unknowledgable plebs have been graced with your presence, the one and only knowledgeable person "in the crowd"?
What are you saying, that you are knowledgable but everyone else here isn't, or that nobody here is knowledgeable, including you? Either way, you've just insulted a lot of people - many of them notably more intelligent and more knowledgeable than either you or me. So get off your high horse. Yes there are a lot of idiots on /., but there are a lot of very intelligent people here too, people who are actually capable of thinking for themselves and analyzing situtations. I like /. discussions precisely because these people have interesting things to say; I've tried before to peruse more "mass-market" average-joe discussion groups, and I couldn't handle it - almost everybody there either accepts the status quo, or they just follow whatever the crowd thinks, or they just spew rehashed versions of whatever shit ideas their parents raised them with. As difficult as it might be to believe, of all online discussion groups, /. has one of the highest percentages of contributors who actually *think*.
I'm not a CS grad student, but I was once. A large number of NP problems have been shown to be equivalant. If any of them are shown to be in P, then all the other have, too. I *believe* (read--haven't studied this for a long time) that all the NP-complete problems have been shown to be equivalent.
Hmm .. not a bad one. But almost all "riddles" like these seem to divide by zero somewhere to obtain their confusing-looking results, which is exactly what you've done there (x - y is 0) ..
To go the other way, standard semi-conductor computers rely on QM to work. I don't remember the details, but my Physics of Semi-Conductors class was based thoroughly on QM. The thing is, at the level where computation took place, the quantum weirdness effects were no longer relevant. As such, you can formulate the workings entirely deterministically even though they are based on non-deterministic events.
The question whether the brain uses quantum level effects is still open. Roger Penrose took a lot of flak for suggesting such effects in his book. Even though it wasn't really relevant to his main point (our current knowledge of science is incomplete and the answer to the mind/brain connection may require new theories), this part was the one most critics chose to attack. Currently, no serious scientific theory suggests a non-deterministic component, AFAIK (which, admittedly, is not far).
Minor nit (only politeness (oops) prevents me from decrying the preceding (parent) post as utter nonsense):
Not at all. Under favourable circumstances, hash insertion and searching can be logarithmic. But, in terms of complexity, such tasks didn't get any easier. In the worst case, hashing and insertion are exactly the same as a linear list. In those worst cases, they transform trivially to a linear search.
Matthew
- Who dealt with this shit for too long to let this one slip past.
heh. In unary representation, I believe composite is P. The trick is that the input is exponentially long...
First, factoring is not in NP-complete
Finding nontrivial factors is in NP, so you could use an algorithm for an NP-complete problem.
If I give you a O(n^10^100) algorithm...
In practice, P-time essentially means efficient. Once you understand the structure of a (non-artificial) problem well enough to provide a P-time algorithm, usually the complexity can be rapidly pushed down until it's in the cubic or quadratic range. The worst I've ever seen for a real problem (finding a minimal cycle basis for a graph) was O(n^6).
David
Equivalent in what sense?
If you mean "many-one polynomial time equivalence", that is A = B iff A is many-one polytime reducible to B, and B is many-one polytime reducible to A, then your statement follows directly from the definition of NP-completeness. I think this is probably what you mean, judging by the context.
If you mean "polynomial time isomorphic", this is not known. (It was conjectured in the '70s, but hasn't been proven. Many think this is not true.)
N=1
P=0
Is that a clip-on tie he's wearing? I think so!
(1) Yes, the problem under consideration in the paper is indeed NP-complete, proven a long time ago by someone other than the author of that paper.
(2) You DO NOT need to show an isomorphism between your problem and an NP-complete problem to show your problem is NP-complete.
You give a polynomial time reduction from the particular NP-complete problem to your candidate problem. Think of it as showing that the NP-complete problem is a "special case" of the candidate problem (that's roughly what goes on, but not exactly).
And a reduction need not be an isomorphism. The isomorphism bit is a totally different issue which people know little about. The known NP-complete problems are indeed isomorphic, but it is not for certain that all of the complete problems are.
Umm... data mining (my current gig)?
Those combinatorics explode awful fast as your data scales. You can't just wait for a Pentium 4 and hope that solves your algorithmic problems...
--
Marc A. Lepage (aka SEGV)
--
Marc A. Lepage
Software Developer
Hmmm, reading your first sentence I shouldn't post that, but ...
1. Proposition: Every object of the laws of Quantum Mechanics is non-deterministic
2. Proposition: Every physical entity is object to the laws of Quantum Mechanics (modulo relativistic effects)
3. Proposition: Human brains are physical entities.
...
The only questions seems to be to what extent human brains are non-deterministic...
His maths is dreadful but his point is right: the transformations of
problems in NPTIME can increase the complexity of the problem, eg. an
oracle giving us an O(n^6) solution to a particular NP complete
graph-theoretic problem might yield an O(n^12) factorisation
algorithm (since numbers of size n might map onto graphs of size n^2).
There is a linear-time algorithm for 2SAT. It is basically as hard as finding a path from one node s to another node t in a directed graph.
By the way, 2SAT is NL-complete (nondeterministic logarithmic space complete with respect to logspace reductions), which implies it is in P.
...a crackpot.
A very respected proof theorist this summer submitted a proof in the major logic conference in Paris this summer. He claims that the P=NP problem is independent of the Peano axioms...
I am puzzled by this statement, so some kind of further info or a link would be greatly appreciated.
I've recently been looking into the possibility that Goedel's proof can be adapted to demonstrate that a great many problems can be subsumed within the Peano axioms. Much of what I have proved so far has been counter-intuitive (at least to me and I've already suggested I may be a crackpot) so it would not surprise me if I'm wrong.
I would like to know more about this proof from the summer conference. Anyone with more info or links is invited to post them.
Eternal vigilance only works if you look in every direction.
Determining whether a boolean formula has a solution (assignment of trues/falses to the variables, that makes the formula evaluate to true) is NP-complete.
Determining if such a formula is a tautology (true) or if it is a contradiction (false) are both coNP-complete problems (conjectured to be harder than NP).
I'm unaware of QC making progress on these problems.
Well, I guess you all see why the Prof gave me a C in that class.
So long and thanks for all the fish . . . !!!
Didn't Lawrence P. Waterhouse solve this one a few years back?
M@T
'sapientia potestas est'
Wow, that would certainly be the coolest outcome of the P=NP question. Do you have any details, name of the guy, proof technique, preprint to download etc.? Thanks!
--
Yes, this is an error in the submission. I meant NP-complete.
Isn't this one of those 7 math problems that someone is offering a million bucks for solving?
But quantum computer is non-deterministic. You will not argue with that, will you? So solving, say, TSP in poly-time using a QC is really just a matter of finding the right algorithm.
___
___
If you think big enough, you'll never have to do it.
Once you acheive atoms the outcomes are more along the lines of deterministic.
I'm not so sure aout this. What about superconductors, superfluid helium, semiconductor devices, cosmic rays....
These are all _obviously_ quantum objects, and all macroscopic. Hell, you can't get more macroscopic than the sun, and it's quantum mechanics that keeps it running.
The point is, while you may not have your classic "where is it and how fast is it going?" type situation, quantum rules are the only way to explain these objects.
Heisenberg uncertainty is not the only strange effect here, others show their faces in different situations. Indeed you'll see an uncertainty relation remarkably similar to Heisenberg's if you try to localise a (classical) sound pulse in time and frequency.
Dave
I'm walking by his office in 20 minutes...
If you look at cryptography through complexity theory, that statement is true. However, it might be the case that factoring is in P, but that there is a lower bound of, say, n^12 (preferably with a large constant factor). A proof of this would actually be an argument for the security of RSA (still not a proof).
Whats realy needed is a gap between the time taken to create keys, and the time needed to break them. If this time increases exponentially with the key length, great, but I can live with a large polynomial increase.
At least, in the dark, I don't see the difference.
GCS/MU d- s+: a- C++$ USH++$ P- L+> E W++$ N o-- K- W++@ O-- M- !V PS Y+ PGP- t+ 5(+) X- R tv? b++++ y++(+++)
Unless there's been a HUGE breakthrough which I didn't hear about, it is not known whether a quantum computer can solve NP-complete problems in polynomial time. None of the "hard" problems (like factoring) that are known to be amenable to quantum solutions are actually NP-complete.
Sorry, factoring is not known to be NP-hard or NP-complete.
Can You prove that? ;)
-- No, no -- Not that one!
Just read the F'in paper -- Then comment intelligently math-boy. What a cop-out. The person stated that they were a CS grad student and not a mathematician. And you are insulting them for not commenting intelligently?
You must not have seen the International Obfuscated C Code Contest winner that solved the towers of hanoi using the C preprocessor. :-)
I'll bite. Quantum situations are governed by the entirely deterministic Schrodinger equation. How is your quantum computer non-deterministic? Of course, you're not going to beat it with a Turing machine, but there's a longway between non-computable and non-deterministic.
Call me stupid, but can someone explain how a Turing machine can possibly be non-deterministic?
Turing invented his machine as a definition of computation (which is by nature deterministic). Has anyone ever observed a Turing machine do something non-deterministically?
"a sub-linear time algorithm". It sounds funny... an algorithm which would NOT take longer as the size of the problem increased. In fact, it's really just a joke, because "obviously" no such thing could exist.
Just because it is faster than linear time does not mean that it doesn't increase with size. EX for an O(log(n)) algorithm would take twice as much time to do 100 items than to do 10 (log(100)=2,log(10)=1).
JET Program: see Japan, meet intere
yes
"Cause there's 40 different shades of black, so many fortresses and ways to attack, so why you complainin'?"
>Rubbish! RSA only depends on that it is *hard* to factorize integers. If the polynomial is aggressive enough RSA may still be effective.
/trold
>
> Have you ever worked with O(n^16) algorithms? They are P allright but . . .
RSA is heavily dependant on that factoring an integer can't be done (at this moment) in polynomial time. e.g. The RSA-155 challenge, where a 155 digit integer was to be factored into two prime numbers, was solved in roughly 8000 MIPS-years of CPU-effort. The next RSA challenge, RSA-160 (still not solved!), where only 5 more decimal digits are added, will require about 32 times (2^5 times) the CPU usage! This way it won't matter how fast a given computer-network can compute, you just add a few more digits to the key, and they'll have tons of work.
If you could factorize an integer in polynomial time, you would have to use enormous keys. e.g. If it could be done in polynomial time (say O(n^16)) RSA-160 would only require 1.66 times the effort of RSA-155. The complexity-class means everything...
To sum it up for those /. readers without a history of complexity theory, P and NP represent certain levels of algorithmic complexity: P representing that the algorithm/problem can be solved in polynomial time. For further discussion, take a course on the Theory of Computation.
MCH/VO S* W- N+++++ PEC+++ D(s++/r) A a+>+++ C* G++(++++) Q+ 666 Y
The nondeterministic Turing machine is a separate creature and, to the best of my knowledge, I don't know that Turing ever thought about it. (Though I wouldn't swear that he didn't---he was an amazing man). It's an abstract generalization of a Turing machine. The guy who said that you should imagine a computer in which you can use an arbitrary number of fork()'s which produce completely parallel processes, any one of which might solve the problem, had the right idea. Perhaps even more roughly, think of a parallel computer that always has as many nodes as you need to create any new process you might want to run on a new node without conflicting with other nodes in any way.
It's a rather abstract model that isn't equivalent to anything we have built. I suppose if we ever build good enough parallel computers, it might be taken as a model for massively parallel computation---but I've never seen anyone pushing this line. The number of nodes would need to grow exponentially with the problem size and this degree of parallelism for problems we might be interested in is probably fairy dust unless DNA or quantum based computers work out. (And no one has proven that either of these amount to general non-determinstic Turing machines anyway, even if they can be made to work at all). So for the moment it's an abstract model of computation that lets us consider whether we can reduce a large number of exponential time problems that are polynomial time on the abstract model to polynomial time on a real computer. In other words, don't hold your breath waiting for a non-deterministic P9 from Intel.
Warning: I'm not an expert on this field, but I am a mathematician and I did study this stuff in a basic way long, long ago. Apologies if I've mangled some facts.
I've converted the document to PDF and mirrored it here because the original site is both being slashdotted and not all of you can probably read PostScript. The mirror is on a 40 MBit connection and should be capable of handling the load.
As a state gets corrupt, its laws multiply; the most corrupt states have the most numerous laws. (Tacitus, Annales 3:27)
Yes, this is in fact one of the seven $1,000,000 Millenium Prize Problems. The other six are The Hodge Conjecture, The Poincaré Conjecture, The Riemann Hypothesis, Yang-Mills Existence and Mass Gap, Navier-Stokes Existence and Smoothness, and The Birch and Swinnerton-Dyer Conjecture. More information is available at Claymath's website. It includes simple examples of the problems as well as lengthy PDF files explaining them mathematically.
You might also find the solution to this problem in Concrete Mathematics, a book of Discrete Mathematics. It is written in one of the side notes there that N=1 implies that P=NP. =-)
"I have not failed. I've simply found 10,000 ways that won't work." --Thomas Edison
just read you email + .sig
clever...very clever
Dave
I studied CS and I swear we never covered the minimal clique partition problem ?
Sorry I don't understand this one, can someone summarise this in a more user friendly manner ?
Busygin just hosts a repository of papers. The man of the hour is Anatoly Plotnikov.
But for every Wiles, there are thousands of crackpots, and also a few intelligent types who made a very subtle mistake.
Even Wiles made a mistake the first time! I do not think it is wise to make a $10-1k bet, since often people like Wiles are working quietly in the background, and you never know what the true state of the art is. IIRC, Wiles made it his lifes work and it took him about 15 years of patient stalking to get to the answer; even then, he relied on progress made by other mathematicians on other problems which could be applied to Fermat.
Donte Alistair Anderson Roberts - hi son!
Karma: Chameleon
If this is true, it's the best math stuff ever done!!!!!!!!!!!!
Absolutely! Hell, his name is Plotnikov...what other evidence do you need?
"UNIX" is never having to say you're sorry.
Where are the CS grad students in the audience?
You know the CS Grad students, they're the ones who do "First Post".
--
Feminism is the wild notion that women are human beings.
Quoting Introduction to the theory of computation by Michael Sipser:
.sig
Section 7.3:
------------
THE P VERSUS NP QUESTION
As we have been saying, NP is the class of languages that are solvable in polynomial time on a nondeterministic Turing machine, or, equivalently, it is the class of languages whereby membership can be tested in polynomial time.
[...]
P = the set of languages where membership can be decided quickly
NP = the set of languages where membership can be verified quickly
[...]
----- end of quote -----
Actually, his definition of NP is:
------------
DEFINITION 7.16: NP is the class of languages that have polynomial time verifiers.
----- end of quote -----
Finding if a graph has an hamiltonian path is NP complete, but to verify that the path [x] is an hamiltonian path can be done in polynomial time (finding if the path goes through every node exactly once...)
phobos% cat
phobos% cat
cat:
The implications are much huger than that. In fact, if P=NP, then mathematics as we know it is over, to be replaced by a little art and a lot of engineering. Here's why:
Suppose I have a theorem X. I want to know if it's true, and if so, what the proof is. Now, if I have a proof, then I can certainly check it in time polynomial in the size of the proof. Therefore, because P=NP, I can also check in polynomial time whether there is any proof of X shorter than some specified size bound.
Of course, it may be that the shortest proof of X is larger than the specified size bound. But if we set the bound large enough, then we can be pretty confident that no human would ever find the proof. Therefore, by running our algorithm on X and !X, we can get three possible answers:
"Yes, X is true and here's the proof of X"
"No, X is false and here's the proof of !X"
"X may or may not be true, but you'll never be able to prove it either way"
Useful, huh? If the polynomial running time in terms of the size bound is high degree, it might take a while for computers to overtake our mathematicians, but it would happen.
This idea is actually not new. Godel basically posed it to Von Neumann in the 50's --- long before the concepts of P and NP became currrent.
Actually, some undecidable algorithms are also useful in practice. Hindley Milner Type inference is not decidable, and is used in every functional language out there. It only diverges for incorrect programs, for for any correct program you will get a result. Also, it only diverges for a small set of contrived things, so common type errors are a non-issue. For correct problems, it occasionaly gives exponential time, butm again, you have to write a weird (ie. nothing that would occur in practice) example to do that. Most program analyses inside compilers are undecidable, although there some approximation is usually used. If you look at it in one way, even the Halting problem is usable: You simply run the program and you can see after a few minutes if it hangs or not.
The dangers of excessive individualism are nothing compared to the oppressiveness of excessive collectivism
The calculations:
/trold
NP: (2^160)/(2^155) = 2^(160-155) = 2^5 = 32 times as hard.
P: (160^16)/(155^16) = (160/155)^16 = 1.66192932761 times as hard
yes. yes it is.
NOOOOOO!!! This is totally wrong. There is a class of problems that take exponential time, which are harder than NP. And in between, there are PSPACE problems, which take polynomial space (which implies that they aren't in NP, due to the amount of time you spend writning/reading memory, but yet, easier in general than EXPTIME problems, since the amount of memory needed for the latter can be exponential).
For example, satisfiability of propositional modal logic formulas is in PSPACE-- it's harder than NP, but still easier than EXPTIME.
"NP Complete" means that this problem is just as hard to solve as any other NP problem.
More precisely, NP-complete means that all NP problems are polynomial-time reducible to that problem. Thus, there is an algorithm that executes in P, which converts any NP problem into the NP-complete problem.
It's computable, it just grows faster than any function of that form. Think of it as something similar to the way exponential functions are computable but still grow faster than any polynomial function. It's just a lot harder to imagine.
On computability, it gets amusing when you have problems you can't solve even given a machine that solves the halting problem ...
Perhaps I worded that badly.
What I meant was that the transformations often produce PROBLEMS which are polynomially bigger than the source problem. In this case, you should certainly be multiplying exponents. If the time spent transforming does not change the size of the problem (as you guys apparently thought I meant), then indeed you do use O notation and just take the biggest exponent. Maybe I am wrong that the transformations often have this size blow-up, but that's what I recall at least from doing some of these transformations for homework.
IMO there are no NP problems, only NP solutions. There are many problems we can't think of P solution for, but until we know everything there is to know we don't know for sure that there isn't another way to solve a problem.
As x approaches total apathy I couldn't care less.
"NP" means that the problem can be solved by a non-deterministic machine (I'd almost say: For example a human) in polynomial time. A problem is already NP if there's a solution for it.
"P" is part of NP, as even a deterministic machine (like an everyday computer) can solve this in polynomial time.
"NP Complete" means that this problem is just as hard to solve as any other NP problem. If you can solve an NP complete problem in polynomial time, you prove that the whole NP Complete set can be solved in polynomial time, and thus you prove that NP=P.
Of course, there are two possible outcomes:
1. The algorithm has a flaw and won't work.
2. The problem presented was not NP Complete, but only NP or P.
GCS/MU d- s+: a- C++$ USH++$ P- L+> E W++$ N o-- K- W++@ O-- M- !V PS Y+ PGP- t+ 5(+) X- R tv? b++++ y++(+++)
well, there we go. Thanks for the tip.
Nonsense -- there is nothing intrinsically parallelizable about quadratic algorithms versus exponential algorithms.
In fact, the brute force factorization algorithm (just try dividing anything less than sqrt(n)) is just about the perfect parallel algorithm (get a machine for each potential divisor and you can solve really quickly!). This algorithm is exponential in the number of bits of the target number.
Well, Kolmogorov published in 1965, Chaitin in 1969. Some have even pointed out that a 1960 technical report by Solomonoff contains a version of algorithmic information, but the report was reasonably obscure, unlike Kolmogorov's work. Basically, Chaitin gets credit in the West because he wasn't a Soviet. But things are moving it the right direction -- algorithmic information used to be called Chaitin complexity, then Kolmogorov-Chaitin complexity, and now quite often just Kolmogorov complexity.
His name is even Plotnikov! Bahahaha.... god this is funny. "I am Plotnikov! I have many plots, Mr. Bond. Now, die a slow death as my N=NP solution eats away your brain!"
--
As far as I can remember, nobody has proved that Graph isomorphism problem is NP-hard. It is trivially in NP but that's a different thing. Actually many researchers think that graph iso- morphism can be solved in polytime. This means it would in P. This is a conjecture however.
To my surprise, he does seem to be a genuine person (not an april fool invention, etc) and a bona-fide mathematician. A quick search on google shows he's been around a ... so he really does think he has P=NP!? I have an nice'n'dodgy degree in mathematics, and I have to say I'll believe it when it's been seriously peer-reviewed. Of course, if P=NP, all our trapdoor-encryption starts to look a lot more susceptible...
You'd break Brooks' law (which I'd paraphrase as "double manpower, and get 25% of the previous productivity" (for a sufficiently big initial manpower).
Zowie.
MSK
GWBushic?
Are you reading your eight ball again?
No, you can always find an experiment where quantum effects have impact on macroscopic objects. :))
Take Schroedinger's cat or build an interplanetary weapon which either destroys venus or mars, depending on whether a given electron has positive or negative spin. I guess the latter is macrosopic enough (while not really real live
Or take snooker, I read somewhere that after the nth (don't remember n, it was 100, maybe 12) reflection of the ball QM-effects are big enough to make it impossible to precompute the trajectories.
Many problems in real live are not well-posed (or well-behaving, don't know the correct english term from the theory PDEs), which means that the solutions do not depend continuosly from the input data. This means that for these kind of problems we cannot hope that statistic effects smooth out the QM effects.
And this proves that all physical entities are subject to the laws of QM.
But I concede that it would be reasonable to ask whether the human brain has an imminent dependence on QM which is "strong" enough to be measurable for a span of a lifetime.
This is Slashdot; you seriously expect some knowledgeable people in the crowd? This is the place where people say, "Well, I'm not a lawyer, but I read a magazine once, so I feel that makes me qualified to give legal advice."
The initial user community that the web was designed for were physicists who needed a faster and more convenient method for distributing preprints than the academic journal process. Of course, one of the reasons you distribute preprints is so that your peers (or betters :-) can see and review your work, and find errors before you get into the official journal review process.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Rhe question IMNSHO is whether the QM effects _must_ be taken into account when modelling the brain. The always _can_ be taken into account, because of the correspondence principle.
But philosophicaly there is always this non-deterministic "backdoor" of QM-effects.
And I think - without reading Penroses book (thanks for the link, I always liked his writings in scientific american) - proponents of a simpler theory (disregarding QM) should be in charge of showing why their modell is sufficent and not the other way around.
Given the (seemingly non-) progress of AI, cognition theory and others in trying to explain the human brain and self-consciousness I tend to think that new theories might really be required.
Dear Keith,
That's why I don't read vaporware papers. I know what an algorithm is, my research area is algorithms. Anyway, I hope you find these remarks useful; I'll try to be helpful despite your disrespectful attitude.
* heuristic algorithms are also algorithms that have a finite running time. and there are optimal algorithms (preferred to "complete solutions"). heuristic algorithms may be optimal or not. in GP, they are approximate. Actually in all NP-complete problems we try to find approximate heuristic algorithms (because exact algorithms have exponential running time)
* What I'm saying is that, without an accompanying program it is not possible to convince anybody that P=NP including me. (this is most probably just another false proof, or as I said valid only for a special case)
* What I suggest does not require infinite time. He just has to take a couple of graphs at varying sizes, run his program and show that the running time is at worst O(n^6) and that it is indeed optimal.
Please read others' claims more carefully before responding. Your flames may bounce back.
Thanks,
--exa--
Where can I get me one of these "quantum computer" things? Do they have the OS preinstalled?
ok then your [sic] infringing on my copyright! Could you as [sic] me next time before STEALING my comments for your own?
100% of the evidence available at this time points to the conclusion that P does NOT equal NP, and most every CS would tell you that they intuitively believe that P != NP. We just haven't been able to mathematically prove that this is the case.
If this guy was claiming to have proven that P does NOT equal NP I might be interested in reading what he has to say. But since he is claiming that P = NP, I can say, without even looking at his argument, that a mistake has almost certainly been made somewhere.
Well, I guess you all see why the Prof gave me a C in that class.
Hihi. I got a grade (6) similar to a C too. I got "best 5%" on the test, but didn't get the "almost for free" bonus points that you got by writing a report about solving one of the problems in the book with a group of 3 students.
I solved a problem NOT in the book (i.e. a NEW problem) by myself and they didn't give credit for that. I'm a guy who doesn't get upset about that.
Roger.
Isin't this what comments are all about guys? This is it! This is why reading Slashdot is an enjoyable experience!
Undecidable problems are not only not solvable in polynomial time, they're not solvable - ever! If you're interested in this kind of thing, you can try reading Languages and Machines, by Thomas A. Sudkamp. It might be a bit of a struggle if you haven't done any university-level mathematics, though.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
Be careful what you believe!
To give an example: one Slashdot reader posted a solvable problem is in NP. This is not true.
There are other complexity classes than P and NP. Such as PSPACE (problems which can be solved in polynomial space). Problems such as PSPACE problems may not by in NP.
I do not think I have read a comment yet for which the writer sounded like he/she really knew and understood what he/she is talking about. Except of course this one!! :) Because I know I know what I'm talking about...
hahahahhahahahahahahahahahaha!!!!
--
May the source be with you!
--
May the source be with you!
Jason Zwolak
Why wouldn't the existance of a P time algorithm simply show that this particular problem was misgrouped? Your statement is like saying if A implies B, then B implies C. The P = NP problem is discusses on Stas Busygin's NP-Completeness Page. He has good links to his research and published papers. Good resource if you want to know about any of this.
Planning to be moderated ± 1: Bad Pun.
--
Probably no one is reading this any longer, but just in case, I thought that I'd point out a serious, perhaps insurmountable, error in the paper. Theorem 5 is simply incorrect. As he didn't really prove it, I cannot point out a flaw in any proof of theorem 5, but I can, quite simply, give a counter-example. Consider a graph which consists only of a 5-cycle. Any X0 would consist of two non-adjacent nodes. The digraph has to have at least two successive edges which point in the same direction around the cycle (I won't bother proving that because it's very easy to see). This means that any transitive closure graphs of that digraph would contain at least one triangle. Given that there is one triangle, in this case the MPP would be guaranteed to consist of a triangle and a line. This fits the definition of a VS graph because any maximum antipath has size two (the same as the number of paths in the MPP), which is the same as the size of X0, and must be a maximal independent set of the transitive closure graph. However, since a triangle is always included in the MPP and one edge of every triangle is always non-essential, there is no possible MPP of the TGC which contains only essential arcs. So the theorem clearly does not hold on a 5-cycle! I sincerely doubt that this is a single exception. I'm quite certain that if need be, I could find many more counter-examples, but one is sure to suffice. Keith
I can probably remind people of a little stuff.
It's probably easiest to think of this stuff in terms of Turing Machines, any problem can be expressed according to a TM which solves it. Input to a turing machine can be sized according to the number of squares on the tape it takes to represent the input. For an input of size n, the time complexity function of a turing machine (or algorithm which it computes) is defined as the maximum number of steps it takes the TM to halt (if it does) ranging over all inputs of size n. Considering all possible input sizes we end up with a function C(n) which maps positive integers to positive integers.
A problem is said to be within the class of complexity P if there exists a (deterministic) Turing Machine having complexity function C(n) and a polynomial function p(n) such that for all n C(n) < p(n). Otherwise the problem is said to be in complexity class NP.
Factoring integers is an NP problem, note that the Shor's polynomial time algorithm for use on a Quantum Computer is non-deterministic.
An NP-complete problem is one that firstly is in NP, and secondly is one in which for every other problem in NP there is some TM or algorithm which takes a polynomial number of steps to restate it in terms of the NP-complete candidate. (Moreover the solution to this problem provides a solution to the second one.)
So to solve P = NP the author needs to show first of all it's NP-complete. Which may or may not have been shown elsewhere, a lot of these graph partition problems have subtle but important differences, and secondly provide a polynomial time algorithm to solve it.
I am of the opinion that NP = P (or not) is one of the hardest problems in mathematics and really needs some brilliant new theories to be solved, so I'm sceptical but I'll read the paper.
:wq
The best you could do, is transform your O(n^1260) algorithm running on one processor into an O(n) algorithm running on (n^1260) processors. Even if you built self-replicating computers, n^1260 of them (for n>1) is likely to chew up a fair bit of space and energy . . . :)
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
Right! It's just conjectured to be so. Primality testing and/or factoring is a weird beastie since the verification string length is not linear in the length of the input string.
NP is defined as the class of decission problems that can be verified by a TM in polynomial time (or defined in other ways that are equivalent).
:).
Factoring is not a decission problem, so it is not immediately in NP. Some non-decission problems
can be rewritten as one by testing against a result (is there a solution for the traveling salesman with a total length of less than K, for any constant K). If solutions are integral then having this allow binary search for the real answer
Factoring is not a decission problem. The corresponding decission problem is whether a number is a composite, and it is in NP since a proof consisting of the proposed factors could be checked in polynomial time. The opposite problem, whether a numer is prime, is in co-NP (the complement of NP... the problems where a counterexample can be checked in polynomial time).
Oddly, Primality is also in NP. It's a very ingenious trick that allows you to have a proof of primality that can be checked in polynomial time.
That means that Compositenes is also in co-NP.
IF compositeness or Primality were known to be
NP-hard, then we would know that NP=co-NP, which we don't.
I'm Stas Busygin, the holder of the site where the paper was published. First of all, thanx to all for the attention. Please take a look at my publishing policy to avoid any misunderstanding. Besides, please use the mirror in the U.S. as my main server in Ukraine is overheated!
Nah I spent a week screaming when told to go away and write my own web server
I am a CS grad. student, working on state-of-the-art heuristic solutions for graph partitioning and related problems, which are NP-complete. Our approximate solutions are slightly superlinear, like in Kumar & Karypis's work.
The thing is we don't present an algorithm without an experiment that verifies its running time in such prominent problems. Let him run this on arbitrary graphs, verify correctness and running time, then I may have some time to read his paper. Probably solves only a special case by the way as I looked at various representational transformations.
Thanks,
--exa--
I quote the paper : Let there be a graph G=(X,Gamma), where X is the set of graph vertices, and Gamma is a map X into X. A map means that to each element of X, another element of X... and only one (or else it's not a map, it's a relation). If i'm not wrong, this guy solves the problem of the partition into cliques for graphs with only one edge leaving each vertex, which i hope is polynomial !!
Keep in mind also that "nondeterminism" in this context means much more than just "can't predict the system's behaviour". It has a much more exacting definition than that - to a first approximation imagine a program that can, whenever it needs to make a decision, executes a fork() call, and continues executing simultaneously down both paths, either one of which can find the answer.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
And the following is true too:
In Soviet Russia, Jesus asks: "What Would You Do?"
I don't even look at these anymore. Well, I would if someone wrote a program that started actually solving these problems. That would be truly excellent. The reason I don't look at them is, as explained by my advisor, is they are an incredible time suck. Since this is a holy grail, lots of reasonably talented people give it a spin. And it never pans out. And it takes a huge ammount of time to figure out what the subtle error in their logic/proof is. Put another way, I know lots of people that will happily take a $10 -> $1k bet that your discovery won't be blessed by a tier 1 journal in 5 years time or less. I'm one of them. Part of the reason for the extreme skepticism is that thousands of brilliant people have tried to come up with a solution to this problem. This is because all NP problems are polynomially transformable to each other, and there are lots of very useful real world problems that are NP. Ergo, some (or all) of the best practicing algorithmers have tried and failed to get an efficient exact algorithm for this problem in their own very well understood (to them) subdomain. Not holding my breath (but I'd love to eat crow on this, as would every other OR practitioner). See Gary & Jhonson for all the gory details.
If Mr Roca is correct (and I think he might be) the consequences of P=NP are far bigger than I think anyone else in this discussion has stated.
Whether he is correct or not is also worthy of discussion.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
This could have huge implications for cryptography. If P=NP, then that means that any problem that has been proven to be in NP can be solved in polynomial time. One good example is factoring, which is generally believed to be in the class of problems that aren't NP-hard, but still aren't in P.
So if P=NP, then RSA breaks.
Probably all public key cryptography breaks.
Secret key cryptography is probably still fine, though. Of course, those secret keys are usually exchanged using public key algorithms.
Scary.
Not a clip tie. can't see the clip (yet can see the edge of his collar). tie just below know is twised a bit (moreso than any clip tie would be). Just a pretty good, tight knot.
... the sensational claims made this time two years ago? Five years ago? Ten years ago?
The proof of Fermat's Last Theorem turns out to be valid. The original proof had holes in it and it took several people several years to fill it.
But what about the 14 year-old Irish girl who discovered something or rather about encryption. Remember her, from a couple of year ago? Where is she now? What happened to her research?
Cold fusion?
High temporature superconductor?
Do we remember the then "Next Big Thing" before Linux? Before the Web? Was it OS/2?
--
IIO
-- Weiqi Gao weiqigao@speakeasy.net
In my opinion, I feel that P!=NP. There are too many problems (eg. in combinatorial optimization) where there is no useful heuristic that guarantees the right answer.
You can find a description of their algorithm formaximum flow in a network (which
presumably is what the paper is about, since its title is Flows in Networks) in basically
any algorithms book. Ex. Cormen Leiserson Rivest, Introduction to Algorithms.
Hmmmm .... Greg Chaitin's work on algorithmic information theory suggests that there may be more of a link between the time taken by a omputer to solve a problem and "those fucked up Goedelian things" than any of us currently suspect.
-- the most controversial site on the Web
As someone else has mentioned, this guy looks like an evil mastermind from a James Bond movie. I believe that this guy's evil scheme to create an RSA-factoring algorithm for classical computers that runs in polynomial time and then hold intercepted informatian and broken passwords for ransom. Then, he will build a fleet of spaceships to colonize the moon. Damn, 007, where are you??
---
GetSystemMetrics(SM_SECURE) == FALSE
NP-hard problems don't actually have to be in NP. I like to think of NP problems as those such that if you were given a solution, you could verify the solution in polynomial time. But there are some problems for which this is not the case, and yet it is still true that you could reduce any problem in NP to this problem.
Forgive my ignorance, but although I understand what P, NP, and NP-complete mean, I'm not sure I know what NP-hard is and how it differs from NP-complete. Anyone care to enlighten me?
I hear a lot of people say that proving P = NP is an immediate devastating blow to cryptography.
This algorithm purports to solve a particular NP complete task in O(n^6). I don't believe it, but let's pretend it's possible.
Calculating the discrete logarithm modulo M (RSA is based on this being difficult) for binary numbers is certainly in NP (it's poly time to verify the answer once you find it). So we can transform any instance of the discrete log problem into a min clique problem, then solve it in O(n^6), then transform it back. These transformations often involve passing through other NP-complete problems (graph coloring, three coloring, three-sat, circuit-sat, algorithm-sat is a common pathway). These transformations usually incur a nontrivial amount of polynomial time (ie, they are in O(n^2) or O(n^6) or something).
Therefore, even if this works, solving the discrete log problem or factoring would probably still be in something like O(((((n^2)^7)^3)^5)^6) time! It's polynomial, sure, but O(n^1260) is NOT fast. (For a 4096-bit key, that poly time solution is MUCH WORSE than a brute-force guessing attempt, even ignoring multiplicative factors lost in O-notation). I just pulled these numbers out of my ass, but it's likely that it would turn out that way.
Of course, the insights gained from a P time solution to any NP-complete problem might be enough to eventually topple certain kinds of cryptography. But don't go delete PGP or GPG because of this claim (which probably isn't valid, anyway); the problem of P vs NP is more of an intellectual curiosity than a practical concern.
Moderating, bah.
Its pretty funny and interesting.
I mean I took it as a funny joke about grad students having lots of time on their hands and having nothing better to do but to troll around. Totally opposite image of people who could explain the question of P=NP? question and the article in question.
Offtopic? Hardly.
The surprise isn't how often we make bad choices; the surprise is how seldom they defeat us.
Humans can not solve NP problems in polynomial time (unless P=NP). NP essentially means a correct solution could be verified in polynomail time, while P means a correct solution can be found in polynomial time.
I'm an "almost" graduate in CS. I always had the feel that P NP. Too many people had worked many years in finding polinomial time solutions for problems that are very simple to describe. If an eficient solution exists we already should have found it. I'll read de paper and give it to some people I know that work on complexity theory.
MOD THE CHILD UP!
I am a CS grad, and I remember during the course I did on Complexity our professor (who was slightly unhinged) gave an excellent quote when speaking on this subject. He said that if you ever did find a p-time solution to a NP complete problem (e.g. proving P=NP) then you'd better be prepared to run very fast - every government security agency in the world will be after you.
---- Den ene knappen er powerknapp, den andre er Bender voice knapp "Bite My Shiny Metal Ass"
Ok, so I majored in CS not math (or "maths" as some of our friends across the pond like to call it.) but here is my $0.02.
Showing that a problem is NP complete is a pretty easy. IIRC, you just have to show that there is an isomorphism between your problem and another NP complete problem. This is the sort of problem they threw at us in the undergrad algorithms class I took. I don't know the details of this particular problem, but I'm guessing if more than one reputable mathmatician says its NP complete, then it probably is.
I personally (and with no real basis except for a general hunch) think that P!=NP. At least I hope that it isn't. If I had to hazard a guess, I'd say that it is much more likely that there is a problem with their algorithm than their proof that this problem is NP complete.
spreer
The P=NP problem has been the death of many a young researcher because it is such a hard problem and there are many subtleties involved in such a proof. Every year there are genuinely smart people who propose a proof one way or another and it requires a significant amount of peer review and analysis to spot the mistake in their proof. After this, of course, they get shunned for wasting everyone's time for submitting a bad proof, even though it took a large number of man-hours to spot the flaw. There are many interesting "proofs" out there right now for which I am interested in learning the results. A very respected proof theorist this summer submitted a proof in the major logic conference in Paris this summer. He claims that the P=NP problem is independent of the Peano axioms (Something that I have long since believed, but never tried to prove). This means that any proof either way about this question would require very high level techniques from set theory, and that standard CS combinatorial arguments are not enough. So, I suggest that we just sit back and wait for each of these to be peer reviewed. Either way, the answer should be very interesting.
I have to admit, I feel a lot better responding to a troll with:
you are dividing by zero between lines 4 and 5;
than the usual:
-1: Troll.
Congratulations.
--
--
E_NOSIG
The definition is indeed correct. NP-complete problems can indeed be solved in poly-time by a non-deterministic machine (such as a quantum computer). I don't think human brain is non-deterministic though. (?) The statement "NP complete problems can be verified in poly-time" is a simplified definition.
___
___
If you think big enough, you'll never have to do it.
I really haven't a clue about this NP and P stuff. Here I am thinking about transistors! Silicon, that's where it's at... Anyone know where I could find some GENERAL information on what this thread is about? I gather it is about equations or something of the like... I think this time it is just out of my league.
Russian Russian Russian RussianDollSig DollSig DollSig DollSig
OK, after reading these two posts, I think I have a better idea of P, NP, and NP-complete. But I have one question...
you just have to show that there is an isomorphism between your problem and another NP complete problem
So what was the first NP complete problem?
Well, you mean Kolmogorov's work on algorithmic information theory that Chaitin likes to claim credit for, despite publishing essentially identical work to Kolmogorov *years* after him?
Graph isomorphism is no worse than NP-complete, and it's not even known to be that hard; you likely mean subgraph isomorphism. Further, electrical networks have particular characteristics, and they are not designed so as to give rise to hard isomorphism problems.
This is a general characteristic. It's true that useful heuristics exist for many hard problems. For example, "random" boolean satisfiability problems are almost always easy to solve using simple search methods. But the hardest instances of satisfiability are totally intractable using these methods. And for applications like factoring, reduction to a problem such as satisfiability yields very hard instances.
David
with an assertion that if there exists an x such that x + y = x + z then y = z. This is just addition of real numbers we're talking about.
Alternatively, you could just declare that the value of a nonterminating decimal is the limit of the series and the whole problem goes away.
I can see that this is the kind of problem that leads to flamewars, so I'm eschewing my +1 for the protection of my precious karma.
--
--
E_NOSIG