O que é

24

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

Alguns problemas naturais de 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 C : L C se L P : ( x LNPCLC .LP:(xLw{0,1}O(|x|):(x,w)L)

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

argentpepper
fonte
Você não pode sempre conseguir isso preenchendo?
MCH
5
Como MCH apontou, se é qualquer linguagem N P com testemunhas do tamanho O ( n k ) , então p a d ( L ) : = { x 10 | x | K : x L } é um N P língua com testemunhas linear de tamanho, e G e p um d ( G ) são de tempo polinomial muitos-um equivalente. Sua turma não é bem N PLNPO(nk)pad(L):={x10|x|k:xL}NPLpad(L)NP, mas é basicamente o mesmo. A classe que você sugere não é fechado sob polytime muitos-um reduções, mas para cada em N P há alguma língua em sua classe que é polytime many-se um equivalente de L . LNPL
Joshua Grochow

Respostas:

27

A classe CNPC=NPNPNPTIME[2O(n)]NPEXP

É muito natural considerar essas classes; eles surgem em várias configurações. No presente trabalho , Rahul Santhanam (implicitamente) propôs a notação TIGU(t(n),g(n))t(n)g(n)C=kTIGU(nk,kn) . No presente trabalhoNTIBI[t(n),b(n)]GC(O(n),P)

Ryan Williams
fonte