Является ли P такой же, как P-Complete в теории сложности? Мне нужно знать, идентичны ли эти два класса. Потому что у меня есть сокращение Карпа между любыми двумя, но не могу найти его в Интернете.Является ли P таким же, как P-Complete?
Любая проблема в Р может быть полиномиальное время уменьшаются (как много-один и Тьюринга) к почти любой другой проблеме в P.
единственной причиной, чтобы сказать «почти» является потому что есть одна проблема (и ее дополнение), которые никакие другие проблемы не могут быть много-единственными, сведенными к (хотя они могут быть уменьшены до Тьюринга): проблема, которая принимает все (и тот, который отвергает все).
Источник: Wikipedia
Как правило, когда речь идет о Р-полноте, более слабой форме сокращения, чем полиномиальное время сводимости используется по той причине, вы перечислили. Обычно используется нечто подобное logspace или AC^0 сводимости. –