WHITE PAPERS SPONSORED PROFILES JOB BOARD WEBINAR CENTER FREE SOFTWARE BZ RESEARCH ALMSHAREPOINT EVENTS CALENDAR PRINT/PDF EDITION PRINT/PDF BACK ISSUES

SUBSCRIBE TODAY CUSTOMER SERVICE EDITORIAL CALENDAR EDITORIAL BEATS GUEST VIEW GUIDE SD TIMES 100 GUIDE EVENTS CALENDAR ADVERTISING ARTICLE REPRINTS REPORT A BUG SITE MAP

ABOUT US BZ MEDIA NEWS BZ RESEARCH NEWS ON MONDAY SPTECHREPORT SPTECHWEB SPTECHCON IPHONE/IPAD DEVCON ANDROID DEVCON PRIVACY POLICY CONTACT US

HOME >> ZEICHICK'S TAKE

Zeichick’s Take: Thinking in polynomial time

By Alan Zeichick

October 19, 2009 — “The Status of the P Versus NP Problem” is the title of an excellent paper in September’s Communications of the ACM. For many developers, it may be a look at the world you live in, where solving complicated problems in a reasonable amount of time may be easy—or it may be difficult. For others, it’s a rare peek into the world of algorithmic computer science.

My own state is somewhere in the middle. I clearly remember studying the classes of problems deemed NP—non-polynomial time as I think of it, but more properly defined as nondeterministic polynomial time. However, that was a long time ago.

P problems—those solvable in polynomial time—are generally easy to code. NP problems aren’t. They seek to do tasks like determining if a large integer is prime, or finding the absolute best way to load a delivery truck with odd-sized packages, or working out the gravitational paths of multiple objects. Generally speaking, NP problems can be only solved in exponential time, and often the solution can be verified in polynomial time. (It might take years to factor a 512-bit number, but you can verify in a couple of nanoseconds that the factors are correct simply by multiplying them together.)

The CACM paper, by Lance Fortnow, a professor at Northwestern University’s McCormick School of Engineering, discusses the ancient question: Is there a way of transforming NP problems so that they can be solved in polynomial time? In other words, does P = NP? (If I remember my computer science correctly, there is a hypothesis that says that if any NP problem can be transformed into a P problem, then all NP problems can be so transformed.)

Should we find out that P = NP, then a whole range of problems will become easier. Long-range weather forecasting is an NP problem. Wouldn’t it be nice to solve? On the other hand, public-key encryption only works because the factoring of very large integers is an NP problem. If P = NP, then the underpinnings of today’s best crypto algorithms will be washed away.

In a nutshell, it still seems that P ≠ NP. However, there is no proof one way or another. As Prof. Fortnow says, the question is still open. There’s a lot more to the subject; I recommend reading the paper. You’ll enjoy it; at least, I did.

Alan Zeichick is editorial director of SD Times. Follow him on Twitter at twitter.com/zeichick. Read his blog at ztrek.blogspot.com.

Related Search Term(s): polynomial time

Share this link: http://sdt.bz/33845

Most Read Latest News Blog Resources

Zeichick’s Take: Radio moves from analog waveforms to digital packets
Streaming radio highlights the need for streaming applications to be designed to take up as little bandwidth as possible

Taking enterprise architecture to the business side
Startup Corso is bringing out a cloud-based planning platform that ties into business plans

Appcelerator Acquires Cocoafish to Add Instant Mobile Cloud Capabilities to its Industry Leading Titanium Platform
Appcelerator Offers Messaging, Social, Location and Storage Mobile Cloud Services to All Mobile App Publishers

ComponentOne Releases a Collection of 40+ UI Widgets Powered by HTML5 and jQuery
ComponentOne has announced the 2012 release of Wijmo: a kit of UI widgets for HTML5 and jQuery development

Taking enterprise architecture to the business side
Startup Corso is bringing out a cloud-based planning platform that ties into business plans

Top five apps to manage your workload
Web applications offer new ways to track your “to-do” lists

Not so fast when it comes to testing in the cloud
Developers face outsourcing, virtual lab management and mobile devices as obstacles

Xceed releases UX-focused suite for Microsoft’s WPF
"Blendables" helps match user experiences to developer visions

Are you at risk for burnout?
Burnout is a severe problem and it can strike at any time. Here's how to tell if you are nearing the edge.

Agility, mom, and apple pie
If we're to evaluate the state-of-the-art in software development, we should start with the values espoused in the Agile Manifesto.

RIM woos developers with free tablet
How do you get more apps ported to the BlackBerry PlayBook? By giving every developer a free tablet, of course!

GitHire: Use Headhunters to Find Your Perfect Programmer
Are you a hiring manager tired of scouring the job boards? Check out this new service that will find 5 people interested in your jobs.

The Hidden Costs of Software Licensing Moving beyond paper-based software licensing to more flexible, software-based licensing is a business decision. There is a growing trend tow...

Case Study: You May Need a Development Mechanic As a contractor for a major financial player in Germany, SOBEGE, a German-based consultancy specializing in embedded IT and web services, wa...

Ensuring Software Quality at a Major International Bank One of the world’s leading international banks has adopted AgitarOne technology for delivering generated unit tests for their Java software...

Load Testing Adobe Flex Applications Adobe Flex applications may be different from applications you’ve worked with before. For classic HTML web applications, the server does all...

Technorati

Digg

Slashdot

Facebook

Friendfeed

Twitter

del.icio.us

Escaping from the “How Long?” time trap A solid agile implementation requires good time-management and time-tracking skills, which can be hard to develop

Short Takes: December 15, 2008 The editors ponder why Sun can't seem to dominate the market despite all of its valuable assets, how warranties can be a good thing, the dearth of cable providers in New York City and the departure of PC Magazine form the world of print.

Time may be up for design-time governance When it comes to efficiency, design-time SOA development doesn't seem to be the best option. Fortunately, if you are using design-time SOA, there are steps you can take to mitigate these problems.

Add comment

Name*
Email*
Country

Comment

Escaping from the “How Long?” time trap
A solid agile implementation requires good time-management and time-tracking skills, which can be hard to develop Read More...

News on Monday
more>>
SharePoint Tech Report
more>>

Download Current Issue
FEBRUARY 2012 PDF ISSUE

Need Back Issues?
DOWNLOAD HERE

Want to subscribe?

Are you at risk for burnout?
Burnout is a severe problem and it can strike at any time. Here's how to tell if you are nearing the edge.
02/09/2012 02:16 PM EST

Agility, mom, and apple pie
If we're to evaluate the state-of-the-art in software development, we should start with the values espoused in the Agile Manifesto.
02/07/2012 11:57 AM EST

RIM woos developers with free tablet
How do you get more apps ported to the BlackBerry PlayBook? By giving every developer a free tablet, of course!
02/04/2012 01:57 PM EST

GitHire: Use Headhunters to Find Your Perfect Programmer
Are you a hiring manager tired of scouring the job boards? Check out this new service that will find 5 people interested in your jobs.
02/03/2012 12:17 PM EST

Facebook claims hacker cred
Facebook's SEC S-1 filing form includes a short essay on the Hacker Way by Mark Zuckerberg himself.
02/02/2012 08:26 AM EST

Ryan Dahl steps down
Ryan Dahl, creator of Node.js, steps back from his position as gatekeeper for the project.
02/01/2012 04:58 PM EST