Один з найвидатніших математиків минулого століття Джон фон Нейман вважав, що теорія складності є “передумовою до розуміння процесів навчання та розвитку”, та що “поняття складності, незважаючи на його prima facie кількісний характер, може висловлювати в дійсності дещо якісне – мати принципове значення”.

Слід розрізняти складність та “важкість”. Проблема чи річ може бути “важкою” до розв’язання, але не обов’язково складною (головоломки в більшості своїй є важкими до розв’язання, але не складними). Різниця між цими поняттями полягає в тому, що складна проблема, зазвичай, має велику кількість розв’язань, і ці розв’язання мають багато призначень, що не в останню чергу викликане слабкою структурованістю та багатобічністю складних проблем та метою їх розв’язання.

Складність є взаємодією та взаємною залежністю, причому залежності складових системи є симетричними зі змінною інтенсивністю. Для складних об’єктів властива множинність системних образів, тобто один і той же об’єкт допускає різні системні моделі, що відповідають його різним сторонам та різному ступеню глибини проникнення в об’єкт.

Складність виявляється також і в динамічній поведінці системи. Не можна стверджувати, наприклад, що глибина природи фізичних процесів принципово стохастична, тому що механізм, що породжує невизначеність, може бути й детермінований процес. Прикладом може бути система, в якій наявні і функціональні, і матеріальні складові в структурі – це підрозділи програмістської фірми, що вирішують різні аспекти однієї і тієї ж проблеми. Тимчасова структура утворюється внаслідок виконання проекту, котрий виконують певні особи з багатьох підрозділів, а керує призначена на час виконання проекту особа. Не виключено, що одна особа належатиме до декількох структур, оскільки може брати участь у декількох проектах, а з ін. боку, ці структури утворюються в межах фірми-розробника, що в свою чергу має певну організаційну структуру.

Інший важливий аспект динамічної складності – це наявність різних шкал часу для різних частин процесу. В багатьох випадках швидкості змін компонент одного і того ж процесу є різним – одні компоненти змінюються швидше, інші – повільніше.

Поняття складності системи вивчається не лише з якісного боку. Існують концепції, скеровані на вимірювання складності деяким числом. Найвідоміші серед них є наступні:

алгоритмічна концепція, що визначає складність як довжину алгоритму відтворення системи;

теоретико-інформаційна концепція, що пов’язує складність системи з її ентропією;

статистична концепція, що характеризує складність через міру розрізнюваності розподілів імовірностей;

обчислювальна концепція, що пов’язує алгоритмічну складність системи та засоби обчислень;

логічна концепція, що ґрунтується на аналізі властивостей предметів, що характеризують систему;

теоретико-множинна концепція, що ототожнює складність системи з числом її елементів.

Алгоритмічна складність ґрунтується на понятті функції, що може бути обчислена, та еквівалентна алгоритму, що може бути реалізований машиною Т’юрінга. Тому виникає природне запитання, чи не можна побудувати алгоритм, що обчислює складність алгоритму, призначеного до розв’язання задач того чи ін. класу, з метою розрахунку значень тієї чи ін. функції, що може бути обчисленою? Такий алгоритм дозволив би визначати довжини найкоротших програм розв’язання задач в сенсі машини Т’юрінга, що було би кроком до автоматизації “оптимального” програмування. Виявляється, що такого алгоритму не існує, тобто алгоритмічна складність не є функцією, що обчислюється. Внаслідок цього розробка програм найкоротшої довжини не може бути автоматизована. Іншими словами, обчислення алгоритмічної складності та побудова найкоротшої програми є творчим процесом, що вимагає у кожному окремому випадку винахідливості.

Отже, алгоритмічна складність – це складність описання алгоритму розв’язання задач деякого визначеного класу. Вона оцінює мінімально можливу довжини програми розв’язання фіксованої масової проблеми, але не дає уявлення про динамічні характеристики процесу обчислень. Алгоритмічна складність класу задач не дозволяє зробити висновок про порядок обчислень при розв’язання довільної індивідуальної задачі та оцінити середні чи максимальні затрати пам’яті та інших ресурсів, що необхідні для її розв’язання. Для повнішої оцінки обчислювального процесу внутрішню характеристику порядку – алгоритмічну складність – необхідно доповнити зовнішніми, що дозволяють оцінити витрати різних обчислювальних ресурсів на розв’язування класу задач.

Алгоритмічна складність та обчислювальна складність характеризують різні аспекти обчислювальних процедур. Для оцінювання обчислювальної складності, тобто ефективності та порядку обчислювальних процесів в залежності від обставин, використовуються статистичні та динамічні міри складності. З метою раціональної організації обчислень доцільно враховувати також міри складності, що характеризують надійність обчислень, можливості розпаралелення процесу розв’язування задач, частоту звертань до різних структурних складових ЕОМ.

Теоретико-інформаційна концепція розглядає складність розв’язання оптимізаційних задач. Оптимізація є ґрунтом для ухвали раціональних рішень. Кожне рішення, особливо у випадку, коли його наслідки впливають на майбутнє, повинно бути найкращим в певному сенсі. Визначення поняття “найкращий розв’язок” є надзвичайно складною методологічною проблемою, дослідження якої не є математичною проблемою, а проблемою СА. Однак оптимізація в більшості випадків є складовою частиною процесу прийняття рішень, а тому оцінювання складності задач оптимізації в залежності від розмірності задачі та припустимої точності є безсумнівно важливим. Недоліком цього підходу є неточність отримуваних результатів, оскільки процес розв’язування задач характеризується лише об’ємом інформації, що потрібно одержати, щоб побудувати розв’язок в межах заданої точності. При цьому не враховуються витрати обчислювальних ресурсів, що можуть суттєво залежати від вибраного методу і бути відчутно значними. Окрім того грубим є й застосовуваний підхід з точки зору принципу гарантованого результату – метод оцінюється за результатами його застосування до “найгірших” задач класу.

Статистична концепція складності ґрунтується на випадку, коли поведінка складних систем є значною мірою стохастичною і в деталях слабо передбачуваною. Агреговані характеристики