Может ли предел жестких языков быть легким?

13

Могут ли все последующие одновременно выполняться?

  1. Ls содержится в для всех натуральных чисел . sLs+1s
  2. L=⋃sLs - это язык всех конечных слов над .{0,1}
  3. Существует некоторый класс сложности и понятие соответствующего сокращения для такой , что для каждого , тяжело .C s L s CCCsLsC
cc.complexity-theory complexity-classes reductions Андраш Саламон
источник
1
Может ли это работать? При заданном перечислении булевых формул of (в двоичном коде) определяют где первые неудовлетворительные формулы в перечислении? Л ы = S Т ∪ { φ I 1 , . , , , Φ я с } φ я 1 , . , , , φ i s sφ1,φ2,...Ls=SAT∪{φi1,...,φis}φi1,...,φiss
Марцио Де Биаси
Это, кажется, работает, возможно, сделать это ответом?
Андрас Саламон

Ответы:

10

Я думаю, что мы можем просто начать с некоторого базового языка , а затем взять и .LL0=LLs+1=Ls∪{0,1}s+1

То есть каждый является объединением со всеми строками длиной до . Каждое , по крайней мере, так же сложно, как но не сложнее (в асимптотическом смысле), предполагая, что мы можем считать до .LsLsLsLs

Я также подумал об противоположном «пределе», поэтому каждый содержится в , а легко, а каждый сложно. Но я думаю, что мы могли бы просто начать с жесткого (но счетного) языка и просто удалять по одному слову на каждом шаге; пересечение должно быть пустым (каждое слово в конечном итоге удаляется).Ls+1LsL=∩sLsLsL0

усул
источник
7

Просто добавлю к ответам Марцио и Усула: то же самое можно сделать, даже если кто-то хочет, чтобы разница между и L s + 1 была бесконечной (что является одним из способов попытаться сделать вопрос менее тривиальным, но, как мы видим, не работает). Пусть D n = { x ∈ { 0 , 1 } ∗ : 1 x  - двоичное разложение целого числа, делимого на  n } . Тогда взяв L 0 = L и L s + 1 =LsLs+1Dn={x∈{0,1}∗:1x is the binary expansion of an integer divisible by n}L0=L должен сделать свое дело.Ls+1=Ls∪Ds

(Для любых фиксированных , если L был, скажем, CLIQUE, должно быть относительно легко взять сокращение от SAT до CLIQUE и изменить его чем-то вроде заполнения, так что это все еще сокращение от SAT до CLIQUE ∪ D s .)sL∪Ds

Джошуа Грохов
источник
4

Учитывая перечисление двоичные кодированные булевы формулы определяют л ы = S Т ∪ { φ я 1 , . , , , Φ я с } , где φ я 1 , . , , , φ i s - первые s неудовлетворительных формул в перечислении.φ1,φ2,...Ls=SAT∪{φi1,...,φis}φi1,...,φiss

Очевидно, что L s трудно для N P : учитывая булеву формулу φ, добавьте к ней достаточно новых переменных OR- x x i φ ∨ x 1 ∨ . , , ∨ х п , пока его индекс в перечислении не становится большечем (константа) я ев .LsNPφxi φ∨x1∨...∨xnis

Марцио де Биаси
источник
1
Если подумать, это, кажется, требует кодировки, для которой каждое конечное слово гарантированно появляется как кодировка некоторой формулы CNF. Однако затем можно изменить второе условие, чтобы был языком всех синтаксически допустимых формул CNF в кодировке; это все еще отражает дух вопроса. L
Андрас Саламон
Для твердости кажется достаточным заметить, что если NP-жесткий, а L ′ конечный язык, то L ∪ L ′ также NP-жесткий. LL′L∪L′
Андрас Саламон
@ AndrásSalamon: ты прав насчет доказательства твердости: -S! Однако я думаю, что «идеальное» кодирование (биекция между N и всеми действительными формулами) возможно и вычислимо за полиномиальное время.
Марцио Де Биаси