Полнота при инъективных сокращениях Карпа

Сокращение Карпа - это вычисляемое многочленное сокращение многочлена за полиномиальное время между двумя вычислительными задачами. Многие сокращения Карпа на самом деле являются функциями «один-один». В связи с этим возникает вопрос, является ли каждое редукция Карпа инъективной (однозначная функция).

Существует ли естественная полная проблема, которая, как известно, завершается только при многократном сокращении Карпа и не является полной при инъективном уменьшении Карпа? Что мы получим (и потеряем), если определим полноту с помощью инъективного сокращения Карпа?Н $NP$$NP$

Одно очевидное преимущество состоит в том, что разреженные множества не могут быть полными при инъективных сокращениях Карпа.

Вот ответ на частный случай, когда мы ограничимся случаем, когда сокращение Карпа можно также сделать увеличивающим длину , а также сделав его инъективным. (Увеличение длины означает, что , где - функция, представляющая сокращение.)$|f(x)|>|x|$$f$

Утверждение: Если каждое сокращение Карпа в можно преобразовать в инъективное и увеличивающее длину, то имеет место.P ≠ N $NP$$P\neq NP$

Доказательство. Предположим, что каждое сокращение Карпа в можно преобразовать в инъективное и увеличивающее длину. Тогда есть две возможности:$NP$

1. $NP$$p$$P\neq NP$

2. $P\neq NP$

$P\neq NP$

$\mathsf{NP}$$\mathsf{NP}$

На самом деле, даже потенциальные «неестественные» контрпримеры к гипотезе об изоморфизме - k-креативные множества из теоремы 2.2 Джозефа и Юнга - полны по построению один-один.

[Повторяется из моего комментария здесь :] Поскольку большинство сокращений «многие-один», которые мы строим, на самом деле являются сокращениями «один-один», почему бы нам не изучить их, когда они формально сильнее, и в любом случае мы получаем их большую часть времени? Я думаю, потому что проще не беспокоиться о доказательстве инъективности, хотя у нас это обычно бывает. В этом смысле, возможно, сокращение «один-один» является своего рода «сокращением Златовласки»: просто правильная сила, просто правильная простота доказательства.

На самом деле, инъекционные сокращения полезны в криптографии. Предположим, у вас есть система доказательства ZK для отношения NP R на языке L. Если вы хотите построить доказательство ZK для другого отношения NP R 'на языке L', вам нужно найти две функции f и g со следующими свойствами. : 1. x принадлежит L 'тогда и только тогда, когда f (x) принадлежит L, 2. Если (x, w) принадлежит R', то (f (x), g (x, w)) принадлежит R. 3. Более того , f и g должны быть эффективно вычисляемыми.

Приведенные выше свойства подразумевают, что если система доказательств для R полна и надежна, система доказательств для R '(определенная очевидным образом с использованием вышеуказанных функций для уменьшения случаев отношения к другой) также является полной и надежной.

Как насчет того, чтобы доказать, что новая система также ZK или не различима свидетелем (WI)? Если f обратимо, вы можете доказать, что полученная таким образом система доказательств ZK. В противном случае, чтобы доказать, что вы должны предположить, что система доказательства для R - это вспомогательный вход ZK (а не просто ZK). Для WI, если f обратим, вы можете доказать, что система доказательств для R 'является WI. Без факта, что f обратимо, я не уверен, что вы можете доказать, что