Factoring numbers is NOT in NP-complete. It is an NP-hard problem. It's one of those NP problems whose "certificate" is not linear in the size of the input.
So you are right, a proof that P=NP doesn't necessarily tell you how to solve any NP-complete problems
in polynomial time
Actually you can from the get go. NP-complete is closed under transitivity, so if you find a P solution of an NP-complete problem, you are pretty much done since the composition of two polynomial time reductions is itself polynomial! So, the proof of P=NP could definitely provide a direct solution, just compose the sequence of known reductions.
When I was an undergrad there, I noticed that the US Air Force was the largest grant supporter of the department. So, we're not exactly talking about consumer products. That's funny since most of these guys are peaceniks, (Fred Brook's banned shooting games on PixelFlow) but will gladly take the money.
Re:I'm a Maths Graduate but ...
on
Does P = NP?
·
· Score: 1
Yes, evaluating Ackermann's function comes to mind. It's VERY bad. See Cormen, Leiserson, and Rivest, Algorithms, pp 451-453.
Re:NP Non-deterministic Polynomial
on
Does P = NP?
·
· Score: 1
Yeah, usually, there is an unsaid understanding that the input representation is not in unary. But, all other base representations produce equivalent complexities. So, unary is almost always considered "unreasonable".
Re:NP Non-deterministic Polynomial
on
Does P = NP?
·
· Score: 1
It's also worth noting that a sufficiently parallel machine is equivalent to a nondeterministic
one, for this kind of stuff.
No. The amount of parallel speedup is fixed, so it can't handle an arbitrary problem. So provide a machine, and I'll provide an input that is much larger...
Re:This is an incorrect definition of NP
on
Does P = NP?
·
· Score: 1
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.
The thing is that binary gates are much easier to build. Slam a gate shut or slam it open...(sorry for the physical analogy), much easier than making something "stop" at some just right place.
I know what he's saying. But, since the entropy of the universe isn't infinite, there is room to compress a representation. Of course, I can't suggest a way of doing this because we aren't sure of the the model should look like. Such a model needs to be able to provide all the information about an atom at time t or some other parameter. But, atoms don't have infinite entropy (if they did, we wouldn't be talking about them). So, take a salt crystal. The sodium ions within that crystal are quite similar (just a characteristic of crystals).
The real problem is what level of precision do we settle on. Many (if not most) models rely on irrational numbers. I don't know if anyone has a good idea on how to represent them exactly using any computational method (of course, we are out of the realm of Turing machines. So, to be able to do this, a more powerful class of abstract machine is needed).
If you're talking about exact models, forget about it.
From what I've seen, ONLY hard drive companies consider 1 kilobyte to be 1000 bytes. Makes you wonder why (sorta a sneaky way to sqeeze by the fact that actual storage space is less than the storage capacity due to directory info).
Don't the Brits consider "giga" to be 100x larger than what american-speakers use?
First of all, I hate dirty optics. This includes any layer of glass that I have to read through. So why they heck do I want to read small text on a sheet of glass with fingerprints all over it??
The thing about voice interaction, or any other form of poorly defined interaction is ambiguity. Try to build ANY context-free language that understands any plain english and you'll quickly realize that it's not context-free. Even if we were to somehow create an incredibly smart interpreter on the computer-end, typing '1' means exactly that, but speaking "one" could be a different story.
Besides, typing ';' is so much damn faster than saying "semi-colon". I'd hate to dictate C code.
It's also the damn local (or regional) telcos. Having being so used to local monopolies, they are accustomed to screwing their customers. After I got my Mindspring/Covad aDSL, which, depending on the server, gives me 200kB/s consistently. Ameritech tried VERY hard to sell me their DSL service. Around the Chicago area, the old established utilities are VERY hated. Now that SBC bought (merged?) Ameritech, complaints have only gone up!
I don't know if this is just marketing BS, but Mindspring supposedly refuses new accounts until they are able to handle the extra traffic.
Plus, some of these images were processed not for visual quality (to humans) but for edge quality (to edge detectors). You'd think that they would add the captions and titles after all of the image processing!
I don't know how feasible this is, but couldn't a nonintrusive profiling methodology be created that tallies the POSIX calls on a variety of machines? For example, we use the generic categories {web server, file server, computer server, blah...} and randomly select a sample of machines in the real world that fit these categories. It seems to me that most of these benchmarks model very ideal conditions. What I'd like to know is what real world sequences of system calls under various loads do to the OS's. Then, we can actually apply a weight or score to each individual "ideal" test for a category of use.
Of course, finding volunteers to run this "nonintrusive" profiler on their production machines might be hard! My point is, there may be very strong interactions between the various types of system calls that a simple benchmark will overlook. I'm sure something like this is in the literature, but if so, why hasn't it been used in academic circles?
Slashdot Mirror
Factoring numbers is NOT in NP-complete. It is an NP-hard problem. It's one of those NP problems whose "certificate" is not linear in the size of the input.
Actually you can from the get go. NP-complete is closed under transitivity, so if you find a P solution of an NP-complete problem, you are pretty much done since the composition of two polynomial time reductions is itself polynomial! So, the proof of P=NP could definitely provide a direct solution, just compose the sequence of known reductions.
Why is this such a big deal anyway? I'd bet that the only new thing coming out of this is another approximation algorithm, which is nothing new.
Does anyone know the proof or reduction to the venerable 3-SAT for Minesweeper?
Not too many alternatives to Maple, but Octave is a rather good replacement for Matlab.
When I was an undergrad there, I noticed that the US Air Force was the largest grant supporter of the department. So, we're not exactly talking about consumer products. That's funny since most of these guys are peaceniks, (Fred Brook's banned shooting games on PixelFlow) but will gladly take the money.
Yes, evaluating Ackermann's function comes to mind. It's VERY bad. See Cormen, Leiserson, and Rivest, Algorithms, pp 451-453.
Yeah, usually, there is an unsaid understanding that the input representation is not in unary. But, all other base representations produce equivalent complexities. So, unary is almost always considered "unreasonable".
No. The amount of parallel speedup is fixed, so it can't handle an arbitrary problem. So provide a machine, and I'll provide an input that is much larger...
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.
The thing is that binary gates are much easier to build. Slam a gate shut or slam it open...(sorry for the physical analogy), much easier than making something "stop" at some just right place.
The real problem is what level of precision do we settle on. Many (if not most) models rely on irrational numbers. I don't know if anyone has a good idea on how to represent them exactly using any computational method (of course, we are out of the realm of Turing machines. So, to be able to do this, a more powerful class of abstract machine is needed).
If you're talking about exact models, forget about it.
Ever heard of compression? The universe hasn't reached infinite entropy...yet.
Don't the Brits consider "giga" to be 100x larger than what american-speakers use?
Dr. Who made some same crazy gizmo with a cup of tea once, literally. Maybe all this thing needs is a sonic screwdriver!
I thought that Ultrix was DEC Unix for a while...? At least that's what I saw above the login prompts on some very old DECs.
Just curious what the previous tasks were.... Anyone have last year's info?
The thing about voice interaction, or any other form of poorly defined interaction is ambiguity. Try to build ANY context-free language that understands any plain english and you'll quickly realize that it's not context-free. Even if we were to somehow create an incredibly smart interpreter on the computer-end, typing '1' means exactly that, but speaking "one" could be a different story.
Besides, typing ';' is so much damn faster than saying "semi-colon". I'd hate to dictate C code.
It's also the damn local (or regional) telcos. Having being so used to local monopolies, they are accustomed to screwing their customers. After I got my Mindspring/Covad aDSL, which, depending on the server, gives me 200kB/s consistently. Ameritech tried VERY hard to sell me their DSL service. Around the Chicago area, the old established utilities are VERY hated. Now that SBC bought (merged?) Ameritech, complaints have only gone up! I don't know if this is just marketing BS, but Mindspring supposedly refuses new accounts until they are able to handle the extra traffic.
Well, announcing a merger with "Destron Fearing" doesn't help either.
Plus, some of these images were processed not for visual quality (to humans) but for edge quality (to edge detectors). You'd think that they would add the captions and titles after all of the image processing!
Of course, finding volunteers to run this "nonintrusive" profiler on their production machines might be hard! My point is, there may be very strong interactions between the various types of system calls that a simple benchmark will overlook. I'm sure something like this is in the literature, but if so, why hasn't it been used in academic circles?
At 1.2M watts (assuming MWh), it'd cost over $100 an hour to keep running. ComEd would love me...
They just don't come that way in real life!