Важное применение теоремы PCP состоит в том, что она дает результаты типа «твердость приближения». В некоторых относительно более простых случаях такую твердость можно доказать без PCP. Есть ли, однако, какой-либо случай, когда твердость результата аппроксимации была сначала доказана с использованием теоремы PCP, т. Е. Результат не был известен раньше, но позже было найдено более прямое доказательство, которое не зависит от PCP? Другими словами, есть ли какой-нибудь случай, когда PCP сначала был необходим, но позже его можно было устранить?
cc.complexity-theory
approximation-hardness
pcp
Андрас Фараго
источник
источник
Для задачи о максимальных непересекающихся путях в ориентированных графах работа Ma & Wang (2000) была основана на проблеме покрытия меток, которая, в свою очередь, основана на теореме PCP. Впоследствии Guruswami et al. Нашел простое снижение с помощью твердости проблемы 2-непересекающихся путей. и др. (2003), который также дал улучшенную твердость.
источник
Есть примеры из приблизительного подсчета. Приблизительно подсчитать количество удовлетворяющих назначений NP-отношения может быть только сложнее, чем решить, существует ли удовлетворительное назначение, поэтому не слишком удивительно, что не требуется теорема PCP, чтобы доказать трудность для таких задач. Тем не менее, теорема PCP иногда дает удобную отправную точку, например, для этой статьи о приблизительном подсчете количества независимых множеств в разреженном графе: http://www.dcs.ed.ac.uk/home/mrj/papers/ DFJ02.pdf Позже, Слай доказал результат твердости для приблизительного подсчета независимых наборов только на основе стандартной NP-твердости Max-Cut: http://arxiv.org/pdf/1005.5584v1.pdf
источник
Другой ответ, который в несколько ином духе, чем предыдущие, - это статья Ури Фейджа: отношения между средней сложностью и сложностью аппроксимации .
Ури показывает, что предположения среднего случая могут заменить теорему PCP для доказательства сложности аппроксимации некоторых задач. Заметьте, однако, что мы не знаем, как доказать допущения в среднем случае, и у нас есть некоторые доказательства того, что мы не сможем доказать их на основе стандартных допущений твердости NP (см. Статьи Фейгенбаума-Фортнау, Богданов-Тревизан и др.)
источник