Унарна система числення — це система числення із базисом-1. Це найпростіша система числення для представлення дійсних чисел:. для того, щоб в ній представити число N, довільно вибраний символ, який використовується як 1 повторюється N разів.. Наприклад, числа 1, 2, 3, 4, 5, … будуть виглядати в такій системі як показано нижче. 1, 11, 111, 1111, 11111, … Ці числа не слід плутати із репюнітами, які також задаються у вигляді послідовностей одиниць але мають свою звичайне десяткову числову інтерпретацію.
Застосування Унарні числа використовуються в деяких алгоритмах стиснення даних, таких як код Голомба.. Це поняття також є основою для аксіом Пеано, що формалізують арифметику в рамках математичної логіки.. Форма унарної нотації, яка називається використовується для представлення чисел в Лямбда-численні..
Складність У порівнянні зі стандартним позиційним записом, унарна система незручна і тому не використовується на практиці для великих обчислень. Вона зустрічається в описах деяких проблем вибору в теорії алгоритмів (наприклад в деяких задачах), де її використовують, щоб «штучно» зменшити час виконання або просторові вимоги задачі. Наприклад, підозрюють, що задача факторизації цілих чисел вимагає часу виконання більшого ніж поліномна функція від довжини її входу в двійковому записі, але їй потрібен лише лінійний час якщо вхід представлено унарно.. Однак, це потенційно оманливо. Використання унарного входу повільніше для будь-якого заданого числа, не швидше. Відмінність у тому, що двійковий (або більшої основи) вхід пропорційний логаритму з основою два (або більше) числа тоді як унарний вхід пропорційний самому числу. Отже, хоча з унарною системою час виконання і просторові вимоги як функції від довжини входу виглядають краще, вони не представляють дієвішого розв'язання..
У теорії складності обчислень, унарні числа використовуються, щоб відрізнити задачі від NP-повних, але не сильно NP-повних. Задача, що має на вході якісь числові параметри сильно NP-повна, якщо вона залишається NP-повною навіть коли розмір входу штучно збільшують переводячи його в унарну систему. Для такої задачі, існують складні випадки для яких значення всіх параметрів майже поліномно великі..
Примітки