Родился в Москве. Окончил Московский университет '(1925 г;), причем во время учебы призывался в Красную Армию. С 1934 г. работал в Математическом институте АН СССР (с 1957 г. возглавлял отдел математической логики). Доктор физико-математических наук (1935 г.), профессор. В 1953 г. избран членом-корреспондентом, а в 1960 г.— академиком АН СССР.
Основные труды относятся к теории множеств, математической логике и алгебре. Еще аспирантом получил полное решение одной из трудных проблем дескриптивной теории множеств. Чтобы найти способы решения важных задач теории множеств, начал усиленно заниматься вопросами математической логики. Уже в своей первой работе в этой области установил класс задач, касающихся целых чисел, для которых из неэффективного решения вопросов извлекается эффективное в совершенно конкретной форме.
Следующие проблемы, которыми занялся ученый, были знаменитая проблема континуума и близкие к ней проблемы мощности и измеримости проективных мно-жеств. В 1952 г. установил, что существуют группы с конечным числом образующих и конечным числом определяющих отношений, для которых нет алгоритма, решающего проблемы тождества слов. Эта проблема возникла еще в 1912 г. Она является одной из центральных проблем теории групп. Работами П. С. Новикова и его учеников открылась новая интересная область исследования. Она, по существу, только частично относится к теории групп, скорее же — к области так называемой конструктивной алгебры. Результаты, устанавливающие отсутствие тех или иных алгоритмов, имеют огромное практическое значение, так как избавляют математиков от безнадежных поисков.
В алгебре (вместе со своим учеником С. И. Адяном) в 1959 г. решил важную проблему Бернсайда: будет ли всякая периодическая группа конечной или нет? Доказал, что существует группа с двумя образующими, периодическая и бесконечная. Таким образом, ответ на вопрос Бернсайда оказался отрицательным. Занимался также исследованиями в области топологии, теории функций и математической физике.
Одновременно с научной вел педагогическую деятельность. Еще студентом преподавал математику в Красноармейской школе. Работал в Московском педагогическом институте им. В. И. Ленина (заведовал кафедрой математического анализа), в течение ряда лет руководил научными семинарами по теории функций и математической логике в педагогическом институте и университете.
Создал советскую школу математической логики, получившую широкое признание. Уделял большое внимание организации учебного процесса в университетах и педагогических институтах. Автор многих программ по различным разделам математики. Вел также большую общественную работу, был членом редколлегий ряда математических журналов. Среди его многочисленных учеников можно назвать А. А. Ляпунова, С. В. Яблонского, А. Д. Тайманова. Лауреат Ленинской премии, награжден двумя орденами Ленина, орденом Трудового Красного Знамени, а также значком «Отличник народного просвещения».