П с целочисленной факторизацией оракула

18

Я только что прочитал вопрос « Является ли целочисленная факторизация NP-полной проблемой? » ... поэтому я решил потратить часть своей репутации :-), задавая еще один вопрос с : $Q$ $P(\text{Q is trivial}) \approx 1$

Если является оракулом, который решает целочисленную факторизацию, какова мощность ? $A$ $P^A$

Я думаю, что это делает незащищенную криптографию с открытым ключом на основе RSA ... но кроме этого, есть ли другие замечательные результаты?

cc.complexity-theory oracles factoring Марцио де Биаси
источник

3

@ Не правда ли, эта часть P(Q is trivial)=1- шутка?

Pratik Deoghare

Этот вопрос предполагает , связанный и (возможно) более естественный вопрос: если R является оракулом , который возвращает F _ (_ МЫ , п ) как максимальное время выполнения полиномиального времени машина Тьюринга M над всеми входами длиной п , каковы силой P ^ R?

Джон Сидлес

2

@Vor: Разве это не то же самое, что спрашивать: «Какие проблемы могут быть за полиномиальное время Тьюринга, сводящееся к целочисленной факторизации?» Или вы хотели спросить что-то еще?

Джошуа Грохов

Я новичок, поэтому мой вопрос - почти любопытство. Все началось с простой мысли: «в реальном мире» я вижу много проблем, связанных с NP (почтальон, пытающийся сохранить силы, семья, которая движется и хочет уложить свою мебель в грузовик, ...: - ))). Но я не вижу «проблем факторинга» ... хотя они МОГУТ быть проще (между P и NPC). ... возможно, реальность ненавидит умножения :-D :-D

Марцио де Биаси

1

Смотрите также Последствия факторинга в P?

Юкка Суомела

11

У меня нет ответа на ваш вопрос, но я знаю, что подобное понятие было изучено совсем недавно под названием «безопасность на основе ангелов».

Первая статья, изучающая эту концепцию, - это Prabhakaran & Sahai (STOC '04) . В частности, они написали в аннотации:

[... мы даем] противнику доступ к некоторой сверхполиномиальной вычислительной мощности.

Другой важный документ, в котором обсуждается это понятие, - это Canetti, Lin & Pass (FOCS 2010) . Я смотрел некоторые части их презентации на конференции (на techtalks ), и, если я правильно помню, они начинают с примера, подобного тому, что вы упомянули в вопросе.

М.С. Дусти
источник

13

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

Проблема вычисления функции Эйлера кажется такой проблемой. Я не знаю, как решить вариант решения этой проблемы с помощью Karp-сокращения до варианта решения факторинга. Но с сокращениями по Тьюрингу это легко свести к факторингу.

Робин Котари
источник

3

Вот соответствующий пост в МО, касающийся сложности вычисления функции totient.

Сянь-Чи Чанг 之之

Небольшое дополнение: есть также полиномиальное сокращение времени в другом направлении, вычисляя функцию Totient Эйлера -> Факторинг. Я не проверял, работают ли известные сокращения для решения этих проблем. Тем не менее, возможность вычислить функцию Totient (или даже фиксированное ее кратное) дает вам возможность факторизовать. Книга Шоупа посвящает этому главу.

Хуан Бермехо Вега

9

Уточняя ранее ответ Джо: заметим , что . Последний является второй самый низкий класс в «низкой» иерархии : который должен сказать , что . Это означает , в частности , что Мы можем сделать аналогичные замечания для и $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$ $\mathsf{NP^{NP \cap coNP} = NP}$

п^{Факторинг} \subseteq N п^{Факторинг} \subseteq N п,

$\mathsf{P^{\textrm{FACTORING}} \subseteq NP^{\textrm{FACTORING}}} \subseteq \mathsf{NP}.$

c o N P

$\mathsf{coNP}$

B Q P

$\mathsf{BQP}$ , Чтобы показать , что по крайней мере , на крупнозернистый уровне,

имеет те же сложности оценки как проблема

самого, который должен сказать

P^{FACTORING}

$\mathsf P^{\textrm{FACTORING}}$

FACTORING

$\textrm{FACTORING}$

п^{Факторинг} \subseteq N п \cap с о N п \cap В Q п,

$\mathsf{P^{\textrm{FACTORING}} \subseteq NP \cap coNP \cap BQP}.$

Ниль де Бодрап
источник

N P \cap c o N P

$NP \cap coNP$

3

U P \cap c o U P

$\mathsf{UP} \cap \mathsf{coUP}$

6

$P^A\subseteq \Delta_2^P$

Маркус Ритт
источник

5

$\mbox{FNP}$ $P \subseteq P^A \subseteq \Delta_2^p$ $P^{NP}$ $\mbox{BQP}$ $P \subseteq P^A \subseteq P^{NP \cap BQP}$

Джо Фитцсимонс
источник

П с целочисленной факторизацией оракула

Ответы: