Software Development is NP-hard

(I originally posted this on my MSDN blog.)

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.

 

Advertisements

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.