What is a problem

The first step to construct a general problem solver is to define what “problem” means .

There are 2 different groups of problems , in the first group we have a complete definition , in the second we know only a partial definition.

The most frequent is the first group . A simple example is the sorting problem . In this case we know what we want to obtain a sorted list of objects so we know the constraint for the list where every object must be <= of its successor. This description (usually known as specification of the problem) is itself a program and we can write it as ” for each possible list of objects the result is the sorted list”. The program directly defined by the specification usually is exponential and absolutely useless to solve practical problems so for this group solve the problem mean to find the temporal/spatial conversion of the problem. This is more easy than second group but in many cases is not absolutely easy .

In the second group we have all the partial defined  , all the problems where we must find its definitions . A classic example is sequence prediction where given a sequence  of bits like “01010101” we must predict the next bit value.  In this case we must find first the best “specification” , the best program that fit the data and then we can operate like in the first group.

In all these 2 groups a problem is always defined as a program so to solve a problem means translate the “problem program” to the “best available program” .

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 )

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