Most Votes
- What's the highest dollar price will Bitcoin reach in 2024? Posted on February 28th, 2024 | 8480 votes
- Will ByteDance be forced to divest TikTok Posted on March 20th, 2024 | 7433 votes
Most Comments
- What's the highest dollar price will Bitcoin reach in 2024? Posted on March 20th, 2024 | 68 comments
- Will ByteDance be forced to divest TikTok Posted on March 20th, 2024 | 20 comments
Electronics (Score:5, Informative)
That is to say, P != NP, but instead n[i] = n*p.
What the...? (Score:4, Funny)
Re:What the...? (Score:5, Informative)
Re:What the...? (Score:5, Funny)
Wikipedia is your friend. It's a classic, unresolved computer science problem.
Thanks for the heads-up. As an EE, I thought it was about semiconductor doping, but the formula felt wrong.
Re:What the...? (Score:5, Funny)
Oh, how wonderful. You just caused several cases of spontaneous cerebral detonation here with that link.
Thanks a lot, you insensitive clod!
Re:What the...? (Score:4, Funny)
Nonsense (Score:5, Funny)
Re:What the...? (Score:2, Funny)
Re:What the...? (Score:2, Informative)
NP stands for the set of problems that can't be solved in polynomial time. These problems take an exponential amount of time to solve, so usually can't be solved within a reasonable amount of time by a computer. NP problems frequently used for encryption. F
Re:What the...? (Score:5, Informative)
P = Polynomial time
NP = Nondeterministic Polynomial Time
NP-Complete = The class of problems to which all problems in the set of NP problems can be reduced in polynomial time. 3-SAT is NP-Complete, as are all problems to which it can be reduced.
P vs NP is the famous conjecture.
NP problems can be solved on computers. They are theoretically "intractible," which is to say, their worst-case computational time complexity is exponential. There are other intractible classes, such as pspace and co-np, to name a couple. That said, there are SAT solvers out there (http://www.satlive.org/ [satlive.org] that do, in fact solve 3-SAT. Most instances, in fact, can be easily solved. Ones that cannot be easily solved fall near the "phase transition."
Re:What the...? (Score:2)
NP problems can be solved on computers. They are theoretically "intractible," which is to say, their worst-case computational time complexity is exponential.
I'm sure you meant "can't" - they can (they're computable), but it takes far too much time with any but the most trivial input.
But their worst-case computational time complexity is unknown. That's the whole issue the poll is about! If P=NP, then there is a polynomial complexity solution to these problems. If one NP-complete problem can be proven to ha
Re:What the...? (Score:2)
Re:What the...? (Score:2)
Think of a simple 3-SAT boolean proposition.
Ok. We know that checking the proof of such a proposition is poly time. How? You simply set all of the variables and then check that the proposition is true. If it is true, then it is satisfiable.
So, how many combinations of boolean variables are there?
Well, if we have 3, there are 8! 2 * 2 * 2 (two values for each of 3 variables).
So, that means that the complexity can be stated as O(2^n)...
I know exactly what t
Re:What the...? (Score:3, Insightful)
Re:What the...? (Score:2)
Re:What the...? (Score:2)
Bad example, because factorisation is not shown to be NP-complete. I believe the fastest factorisation method (the general number field sieve) actually has a better running speed than the best algorithm for, say, satisifiability. Bruce Schneider says in Applied Cryptography that GNFS runs in sub-exponential time, but not in polynomial time. AFAIK the best solution for satisfiability (wh
Re:What the...? (Score:5, Informative)
Close, but not entirely true. Allow me to explain. The class that a problem falls into only describes how the time required to solve it grows as the size of the problem increases. For instance, if a problem is linear and you can solve a problem of size n in time p, then you will be able to solve a problem of size 2n in time 2p.
Now consider another algorithm that can solve the problem in quadratic time. It can solve a problem of size n in time q and a problem of size 2n in time (2q)^2 = 4q^2.
You now know that, whatever the numbers p and q are (as long as they're > 1), there is some multiple of n for which the first algorithm will be faster than the latter. However, for all smaller values, the second one may actually be faster, even though it is of higher complexity. (For instance, take p = 10000, q = 1, n = 1 and a problem of size 2n. The first algorithm takes 2*1*10000=10000 units to solve the problem, while the second takes only (2*1*1)^2=4 units.)
To give an example: a professor of mine once invented a new algorithm that solved a very difficult problem in polynomial time. Even though this was a significant find (I believe it even made it into Knuth), everybody still uses the exponential algorithm. The reason for this is that the exponent, while constant, is so monstrously big that the algorithm will take forever even to solve the smallest of problems.
The same thing can happen with P=NP. We may someday find an algorithm that can solve an NP problem in P time, but with an exponent that is so humongous that it has no practical application whatsoever. In that case public key encryption will still be in the same situation that it is today: breakable, but not in a practical amount of time.
Re:What the...? (Score:2)
Not all problems that can be solved in exponential time are NP. In order to be NP, it needs to be something that can be verified in p
Re:What the...? (Score:5, Funny)
Re:What the...? (Score:5, Informative)
Re:What the...? (Score:2)
-Lars
Re:What the...? (Score:3, Insightful)
Re:What the...? (Score:5, Informative)
I believe that optimization problems are usually converted to yes-or-no questions: 3-SAT reduced to Travelling Salesman doesn't ask "What is the shortest path the salesman can take?", but "Can the salesman take a path shorter than X?"
If the solver gives you a path, it's easy to check and see whether it hits all the stops and has a total length less than what you're looking for. (I don't remember how you check if the solver says "No such path exists"; I want to say that NP only applies to problems where positive solutions can be checked quickly, and there's some other category for negative solutions, but it's been a while....)
There are usually polynomial-time methods to solve the optimization problem, given a yes-or-no solver. Travelling Salesman, for example, you could do a kind of binary search on X to find the length of the shortest path, then start removing edges from the graph and asking the solver if the path is still possible--if you remove an edge and the solver starts saying "no", then that edge must have been in the path.
Re:What the...? (Score:2)
Then again, maybe the high vote is a protest of th
Re:What the...? (Score:5, Insightful)
NP and quantum computers (Score:2)
Re:NP and quantum computers (Score:2)
I don't know enough about quantum computation to know how this relates to computational complexity. I would imagine, however, that the quan
Re:NP and quantum computers (Score:2)
Re:NP and quantum computers (Score:5, Informative)
If it is NP-Hard, this is not true.
Actually it is. If a problem is NP-hard but not known to be NP-complete, and we then find a polynomial time algorithm for it, then that problem is now known to be within NP, and thus is NP-complete by definition. As a result this would also prove P=NP.
The crux of the matter is that NP-hard problems are at least as hard as NP-complete problems (in that all NP-complete problems are reducable in polynomial time to NP-hard problems), if you solve an NP-hard problem in polynomial time, then you can solve all problems in NP in polynomial time.
see http://en.wikipedia.org/wiki/NP-hard [wikipedia.org] and http://en.wikipedia.org/wiki/NP-complete [wikipedia.org] for more details
Re:NP and quantum computers (Score:2)
Re:NP and quantum computers (Score:2)
Re:NP and quantum computers (Score:2)
Re:NP and quantum computers (Score:2)
Re:NP and quantum computers (Score:2)
Re:NP and quantum computers (Score:2)
Integer factoring is certainly in NP, as every problem in P is in NP. What you mean is that it is considered to be NP-hard - that is, any problem in NP can be reduced to factoring.
However, it isn't believed to be NP-hard. There are known algorithms for factoring that are super-polynomial but sub-exponential, so it would be quite surprising if it were NP-hard. In fact, it is one of only a few known natural problems that can be solved in better than exponential time, but aren't known to be in P.
In pure c
Re:NP and quantum computers (Score:2)
Firstly what you are talking about is the Church Turing thesis (every problem is reducable to a previously solved problem or by definition is unsolveable) and there are a few that can't be reduced to primes off the top of my head the big three of Halting Problem, Busy Beaver and Travelling Salesman can't be reduced to Prime based factorisation and still require a non-deterministic programming language.
Re:NP and quantum computers (Score:2)
However, AFAICT, nobody's even attempted to answer your question!
If it is possible to solve any NP-Complete problem in polynomial time, it is possible to solve NP-Complete problems in polynomial time, because eve
Re:NP and quantum computers (Score:2)
Re:NP and quantum computers (Score:2)
Re:NP and quantum computers (Score:2)
quantum computers (Score:2)
Quantum computers are known to solve certain classes of P problems slightly faster than their classical counterpart.
Showing that a quantum computer can s
Re:NP and quantum computers (Score:2)
A=NE (Score:5, Informative)
Affect
1. affect (transitive verb) [Middle English, from affectus, past participle of afficere]
to produce an effect upon, as a: to produce a material influence upon or alteration in b: to act upon (as a person or a person's mind or feelings) so as to bring about a response; influence
Effect
1. effect (noun) [Middle English, from Middle French & Latin; Middle French, from Latin effectus, from efficere to bring about, from ex- out (of) + facere to make, do]
1a: purport; intent b: basic meaning; essence
2: something that inevitably follows an antecedent (as a cause or agent)
3: an outward sign; appearance
4: accomplishment; fulfillment
5: power to bring about a result; influence
6 plural: movable property; goods
7a: a distinctive impression b: the creation of a desired impression c (1): something designed to produce a distinctive or desired impression, usually used in plural (2) plural: special effects
8: the quality or state of being operative; operation
I know, I know, I'll mod myself down; give me a sec.
Re:A=NE (Score:2, Redundant)
Effect is also a verb.
"it won't effect me in the slightest" means something like "it won't play even the slightest role in causing me to exist", I guess.
Re:A=NE (Score:2)
I voted for this one. I know enough about the subject to recognise the question, but not much more. However, I'm pretty sure CowboyNeal isn't in either N or NP. I'm also fairly certain that the answer (to human knowledge) is neither Yes nor No. I'm also fairly certain that it hasn't been shown to be undecideable (if that even has meaning in this context). The remaining option, correctly parsed [reference.com] above [slashdot.org] as "it will play no role in creating me", is true (I already exist, as far as I am aware).
I'm being a
Re:A=NE (Score:2)
Especially in the case of the poll, the incorrect use of "effect" in place of "affect" causes (effects, if you will) a vastly different interpretation of the que
Re:A=NE (Score:3, Insightful)
Undecidable = nonsense option (Score:2)
One might, of course, speculate about the existence of a proof for P = NP. Of course, if P = NP, then a proof is certain to exist. The most tantalizing situation would be if, in fact, P != NP is true but not provable.
Re:Undecidable = nonsense option (Score:2)
Depends on if you are willing to accept paradox. Otherwise, your system of logic must be incomplete. If incomplete, there will be true statements which can not be proven.
Re:Undecidable = nonsense option (Score:2)
That being said, it's not clear to me why there necessarily would be a proof for P=NP if it were true, but maybe I'm just missing the obvious.
Re:Undecidable = nonsense option (Score:3, Informative)
Re:Undecidable = nonsense option (Score:2, Interesting)
"Of course, if P = NP, then a proof is certain to exist."
I'm not so sure of this. Suppose P=NP. Then for any NP-complete problem, say 3SAT, there is a finite algorithm that solves any instance of the problem in polynomial time. We could write down such an algorithm. It may indeed be the case that for any instance of 3SAT of length n the algorithm correctly decides satisfiability in time n^10. BUT...
We may have no way to prove that the algorithm is always correct, even if it is.
We may have no way
A couple fun P?=NP pages (Score:2)
And, here's a reminder of the monetary value associated with proving this http://www.claymath.org/millennium/P_vs_NP/ [claymath.org]
By the way, there's more money in it for you if you show that P=NP. There's another prize, but I don't know the link.
Re:A couple fun P?=NP pages (Score:2)
Probably not the one you're thinking of, but I think we can quite safely say you'll get one of these [nobelprize.org]. Think it comes with some cash as well.
True iff N = 1 or P = 0 (Score:3, Funny)
The Know-It-All (Score:5, Funny)
As he is so smart, he generally feels his time would be better spent in the pub than in lectures (which I can sympathise with). But he still likes to ask me what we did in each Algorithms and Data Structures lecture as the lecturer doesn't make the notes available online.
So one day, I tell him that we did the Travelling Salesman problem, oh and the lecturer would like us to prove, in our own time, whether P=NP.
"Oh yeah, I've done it before. It does."
I told him should really submit that proof. Gotcha.
Come on guys... (Score:2)
Re:Come on guys... (Score:2)
(1)"(E)xGx"
or: (2) "it is not the case that(E)xGx"
Meaning that it is either the case, as in (1) or not the case, as in (2) that there exists an "x" and that that "x" is God
Although because "I exist" is a well formed claim it does kind of undermine that one a bit... (but don't tell Kant
Another poll about this (Score:5, Interesting)
- True - 9
- False - 61
- Undecidable - 8
- CowboyNeal - 22
Since there have conveniently been about 1000 votes about now, these numbers can be scaled up as follows:- True - 90
- False - 610
- Undecidable - 80
- CowboyNeal - 220
And for the visually minded, this would look like this:p = np (Score:5, Interesting)
and...
this is the requisite Wikipedia entry on what this all means [wikipedia.org]
Personally, I had my crazy days, thinking I could write an algorithm to make solve NP problems in P time.
Re:p = np (Score:3, Insightful)
That's actually kind of a litmus test for me. In undergrad, all of my friends tried the exact same thing, but none of the "get rich through coding!" students ever bothered. In other words, every single student who was genuinely interested in their studies believed that they were the clever one who would come along and solve it out of the blue. People who believed the instructor and moved along to th
Missing option (Score:2, Funny)
P=NP=NI (Score:2)
If Poll = No Poll
Then No Poll = No Ideas.
Maybe it's time to ask for poll suggestions?
This is depressing (Score:4, Interesting)
Re:This is depressing (Score:5, Informative)
Not true at all. Even if such algorithms aren't provably unbreakable, there will still be online transactions. People aren't going to give up convenience just for some abstract mathematical concepts. Yeah, so given enough computational power your credit card number can be extracted from the SSL stream. It's still an intractable amount of computing power. And as computers get faster, we can just add more bits to the key.
The cryptography may not be perfect, but it is (and will remain) good enough. It'll still be way more secure than handing your card over to the waiter at a restaurant and having him disappear into the back room for a few minutes to scan it. The overwhelming majority of the population, myself included, will consider it an acceptable risk.
I stand by my vote of "It won't affect me either way." I'm confident that regardless of whether or not "P=NP" can be proven or disproven, my way of life won't change in the slightest. The only effect it will have on me is that it might make an interesting bit of bathroom reading when the announcement hits Science News.
Re:This is depressing (Score:5, Informative)
Re:This is depressing (Score:2)
Say, tomorrow someone finds an algorithm which solves the factorization problem for N-bit numbers in N^64 seconds. That's clearly a polynomial time algorithm. However for a 1024 bit key, you'd still need 1024^64 = 4.56*10^192 seconds. Given that age of the universe is about 4.7*10^17 seconds, this would still amount to about 10^175 times the age of the universe. Doesn't sound too mana
Re:This is depressing (Score:2)
That may be the most practical provably secure system, but it isn't the only one. Schneier's "Applied Cryptography" mentions the Rip van Winkle cipher for example. This cipher is guaranteed to be secure for an arbitrary period of time x, but it requires x^2 time before the legitimate recipient can read the plaintext.
Original paper:
J.L. Massey and I. Ingemarsson, The Rip van Winkle cipher - a simple and provably computationally secure cipher with a
Re:This is depressing (Score:5, Insightful)
That is if:
a) There's an actual formula, not just an existance theorem.
b) You can find a transformation that maps your problem to a solved problem.
c) The constant factor isn't out of reach (100000000000000000000000000000000000000000000000
d) The exponent isn't out of whack (n^10000000000000000000 is polynominal).
What's theoretically possible has nothing to do with what's practicly feasible. A polynomial could still take until the sun burns out and then some to complete.
Re:This is depressing (Score:3, Informative)
No, you're describing the way things are now. If a proof of P==NP is shown to be valid, factorization will be achievable in polynomial time, i.e. with *tractable* computing power.
Re:This is depressing (Score:3, Informative)
Until and unless P=NP is proven true. Right now the intractable amount of computing power comes from the fact that there's no non-exponential way to search keyspaces - adding a bit adds twice as many keys to brute force, and there's no way to apply computations from previous brute force
Don't be depressed (Score:2)
Re:Don't be depressed (Score:2)
Re:This is depressing (Score:2)
P=NP explained in simple words (Score:3, Informative)
P and NP are both classes of problems. Each problem in P and NP can be solved by a computer; for each problem there is only a limited number of possible solutions. The problems in P can be solved with few effort. NP is a little bit more tricky: Each solution for a NP-problem can be validated with few effort; but until now there is no way to solve such a problem without huge amounts of effort.
There is a very simple but also very expensive way to solve a NP-problem: You just try to validate each possible solution. While it is very easiy to validate one soultion for a NP-problem, it becomes quickly very expensive to test every possible solution. The qustion is, whether there is a better way than trying every possible solution. Or in other words: When it is easy to validate a solution, is it also easy to calculate the soultion? This question is also referenced as "P=NP".
Until now, there was no way to simplify one of the NP-problems, so it could be easily solved. But when somenone would be able to do this for one NP-problem, this would help to simplify (most of) the other NP-problems. (Cryptographic problems are usually seen somewhere between P and NP, so they might not be affected.)
Re:P=NP explained in simple words (Score:4, Informative)
NP is the class of problems, where solutions can be easily validated. This does include every problem in P. (If the solution can be easily calculate, it can also be easily verified : just calculate the solution and compare).
NP contains P. NP contains also some problems who are "NP-complete". NP-complete problems are problems in NP. And if one of these (NP-complete) problems has an easy solution, ALL problems in NP (including public-key encryption) can be easily solved.
One of my favorite Futurama jokes (Score:3, Interesting)
Utility (Score:3, Insightful)
1) If you can reduce ONE inherently difficult problem (NP) to a simple problem (P), then it can be proven that all NP problems are reducible to P problems.
2) If you prove that P=NP, it does *nothing* to actually help you solve an individual NP problem. That is to say, proving that a difficult problem is reducible to a simple one does nothing to actually help you solve the difficult problem.
Sorry folks, I'm an astrophysicist, not a mathematician!
SEP field... (Score:2)
Tsk. Tsk. Ignorant people are so arrogant.
Hint: If you rely on cryptography (e.g. if you use banks), and P=NP were true, then you would definitely be affected!
you forgot to initialize P and NP (Score:3, Funny)
For the majority who think they'll be unaffected.. (Score:4, Interesting)
If P=NP then public key cryptosystems become crackable in polynomial time. So if you use such an encryption scheme (for example, to carry out credit card transactions over the web) you will certainly be affected.
For example, RSA assumes that factoring is hard. But if P=NP then factoring is in deterministic polynomial time, so RSA is easily cracked.
A hacker who proved P=NP and kept it to himself could carry out larceny and fraud on a grand scale.
Notes for the confused: Recently prime testing has been shown to be in deterministic polynomial time. While that was a breakthrough, prime testing was already known to be in random polynomial time and is a much easier problem than factoring. Factoring can be done in quantum polynomial time, but no quantum computer with more than a few bits has been built. When people finally figure out how to engineer a quantum computer with several hundred bits, RSA will be dead. But that still doesn't imply QP=NP, since factoring isn't believed to be NP-complete anyway. A proof that P=NP would be the most radical development in mathematics in over a century.
Re:For the majority who think they'll be unaffecte (Score:2)
A proof that a solution exists doesn't necessarily mean that you have an explicit solution (although giving a solution of course is a proof that a solution exists). That is, it might happen that someone gives an indirect proof that P=NP, but still doesn't know how to construct a single polynomial algorithm for any problem which wasn't yet known to be in P. And of course, having a polynomial algorithm doesn't i
Re:For the majority who think they'll be unaffecte (Score:5, Funny)
That you know of.
BWAHAHAHAHAHA
Feels True (Score:2)
It could just be that I want it to be true, but in most cases that would be the same thing.
True, False and Undecidable (Score:2)
It's true (Score:3, Funny)
What do you mean? (Score:3, Funny)
P != NP -- Solved (Score:3, Funny)
-Bill
Re:wow thats geeky (Score:2)
All NP-complete problems can be solved in exponential time: enumerate the (exponential) number of possible solutions, and test each of them, which by definition requires polynomial time. n! (factorial) time is even slower.
Classical computer science says that if P=NP, then all problems in NP can be solved "trivially", but the speed of polynomial algorithms is an issue as well. If your NP-complete problem can be solved in n^20 time, does it really matter in the real world? Polynomial time bounds are not n
Roadblocks... (Score:4, Funny)
Ah yes! But you'll have to get by the mathematicians who say "Ni!"
Re:Roadblocks... (Score:3, Funny)
Re:wow thats geeky (Score:2)
If you want to prove that P != NP then yes. If you want to prove that P == NP, then all you need to do is to come up with an efficient solver for the travelling salesman problem. That is down to laymen's terms. The popular conjencture is that there isn't one though, so it's probably like fermat's last theorem - simple question, horribly difficult answer, and the answer is no.
Re:Capt. Obvious answers (Score:2)
Re:Capt. Obvious answers (Score:2)
Re:Capt. Obvious answers (Score:5, Funny)
Re:Capt. Obvious answers (Score:2)
Re:The million dollar question (Score:2, Funny)
But that's easy! P=NP exactly when P=0 or N=1. Now to get my million dollars...
Re:The million dollar question (Score:2)
Re:Booooooring... (Score:2)
Mod parent UP! (Score:2)