Скудный язык - Sparse language

В теория сложности вычислений, а скудный язык это формальный язык (набор струны ) такой, что функция сложности, считая количество строк длины п на языке ограничен многочлен функция п. Они используются в первую очередь при изучении взаимосвязи класса сложности НП с другими классами. В класс сложности всех разреженных языков называется РЕДКО.

Редкие языки называются редкий потому что всего 2п строки длины п, и если язык содержит только полиномиально много из них, то пропорция строк длины п что он содержит, быстро стремится к нулю при п растет. Все унарные языки редки. Примером нетривиального разреженного языка является набор двоичных строк, содержащих ровно k 1 бит для некоторых фиксированных k; для каждого п, Есть только строки на языке, который ограничен пk.

Отношения с другими классами сложности

РЕДКО содержит ВСЕГО, класс унарные языки, поскольку они содержат не более одной строки любой длины. Хотя не все языки в п/поли редки, есть редукция по Тьюрингу за полиномиальное время с любого языка в п/ poly на разреженный язык.[1]В 1979 году судьба показала, что если какой-то скудный язык со-НП-полный, тогда п = НП;[2]Махани использовал это, чтобы показать в 1982 году, что если какой-то скудный язык НП-полный, тогда п = НП (это Теорема Махани ).[3]Более простое доказательство этого, основанное на левых множествах, было дано Огихарой ​​и Ватанабе в 1991 году.[4]Аргумент Махани на самом деле не требует наличия разреженного языка в NP, поэтому существует разреженный НП-жесткий установить тогда и только тогда, когда п = НП.[5]Дальше, E ≠ NE тогда и только тогда, когда в НП что не в п.[6]Существует Редукция Тьюринга (в отличие от Редукция Карпа из теоремы Махани) из НП-полный язык к разреженному тогда и только тогда, когда В 1999 году Цзинь-И Цай и Д. Сивакумар, основываясь на работе Огихары, показали, что если существует редкая п-полный проблема тогда L = п.[7]

Рекомендации

  1. ^ Джин-И Цай. Лекция 11: P = poly, разреженные множества и теорема Махани. CS 810: Введение в теорию сложности. Университет Висконсина-Мэдисона. 18 сентября 2003 г. (PDF)
  2. ^ С. Форчун. Отметка о скудности комплектаций. SIAM Журнал по вычислениям, том 8, выпуск 3, с.431–433. 1979 г.
  3. ^ С. Р. Махани. Редкие полные наборы для NP: решение гипотезы Бермана и Хартманиса. Журнал компьютерных и системных наук 25:130–143. 1982.
  4. ^ М. Огивара и О. Ватанабэ. О полиномиальной таблице истинности сводимости NP-множеств к разреженным множествам. SIAM Журнал по вычислениям том 20, с.471–483. 1991 г.
  5. ^ Балькасар, Хосе Луис; Диас, Хосеп; Габарро, Хоаким (1990). Структурная сложность II. Springer. С. 130–131. ISBN  3-540-52079-1.
  6. ^ Юрис Хартманис, Нил Иммерман, Вивиан Севельсон. Редкие наборы в NP-P: EXPTIME против NEXPTIME. Информация и контроль, том 65, выпуск 2/3, стр 158–181. 1985 г. В цифровой библиотеке ACM
  7. ^ Джин-И Цай и Д. Сивакумар. Редкие жесткие множества для P: разрешение гипотезы Хартманиса. Журнал компьютерных и системных наук, том 58, выпуск 2, стр.280–296. 1999 г. ISSN  0022-0000. В Citeseer

внешняя ссылка