Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Отношения с другими классами сложности [ править ]

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

Ссылки [ править ]

  1. ↑ Jin-Yi Cai. Лекция 11: P = poly, разреженные множества и теорема Махани. CS 810: Введение в теорию сложности. Университет Висконсина-Мэдисона. 18 сентября 2003 г. (PDF)
  2. ^ С. Форчун. Замечание о скудности комплектаций. SIAM Journal on Computing , том 8, выпуск 3, стр. 431–433. 1979 г.
  3. ^ SR Mahaney. Редкие полные наборы для NP: решение гипотезы Бермана и Хартманиса. Журнал компьютерных и системных наук 25: 130–143. 1982 г.
  4. ^ М. Ogiwara и О. Ватанабе. О полиномиальной таблице истинности сводимости NP-множеств к разреженным множествам. SIAM Journal on Computing, том 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. ↑ Jin-Yi Cai и D. Sivakumar. Редкие жесткие множества для P: разрешение гипотезы Хартманиса. Журнал компьютерных и системных наук , том 58, выпуск 2, стр.280–296. 1999. ISSN 0022-0000 . В Citeseer 

Внешние ссылки [ править ]

  • Лэнс Фортноу . Любимые теоремы: малые множества . 18 апреля 2006 г.
  • Уильям Гасарх . Редкие наборы (дань уважения Махани) . 29 июня 2007 г.
  • Зоопарк сложности : SPARSE