?
Нижние множества и свойства замкнутости классов функций подсчета
Язык L является нижним для релятивизируемого сложностного класса C, если CL=C. Для классов #P, GapP и SpanP известны точные нижние классы языков: Low(#P) = UP ∩ coUP, Low(GapP) = SPP и Low(SpanP) = NP ∩ coNP. В этой статье мы доказываем, что Low(TotP) = P, и приводим характеризации нижних классов функций для #P, GapP, TotP и SpanP. В частности, мы доказываем, что Lowf(#P) = UPSVt и Lowf(SpanP) = NPSVt. Мы устанавливаем отношения включения между NPSVt, UPSVt и классами функций подсчета, предоставляя для каждого из этих включений эквивалентное включение между классами языков. Мы также доказываем, что SpanP ⊆ GapP тогда и только тогда, когда NP ⊆ SPP, и включение GapP+ ⊆ SpanP влечет PH = ΣP2. Для класса #P мы доказываем, что его замкнутость относительно левой композиции с FP+ эквивалентна #P = UPSVt, а для SpanP такая замкнутость эквивалентна SpanP = NPSVt. Для классов #P, GapP, TotP и SpanP мы приводим обзор известных результатов и показываем, что каждый из этих классов замкнут относительно левой композиции с FP+ тогда и только тогда, когда он совпадает со своим нижним классом функций. Мы также доказываем, что НПМТ с оракулом #P всегда может делать не более одного запроса к оракулу, не изменяя количество принимающих путей.