Welcome to MSDN Blogs Sign in | Join | Help

Eric Lee

Thoughts on Agile development, Scrum, ALT.NET, and whatever else comes to mind.
Software Development is NP-hard

Here’s one more thought on the subject of complexity in software development: software development is NP-hard.

Software development (in the sense of building large projects end-to-end) has these characteristics:

  1. A proposed solution can be easily proved correct or not correct.
  2. The cost of searching for the correct solution grows exponentially as the problem set grows in size.
  3. There are no known shortcuts that make the process of searching for the correct answer dramatically easier.

What’s the best way to deal with NP-hard problems?

Successive approximation and heuristics.

Posted: Thursday, September 17, 2009 1:51 PM by Eric Lee

Comments

Alan Pretre said:

Formal methods have been developed, such as Z (see http://formalmethods.wikia.com/wiki/Z and http://en.wikipedia.org/wiki/Z_notation), but a large system must be broken down into smaller components and analyzed.  Proving the correctness for all but the most trivial algorithms is VERY difficult.

Testing, while useful, is not PROOF that a system is correct.  As we say, testing can show the presence of bugs, but not the absence of them.

# September 23, 2009 11:36 AM
Leave a Comment

(required) 

(required) 

(optional)

(required) 

  
Enter Code Here: Required

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Page view tracker