Вопросы с тегом «np»

9
Каждый ли распознаваемый по Тьюрингу неразрешимый язык имеет NP-полное подмножество?

Каждый ли распознаваемый по Тьюрингу неразрешимый язык имеет NP-полное подмножество? Этот вопрос можно рассматривать как более сильную версию того факта, что каждый бесконечный распознаваемый по Тьюрингу язык имеет бесконечное разрешимое...

9
Неравные против единообразных противников

Этот вопрос возник в контексте криптографии, но ниже я представлю его с точки зрения теории сложности, поскольку здесь люди больше знакомы с последним. Этот вопрос связан с проблемами в NP, но не в Average-P / poly и неоднородности биения по Oracle Access . Неформальное утверждение: когда...

9
Может ли быть чрезвычайно большое скрытое подмножество полиномиально разрешимых задач в задачах NP-Complete?

Предположим, P! = NP. Мы знаем, что можем в любое время легко создавать 3-SAT. Мы также можем генерировать то, что мы считаем трудными примерами (потому что наши алгоритмы не могут их быстро решить). Что-нибудь мешает множеству жестких экземпляров быть сколь угодно малыми, при условии, что для...