Что такое

24

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

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

Рассмотрим класс сложности « ограниченный свидетелями линейной длины». Формальное определение этого класса сложности, назовите его C : L C, если L P : ( x LNPCLC .LP:(xLw{0,1}O(|x|):(x,w)L)

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

argentpepper
источник
Разве вы не всегда можете добиться этого, набив?
МЧ
5
Как указывал MCH, если - это любой язык N P со свидетелями размера O ( n k ) , то p a d ( L ) : = { x 10 | х | k : x L } является языком N P с свидетелями линейного размера, а L и p a d ( L ) являются многозначным эквивалентом за полиномиальное время. Ваш класс не совсем N PLNPO(nk)pad(L):={x10|x|k:xL}NPLpad(L)NP, но это в основном то же самое. Класс ты предлагаешь не замкнуты относительно полиномиального по много-один сокращений, но и для каждого в N P есть некоторый язык в своем классе , который является полиномиальным по много-один эквивалентом L . LNPL
Джошуа Грохов

Ответы:

27

Класс вы предлагаете, вероятно , не N P . (Если C = N P , то каждый язык N P будет иметь свидетелей линейного размера, что подразумевает, что , среди прочего , все N P T I M E [ 2 O ( n ) ] и N P E X P ) ,CNPC=NPNPNPTIME[2O(n)]NPEXP

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

Райан Уильямс
источник