Reductibility is the property of a domain which is more complex than some knowledge to describe it.

The concept, in its principle, can be illustrated by an example:

Consider the following string: "11111111111111111111111111111111111".

Consider a possible method to generate it: "write 35 times the character 1".

It can be seen in this example that the method can be described with a smaller amount of information (30 characters) than the string itself (35 characters).

In practice, reductibility usually seems to stand for smaller complexity; but this "merit" must be balanced by the fact that some kind of cognitive engine is then required.

See also: