Forgot your password?

P=NP

Displaying poll results.
True
  5153 votes / 12%
False
  9706 votes / 23%
Undecidable
  9435 votes / 23%
Either way won't affect me in the slightest
  11383 votes / 27%
== CowboyNeal
  5232 votes / 12%
40909 total votes.
[ Voting Booth | Other Polls | Back Home ]
  • Don't complain about lack of options. You've got to pick a few when you do multiple choice. Those are the breaks.
  • Feel free to suggest poll ideas if you're feeling creative. I'd strongly suggest reading the past polls first.
  • This whole thing is wildly inaccurate. Rounding errors, ballot stuffers, dynamic IPs, firewalls. If you're using these numbers to do anything important, you're insane.
This discussion has been archived. No new comments can be posted.

P=NP

Comments Filter:
  • Electronics (Score:5, Informative)

    by PM4RK5 (265536) on Monday March 27, 2006 @02:47AM (#15001134) Homepage
    Generally, in doped semiconductors, n[i]^2 = p*n, where n[i] is the intrinsic carrier concentration of the semiconductor at a given temperature T, and p and n are the concentrations of positive and negative carriers in the doped slicon. So for p-type, p >> n, and in n-type, n >> p.

    That is to say, P != NP, but instead n[i] = n*p.

    ... but that's probably not what the poll was shooting for.
  • by tahii (758556) on Monday March 27, 2006 @02:47AM (#15001136) Homepage Journal
    Let me be the first to ask, what the heck does P=NP mean anyway?
    • Re:What the...? (Score:5, Informative)

      by Nasarius (593729) on Monday March 27, 2006 @02:49AM (#15001145)
      Wikipedia [wikipedia.org] is your friend. It's a classic, unresolved computer science problem.
    • by Anonymous Coward
      Leave your nerd badge at the door.
    • Re:What the...? (Score:2, Informative)

      by arevos (659374)
      In a nutshell, P stands for the set of problems that can be solved in polynomial time, which roughly equates to all problems that can be solved by a computer. For instance, multiplication of two integers is a problem that can be solved in polynomial time.

      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)

        by NitsujTPU (19263) on Monday March 27, 2006 @03:39AM (#15001283)
        I've been resisting the urge to correct people, but yes, there is a mistake.

        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."
        • 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

          • Nope. I meant that NP problems CAN be solved by computers. 3-SAT is NP-Complete. There are a number of solvers that solve these problems, and the instances are certainly non-trivial. There is a great deal of research on this topic. There are "hard instances" and instances that haven't been solved, but I have, installed on my computer, several pieces of software that solve NP and P-Space complete problems, such as minisat, walksat, and quaffle.
            • Also, their worst case complexity is well known.

              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)

                No, you know what the worst case complexity for that particular algorithm is. If P = NP turns out to be true, that means you could reduce this problem to one in P and solve it in poly time.
          • The part that isn't known is the presence of a poly-time algorithm. Sorry, missed that part in my answer.
      • "For instance, working out the prime factors of an integer is a problem that can't currently be solved in polynomial time."
        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)

        by Gorath99 (746654) on Monday March 27, 2006 @09:38AM (#15002566)
        If P = NP is proved, the results would be profound. All public key encryption would be made virtually useless, which would make online security rather more difficult.

        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.
      • 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. For instance, working out the prime factors of an integer is a problem that can't currently be solved in polynomial time.

        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
    • by maxwell demon (590494) on Monday March 27, 2006 @07:50AM (#15001936) Journal
      Either P=0 or N=1.

    • Re:What the...? (Score:5, Informative)

      by bunratty (545641) on Monday March 27, 2006 @08:15AM (#15002039)
      Basically, P is the set of problems that can be quickly solved. NP is the set of problems that can be quickly checked to see if you have the correct answer. If P=NP, that means that if you can quickly determine if an answer is correct, you can quickly solve the problem.
      • Please mod parent up! This is the most succinct explanation of the P=NP problem I have ever seen.

        -Lars
      • Re:What the...? (Score:3, Insightful)

        by St. Arbirix (218306)
        How do you prove that the answers you are given for the travelling salesman and the knapsack problem are the correct in P time?
        • Re:What the...? (Score:5, Informative)

          by Chrondeath (757612) on Tuesday March 28, 2006 @09:45AM (#15010471)
          How do you prove that the answers you are given for the travelling salesman and the knapsack problem are the correct in P time?

          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.

    • Ignoring the spelling error, I am stunned at the number of people from this supposedly nerdy crowd who selected "won't affect me" option. If P = NP, then you better freaking damn well believe it will affect all of us much more than slightly. Previously intractable problems will be reduced to simple ones and lots of things that couldn't be done before will be done (somewhat) trivially. Whole new fields of application in software and hardware would come about.

      Then again, maybe the high vote is a protest of th
    • Re:What the...? (Score:5, Insightful)

      by FalconZero (607567) <FalconZero@[ ]il.com ['Gma' in gap]> on Monday March 27, 2006 @01:18PM (#15004358)
      Of course P=NP, the poll creator used the assignment operator '='. The correct answer is therefore 'true'
  • If I remember correctly factoring numbers into their primes is considered to be NP, but can be done in P time on a quantum computer. Does this imply that all or only some NP problems can be computed in P time on a quantum computer, for example if all NP problems could be shown to be related to prime factorization then we could safely assume they could all in theory be done in P time on a quantum computer. If not, and some problems are still infeasable even with a quantum computer then NP should br re-divi
    • The complexity class of integer factorization is unknown. If it were NP-Complete, a polynomial time algorithm that solves it would mean that P=NP. If it is NP-Hard, this is not true. The reason that this is true of NP-Complete problems is by defininition. NP-Complete problems are problems to which it is known that all problems in NP have a polynomial time reduction.

      I don't know enough about quantum computation to know how this relates to computational complexity. I would imagine, however, that the quan
      • Actually I know a little about quantum computers from "A Shortcut Through Time", and in that book Shor's algoritem is presented as a way break a number into prime factors on a quantum computer. However because of the way the computer acutally works you can't simply run any calculation in parallel with its self, only ones specially designed so that the wrong aswers "cancel out" on the quantum level while the correct answers reinforce each other. Thus because the problem space which quantun computers can wo
      • by bradkittenbrink (608877) on Monday March 27, 2006 @03:38AM (#15001279) Homepage Journal

        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

    • 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


    • 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.
    • As previous posters have said, you're not quite getting the difference between "NP Complete" and "NP Hard" (which is often used in the loose sense to describe problems whose hardness is unknown, but usually at least as hard as NP Complete - its sort of like self-assigning an "X" rating to a movie).

      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
    • Prime factorisation is in P, actually - see M. Agrawal, N. Kayal, and N. Saxena, "Primes is in P", Annals of Mathematics, 160 (2004), 781-793.
      • I think you might be confusing primality with prime factorization. Those are different problems, in the firt one the problem is "is this integer a prime number?". In the second one the problem is "what are the prime factors of this number?".
    • P is a set of problems that can be solved quickly on a classical computer. NP is a set a problems that have solutions that can be checked quickly on a classical computer. Or a set or problems that can be solved quickly on a non-determinstic computer. A ND computer will branch out in different computing threads. All these threads are computed at the same time. As a deterministic computer can only process one thread at a time. Generally speaking we can achieve a non-deterministic model in computers by having
    • I hope this clarifies your questions a bit: Factoring numbers into their primes isn't known to be NP, but there are compelling reasons to think it is. This can be misleading, since at some point it was thought that finding if a number was prime (a different problem) could be NP, but it was shown that it was in fact P. So, it is still an open question.

      Quantum computers are known to solve certain classes of P problems slightly faster than their classical counterpart.

      Showing that a quantum computer can s

  • A=NE (Score:5, Informative)

    by michaelar (252189) on Monday March 27, 2006 @03:01AM (#15001172) Homepage
    *Sigh*. C'mon, guys, you're making us look bad.

    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)

      by Scarblac (122480)

      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.

    • by Ibix (600618)

      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

  • Undecidability is a property of sets (or boolean functions). A set is undecidable if there is no algorithm for deciding if a given element is in the set. For a single yes-no question such an algorithm trivially exists, because either print("yes") or print("no") is sure to do the job.

    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.
    • "Of course, if P = NP, then a proof is certain to exist."

      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.
    • Undecidability, in this context, is probably supposed to mean that the question is independent of ZFC (using "normal" logic, one might add).

      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.
    • "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

  • Here's a page that I enjoyed a while ago that I'm sure others would like http://www.win.tue.nl/~gwoegi/P-versus-NP.htm [win.tue.nl]
    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.
    • 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.

      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.
  • by Per Abrahamsen (1397) on Monday March 27, 2006 @03:18AM (#15001220) Homepage
    This field intentionally left almost blank.
  • by wizzdude (755000) on Monday March 27, 2006 @04:10AM (#15001363)
    My former lab partner likes to act as if he knows everything.

    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.
  • Everybody knows that P=NP is the Proof or NonProof of the existance of GOD!

    • I thought that was easy (in correct logical grammar).... all you have to do is reject both the subject and the predicate

      (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 ;))
  • by caffeination (947825) on Monday March 27, 2006 @04:48AM (#15001459)
    In a 2002 poll of 100 researchers, 61 believed the answer is no, 9 believed the answer is yes, 22 were unsure, and 8 believed the question may be independent of the currently accepted axioms, and so impossible to prove or disprove.
    This is:
    • 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:
    True
    xxxxx
    False
    xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
    Undecidable
    xxxx
    CowboyNeal
    xxxxxxxxxxx
  • p = np (Score:5, Interesting)

    by philipkd (528838) on Monday March 27, 2006 @05:46AM (#15001600) Homepage
    The Clay Institute will give you $1 million if you can prove any of the first three. [claymath.org]

    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)

      by Just Some Guy (3352)
      Personally, I had my crazy days, thinking I could write an algorithm to make solve NP problems in P time.

      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

  • by aurb (674003)
    == "Breasts!"
  • P=NP
    If Poll = No Poll
    Then No Poll = No Ideas.

    Maybe it's time to ask for poll suggestions?
  • This is depressing (Score:4, Interesting)

    by metternich (888601) on Monday March 27, 2006 @09:20AM (#15002409)
    As of this post, over half of /. says it is either undecidable or it won't effect them in the slightest. As to the first group, just because a problem hasn't been solved in 30 years doesn't mean it's undecidable. Fermat's Last Theorem was unsolved for 400 years. While it's true that undecidable theorems exist, there is absolutely no reason to believe that P=NP is one of them, (or really any other thing that you would care about for that matter.) As to the second group, if P=NP it will effect you in very major ways. All Public Key encryption relies on one-way functions, (ie. functions that are difficult to invert without the private key.) If P=NP, then you can say goodbye to online credit card payments, PGP, etc., etc.
    • by Chelloveck (14643) on Monday March 27, 2006 @09:44AM (#15002620) Homepage
      As to the second group, if P=NP it will effect you in very major ways. All Public Key encryption relies on one-way functions, (ie. functions that are difficult to invert without the private key.) If P=NP, then you can say goodbye to online credit card payments, PGP, etc., etc.

      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.

      • by metternich (888601) on Monday March 27, 2006 @11:02AM (#15003303)
        It seems like you have a poor understanding of Public Key Crytography. The only method that is truely secure is a one time pad. Shannon proved this decades ago. Public Key methods wrok becuase people they currently require an "intractable amount of computing power." (In other words, if someone with super computer worked on your key for a very long time or got very lucky, they could break it.) If P=NP, then an algorithm exists to break keys using a tractable amount of computing power. (That is, I could break your key in two seconds on my desktop.)
        • I don't know where you get those 2 seconds from. It certainly doesn't follow from the hypothesis of factorization being in P.

          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
        • "The only method that is truely secure is a one time pad."

          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
        • by Kjella (173770) on Monday March 27, 2006 @01:35PM (#15004482) Homepage
          If P=NP, then an algorithm exists to break keys using a tractable amount of computing power. (That is, I could break your key in two seconds on my desktop.)

          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 (1000000000000000000000000000000000000000000000000 00*n is linear).
          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.
      • by volpe (58112)
        eah, 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.

        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.
      • by merlin_jim (302773)
        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.

        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
      1. Those who think it's undecidable are saying they think there's a fundamental discovery right around the corner. I think that's pretty cool.
      2. If someone manages to solve an NP-complete problem in O(n^1000) time, then that's not going to break PGP.
      • It could be an O(n^1000) algorithm, but then again it could be much faster. For almost every problem that has been solved in Polynomial time a quick way to solve the problem ( n^3) has also been found.
  • by geggo98 (835161) on Monday March 27, 2006 @09:44AM (#15002618) Homepage

    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.)

    • by TekGoNos (748138) on Monday March 27, 2006 @04:42PM (#15006196) Journal
      While your explanation is nice, you do mix up NP and NP-complete.

      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.
  • by ari_j (90255) on Monday March 27, 2006 @10:46AM (#15003156)
    In a closet there are two books on a shelf. One is entitled "P" and the other is entitled "NP." Evidently they are completely disjoint.
  • Utility (Score:3, Insightful)

    by Pi_0's don't shower (741216) <ethan.isp@northwestern@edu> on Monday March 27, 2006 @11:08AM (#15003360) Homepage Journal
    Although the P=NP question is remarkably interesting from a mathematical standpoint, i.e. whether an inherently difficult problem can be reduced to a simple one, there are two well-known things that can be said about it that I'd like to point out.

    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!
  • "Either way won't effect me in the slightest"

    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!

  • by WillAffleckUW (858324) on Monday March 27, 2006 @11:31AM (#15003545) Homepage Journal
    they're both null pointers, actually.
  • by J.R. Random (801334) on Monday March 27, 2006 @11:35AM (#15003574)

    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.

  • Most have voted P != NP, but I voted P == NP because it "feels" true.
    It could just be that I want it to be true, but in most cases that would be the same thing.
  • The real choices should be Provable, Disprovable, and Undecidable. If it's undecidable there are no counter-examples, so it is true.
  • It's true (Score:3, Funny)

    by 1110110001 (569602) <slashdot-0904.nedt@at> on Monday March 27, 2006 @01:52PM (#15004623)
    Of course it's true. As long as N = 1. Or P = 0. If my math tests had been that easy ...
  • by Tumbleweed (3706) * on Monday March 27, 2006 @03:26PM (#15005414)
    African or European?
  • by wdr1 (31310) * <wdr1@pobox.TWAINcom minus author> on Wednesday March 29, 2006 @02:21AM (#15016219) Homepage Journal
    I have discovered a truly remarkable proof of this, but the margin of Slashdot is too small to contain it.

    -Bill

Never try to teach a pig to sing. It wastes your time and annoys the pig. -- Lazarus Long, "Time Enough for Love"

 



Forgot your password?
Working...