Tractability

CSC385

Why study tractability?

To gain experiential insight to this question, carry out the following assignment.

1.

Download this Visual Basic program and run it for the following inputs:

ab

abc

abcd

abcde

. .

abcdefghi

2.

Analytically estimate its run time for the following inputs:

abcdefghijklmn

abcdefghijklmnopqr

abcdefghijklmnopqrstuvwzyz

3.

Download this Visual Basic program and run it for the following inputs:

abcdefgh

abcdefghij

4.

Analytically estimate its run time for the following inputs:

abcdefghijklmn

abcdefghijklmnopqr

abcdefghijklmnopqrstuvwzyz

5.

What is the difference between the two programs?  How does that account for the difference in run times?

6.

What is the runtime Big-O classification of GenPerms?

7.

What is the space usage Big-O classification of GenPerms?

Introduction to Tractability

It is required of a professional in any field to know the limits of our present capabilities in that field.  This is also the case in the IT profession.  If we know what can and cannot be accomplished with computing machinery, we will not be as likely to waste scare resources of time, money and manpower on quixotic ventures.  Among the most important constraints on our abilities are those imposed by problems related to tractability, commensurability and computability.  We will consider these in turn.

We begin our discussion with tractability.  Dictionary.com defines tractable and intractable thus:

tractable \TRAK-tuh-bul\, adjective:
Capable of being easily led, taught, or managed; docile; manageable; governable; as, tractable children; a tractable learner.

Tractable derives from Latin tractabilis, from tractare, to handle, to manage, frequentative of traho, to draw, to drag.

http://dictionary.reference.com/wordoftheday/archive/2000/07/27.html

intractable \in-TRAK-tuh-buhl\, adjective:
1. Not easily governed, managed, or directed; stubborn; obstinate; as, "an intractable child."
2. Not easily wrought or manipulated; as, "intractable materials."
3. Not easily remedied, relieved, or dealt with; as, "intractable problems."

Intractable is from Latin intractabilis, from in-, "not" + tractabilis, "manageable," from trahere, "to draw (along), to drag, to pull."

http://dictionary.reference.com/wordoftheday/archive/2002/07/23.html

In computer science, a programming task is considered to be tractable if it can be accomplished in a reasonable period of time or with a reasonable supply of physical resources (usually space).  Otherwise it is intractable.  The study of tractability has a theoretical and a practical aspect, yielding theoretical and practical definitions of terms.

The field of computer science known as Analysis of Algorithms has developed the Big-O notation for categorizing the time and space requirements of various programming tasks/problems.  The most often used categories are:

          O(1) ::          constant

          O(log n) ::    logarithmic

          O(n) ::          linear

          O(n log n) ::  linearithmic

          O(n^k) ::         polynomial

          O(bⁿ) ::         exponential

          O(n!) ::          factorial

To these we add two which are of theoretical interest.

          O(nⁿ) ::          polyexponential

          O(2^2^2^ . . ^2), where the number of exponentiations is n ::    

                             Ackermanial

Further Exercises

Exercise 1:

Assume that in the near future you have a 100 gigahertz desktop machine.  Assume also that the key processing step requires only one machine cycle of time.  For what values of n would each of the Big-O categories yield a run time that exceeds 1 second?  1 day?  1 year?  1 millennium?

Some computer scientists give a theoretical-only definition of tractability, i.e., a task/problem is tractable iff its Big-O classification is sub-polynomial.  If it is exponential, or worse, it is intractable.  Unfortunately, this definition ignores the fact that exponential algorithms can be useful and are, in fact, used.  Here is a utilitarian definition.  A task/problem is tractable-in-practice if an answer can be obtained in a useful period of time.  Otherwise it is intractable-in-practice.

Exercise 2:

Which of these tasks in tractable-in-practice?

1. You are in charge of graduation ceremonies.  Generate a listing of all possible seating arrangements for the 600 graduates.

2. You are in charge of the custodial staff.  You have 9 buildings and 9 custodians.  Generate a listing of all possible assignments of custodians to buildings, with one per building.

3. You are in charge of the University intramural basketball program.  Fifty students have signed up.  Generate (but do not print) a listing of all possible 5 person squads.

4. You are in charge of the University intramural basketball program.  1100 students have signed up.  Generate (but do not print) a listing of all possible 8 person squads.