Когда мы говорим «Полиномиальное время», мы имеем в виду O (n ^ c). O (x) означает «x или меньше», поэтому постоянное время также попадает в эту категорию. Ответ на вопрос «Являются ли проблемы, решаемые в постоянное время, разрешимыми за полиномиальное время?» Да. Мы также говорим, что ответ на вопрос «Подпадают ли задачи, решаемые в постоянном времени, под категорию задач P?» это да.
Однако, ваш пример "определения значения 4/2" технически не является проблемой P. Задачи P определяются как «Класс сложности P - это совокупность всех решений задач, которые могут быть решены с помощью полиномиальной сложности времени в худшем случае». Решение проблемы имеет «да» или «нет» в качестве вывода, а не 2. Кроме того, такая проблема должна иметь вход. Вариант решения вашей проблемы может быть:
Учитывая три числа, a, b и c, определить, является ли a / b
Проблемы, решаемые в постоянное время, часто бесполезны в теории сложности, потому что мы не можем даже проверить каждый бит ввода в постоянное время.
Пример (бесполезной) проблемы решения с постоянным временем (так в P):
Учитывая n входных чисел, определить, если 4/2 = 2. Выход не зависит от входа и всегда да.
Другой пример (бесполезной) проблемы решения с постоянным временем (так в P):
Учитывая массив A, определить, является ли A [0] четным.