Что такое

Это связано с вопросом: известен ли размер свидетельства для каждого языка NP, уже известного?

Некоторые естественные задачи (-complete) имеют свидетелей линейной длины: удовлетворительное назначение для S A T , последовательность вершин для H A M P A T H и т. Д.$\mathsf{NP}$$SAT$$HAMPATH$

Рассмотрим класс сложности « ограниченный свидетелями линейной длины». Формальное определение этого класса сложности, назовите его C : L ∈ C, если ∃ L ′ ∈ P : ( x ∈ $\mathsf{NP}$$\mathcal{C}$$L\in\mathcal{C}$ .$\exists L'\in\mathsf{P}\colon (x\in L \iff \exists w\in\{0, 1\}^{O(|x|)}\colon (x, w)\in L')$

Это известный класс сложности? Каковы его свойства?

Класс вы предлагаете, вероятно , не N P . (Если C = N P , то каждый язык N P будет иметь свидетелей линейного размера, что подразумевает, что , среди прочего , все N P ⊆ T I M E [ 2 O ( n ) ] и N P ≠ E X P ) ,${\cal C}$$NP$${\cal C} = NP$$NP$$NP \subseteq TIME[2^{O(n)}]$$NP \neq EXP$

Это очень естественно, чтобы рассмотреть такие классы; они возникают в нескольких настройках. В этой статье Рахул Сантанам (неявно) предложил обозначение для вычисления времени t ( n ) с битами g ( n ) -гадачи. Следовательно, C = ⋃ k T I G U ( n k , k n ) . В этой статье$TIGU(t(n),g(n))$$t(n)$$g(n)$${\cal C} = \bigcup_{k} TIGU(n^k,kn)$Я определил аналогичный класс . (NTIBI означает «недетерминированное время и биты».) Кроме того, Кай и Чен назовут ваш класс G C ( O ( n ) , P ) (GC означает «Угадай и проверь», ср. Л. Кай и Дж. Чен О количестве недетерминизма и силе проверки. SIAM Journal of Computing, 1996). Наконец, если вы ищете «ограниченный недетерминизм», вы можете найти еще три нотации для того же класса ...$NTIBI[t(n),b(n)]$$GC(O(n), P)$