O que é

Isso está relacionado à pergunta O tamanho da associação de testemunhas para cada idioma NP já é conhecido?

Alguns problemas naturais de $\mathsf{NP}$ (completos) têm testemunhas de comprimento linear: uma tarefa satisfatória para $SAT$ , uma sequência de vértices para , etc. $HAMPATH$

Considere a classe de complexidade " restrita a testemunhas de comprimento linear". Definição formal dessa classe de complexidade, chame-a : se $\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')$

Esta é uma classe de complexidade conhecida? Quais são as suas propriedades?

cc.complexity-theory complexity-classes np argentpepper
fonte

Você não pode sempre conseguir isso preenchendo?

MCH

Como MCH apontou, se

é qualquer linguagem

com testemunhas do tamanho

, então

é um

língua com testemunhas linear de tamanho, e

são de tempo polinomial muitos-um equivalente. Sua turma não é bem

L

$L$

N P

$\mathsf{NP}$

O (n^{k})

$O(n^k)$

p a d (L) := {x 10^{| x |^{k}} : x \in L}

$pad(L) := \{ x10^{|x|^{k}} : x \in L\}$

N P

$\mathsf{NP}$

L

$L$

p a d (L)

$pad(L)$

N P

$\mathsf{NP}$ , mas é basicamente o mesmo. A classe que você sugere não é fechado sob polytime muitos-um reduções, mas para cada

há alguma língua em sua classe que é polytime many-se um equivalente de

L

$L$

N P

$\mathsf{NP}$

L

$L$

Joshua Grochow

O que é

Respostas: