ΑΠΟΔΕΙΧΘΗΚΕ ΟΤΙ P!=NP

August 11, 2010 at 6:43 pm (ΕΠΙΣΤΗΜΟΝΙΚΑ ΝΕΑ)

http://cacm.acm.org/news/97397-p-%E2%89%A0-np-its-bad-news-for-the-power-of-computing/fulltext

ACM News

P ≠ NP? It’s Bad News for the Power of Computing

New Scientist

August 11, 2010

Has the biggest question in computer science been solved? On 6 August, Vinay Deolalikar External Link, a mathematician at Hewlett-Packard Labs in Palo Alto, California, sent out draft copies of a paper External Link titled simply “P ≠ NP”

This terse assertion could have profound implications for the ability of computers to solve many kinds of problem. It also answers one of the Clay Mathematics Institute’s seven Millennium Prize problems, so if it turns out to be correct Deolalikar will have earned himself a prize of $1 million.

The P versus NP question External Link concerns the speed at which a computer can accomplish a task such as factorising a number. Some tasks can be completed reasonably quickly—in technical terms, the running time is proportional to a polynomial function of the input size—and these tasks are in class P.

If the answer to a task can be checked quickly then it is in class NP.

So if P = NP, every problem that can be checked quickly can also be completed quickly. That outcome would have huge repercussions for Internet security, where the difficulty of factorising very large numbers is the primary means by which our data is kept safe from hackers.

1 Comment

  1. Λυκόφρων said,

    Φτου!

    (Μπορούμε να πούμε τίποτε άλλο; )

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: