Учитывая A до C, и B к C с известными сложными слоями, то, что можно сказать о B-B?

Question

Скажем, у меня есть два набора значений $ a $ и $ b $ и для каждого набора i Имейте вычислимую функцию, установленную на третий набор $ C $ . Теперь предположим, что я хочу построить функцию из $ A $ на $ B $ , так что если я Составьте эту функцию с помощью $ B $ на $ C $ Функция, упомянутая выше, я получаю функцию, которая производит Та же результаты, что и $ A $ на $ C $ Функция, упомянутая выше.

Если я знаю временную сложность двух функций, которые возвращают элементы $ C $ , что позволяет мне сказать что-нибудь о функции от <класса Span= «Математический контейнер»> $ a $ на $ b $ с указанным свойством? Например, могут быть размещены любые границы на вычислительную сложность такой функции? Можем ли мы даже сказать, является ли такая функция вычислима или нет?

Answer 1

Мы можем иметь множество $ a, b, c $ с линейными вычисляемыми картами $ f: a \ C $ и $ G: B \ C $ Такое, что существует карта $ h: a \ до b $ с $ f= g \ circ h $ , но необходимая степень сложности времени / ст. для $ h $ так же высок, как вы хотите.

Доказательство: выбрать карту $ h: \ sigma ^ * \ to \ sigma ^ * $ Что сложно в любом смысле вы выбрали. Теперь позвольте $ a= c=sigma ^ * $ и $ b={\ langle w, h (w ) \ rungle \ mid w \ in \ sigma ^ * \} $ . Пусть $ f=mathrm {id} $ и $ g=pi_1 $ , т.е.="Математический контейнер"> $ g (\ langle w, u \ pangle)= w $ . Теперь $ a, b, c $ и $ f, g $ соответствует критериям претензии, а также Единственная карта $ h $ , который работает $ h (w)=langle w, h (w) \ rangle $ , который по сути так же сложно, как $ h $ .

Answer 2

Вы задаете два вопроса, один о вычислимости и один о вычислительной сложности.Обычное правило - задать один вопрос на пост.Я отвечу на второй вопрос.Нет, при стандартных предположениях, вычислительная сложность может быть довольно плохой.Предположим, $ f: a \ to c $ дается $ f (x)=alpha ^ x \ bmod p $ и $ g: b \ close c $ дается $ g (x)=beta ^ x\ bmod p $ , где $ p $ - это большое простое число.Затем вы можете вычислить $ F, G $ в полиноме;Но нахождение карты $ a \ to b $ так же сложно, как вычисления дискретных журналов $ \ beta $ Для базы $ \ alpha $ , который предполагается быть сложно.

Answer 3

Открытый ключ Криптография основан на идее того, что сложность может быть сделана очень высокой.

Пусть A - набор открытых ключей, а B - набор частных клавиш, и C множество результатов шифрования некоторого фиксированного простого текста.Как публично, так и закрытый ключ позволяют довольно легко рассчитать зашифрованный текст.Но вы спрашиваете, если учесть открытый ключ, вы можете рассчитать частный ключ, дающий то же самое зашифрованное сообщение.Поскольку простой текст должен быть одинаковым, чтобы получить то же самое зашифрованное сообщение, это немедленно даст вам закрытый ключ на любой открытый ключ.