2.3. Функціональні схеми. Будь-яку функцію  можна трактувати як функцію  і розглядати можливість її обчислення прямолінійною програмою. Зауважимо, що стандарт­ні логічні зв'язки можна виразити через арифметичні операції в : кон'юнкцію булевих змінних і , як їх добуток , диз'юнкцію як , а заперечення змінної  як операцію додавання одиниці . Оскільки кожну булеву функцію  можна вира­зити булевою формулою у диз'юнктивній нормальній формі, приходимо до висновку, що кожна функція  обчислюється певною прямолінійною програмою. Складність обчислення функції  позначимо через . Таким чином,  позначає найменшу можли­ву довжину прямолінійної програми над  для обчислення функції .

Прямолінійні програми над  довжини  частіше називають (функ­ціональними) схемами розміру  у базі . Як зазначалось, кон'юнкція  збігається із множенням в . Логічна зв'язка , що відповідає додаванню в , часом позначається як XOR, від eXclusive OR — "виключне або".

Зазначимо принципову відмінність між схемами та алгоритмами у сенсі пункту 1.2. Перші обчислюють скінченні функції вигляду , в той час як другі — нескінченні функції ви­гляду  (як зазначалось в пункті 1.2, вибір алфавіту не відіграє принципової ролі, тож ми задля зручності надаємо пере­вагу двійковому). Однак між двома моделями існує глибокий зв'язок. Наступна теорема справедлива для будь-якої природної формалізації поняття алгоритму.

теорема 2.2. Нехай функція  обчислюється деяким поліноміальним алгоритмом. Позначимо через  звуження  на множину . Тоді  для деякої константи  > 0.

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

1) взяти схему ,

2) промоделювати її обчислення на вході .

 Так от, з пунктом 2 немає проблем, але для втілення пункту 1 повинен бути ефективний спосіб породження схеми  за словом довжини . Послідовність схем  з такою властивістю називають однорід­ною. Очевидно, що однорідною є далеко не кожна послідовність схем. В цьому контексті, алгоритми у сенсі пункту 1.2 називають однорідною моделлю обчислень, а прямолінійні програми та схеми — неоднорідною.

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

Функціональні схеми, тобто прямолінійні програми над , дозво­ляють розглядати внутрішню структуру операцій множення та дода­вання у двійковій системі числення. В контексті виконання арифметич­них операцій команди прямолінійної програми над  часто називають бітовими операціями. Стандартні алгоритми додавання та множен­ня двох -розрядних двійкових чисел затрачають, відповідно,  і  бітових операцій. Ділення (з остачею) має такий же порядок складності, як і множення. Шонгаге і Штрассен запро­понували алгоритм, який виконує множення коштом  бітових операцій. Їх ме­тод використовується в асимптотично швидкому алгоритмі знаходжен­ня НСД двох -розрядних чисел за  операцій.