Разреженный язык

В теории вычислительной сложности разреженный язык — это формальный язык (набор строк ), такой, что функция сложности , подсчитывающая количество строк длины n в языке, ограничена полиномиальной функцией n . Они используются в основном при изучении связи класса сложности NP с другими классами. Класс сложности всех разреженных языков называется SPARSE .

Разреженные языки называются разреженными, потому что существует всего 2 ⁿ строк длины n , и если язык содержит только полиномиально много таких строк, то доля строк длины n , которые он содержит, быстро стремится к нулю по мере роста n . Все унарные языки являются разреженными. Примером нетривиального разреженного языка является множество двоичных строк, содержащих ровно k 1 бит для некоторого фиксированного k ; для каждого n в языке есть только строки, что ограничено n ^k . ${\binom {n}{k}}$

Связь с другими классами сложности

SPARSE содержит TALLY , класс унарных языков , поскольку они имеют не более одной строки любой длины.

Хотя не все языки из P /poly являются разреженными, существует полиномиальное по времени сведение по Тьюрингу любого языка из P /poly к разреженному языку. ^[1]
В 1979 году Форчун показал, что если какой-либо разреженный язык является co-NP -полным , то P = NP . ^[2] Махани использовал это, чтобы показать в 1982 году, что если какой-либо разреженный язык является NP -полным , то P = NP (это теорема Махани ). ^[3] Более простое доказательство этого, основанное на левых множествах, было дано Огихарой и Ватанабе в 1991 году. ^[4] Аргумент Махани на самом деле не требует, чтобы разреженный язык был в NP (потому что существование NP-трудного разреженного множества подразумевает существование NP-полного разреженного множества), поэтому существует разреженное NP -трудное множество тогда и только тогда, когда P = NP . ^[5]
Далее, E ≠ NE тогда и только тогда, когда существуют редкие языки в NP , которых нет в P. ^[6]
Редукция Тьюринга (в отличие от редукции Карпа из теоремы Махани) от NP -полного языка к разреженному языку существует тогда и только тогда, когда . ${\textbf {NP}}\subseteq {\textbf {P}}/{\text{поли}}$
В 1999 году Джин-И Цай и Д. Сивакумар, основываясь на работе Огихары, показали, что если существует разреженная P -полная задача, то L = P.^[7 ]

Ссылки

^ Jin-Yi Cai. Лекция 11: P=poly, разреженные множества и теорема Махани. CS 810: Введение в теорию сложности. Университет Висконсин–Мэдисон. 18 сентября 2003 г. (PDF)
^ S. Fortune. Заметка о разреженных полных наборах. SIAM Journal on Computing , том 8, выпуск 3, стр. 431–433. 1979.
^ SR Mahaney. Разреженные полные множества для NP: решение гипотезы Бермана и Хартманиса. Журнал компьютерных и системных наук 25:130–143. 1982.
^ М. Огивара и О. Ватанабэ. О полиномиальной временной ограниченной сводимости таблиц истинности множеств NP к разреженным множествам. Журнал SIAM по вычислениям, том 20, стр. 471–483. 1991.
^ Балькасар, Хосе Луис; Диас, Хосеп; Габарро, Хоаким (1990). Структурная сложность II . Спрингер . стр. 130–131. ISBN 3-540-52079-1.
^ Юрис Хартманис, Нил Иммерман, Вивиан Сьюэлсон. Разреженные множества в NP-P: EXPTIME против NEXPTIME. Информация и управление , том 65, выпуск 2/3, стр. 158–181. 1985. В ACM Digital Library
^ Jin-Yi Cai и D. Sivakumar. Sparse hard sets for P: resolution of a conjecture of Hartmanis. Журнал компьютерных и системных наук , том 58, выпуск 2, стр. 280–296. 1999. ISSN 0022-0000. На Citeseer

Внешние ссылки

Лэнс Фортнау . Любимые теоремы: малые множества. 18 апреля 2006 г.
Уильям Гасарч . Разреженные множества (Посвящение Махани). 29 июня 2007 г.
Зоопарк сложности : РАЗРЕШЕННЫЙ