Примеры игрушек для барьеров для

28

Существуют ли какие-нибудь игрушечные примеры, которые дают «существенную» информацию для понимания трех известных барьеров для проблемы P=NP - релятивизации, естественных доказательств и алгебризации?

против
источник

Ответы:

25

TIME[t(n)]TIME[t(n)2]A(x)xAxxt(|x|)At(|x|)2

Аргумент работает одинаково хорошо, если мы снабдим все алгоритмы доступом к произвольному множеству оракулов , к которому, как мы предполагаем, мы можем задать запросы членства, за один шаг вычислений. Пошаговый для шага моделирование также может быть осуществлено с помощью , до тех пор , как имеет доступ к оракулу тоже. В обозначениях, мы имеем для всех оракулов . Другими словами, временная иерархия релятивизируется .OAxOAAOTIMEO[t(n)]TIMEO[t(n)2]O

Мы можем определить оракулы для недетерминированных машин естественным образом, поэтому имеет смысл определить классы и относительно оракулов. Но есть оракулы и относительно которых и P ^ {O'} \ neq NP ^ {O '} , поэтому этот вид прямого аргумента моделирования в теореме иерархии времени не будет работать для разрешения P против NP . Релятивизирующие аргументы являются мощными в том смысле, что они широко применимы и привели ко многим великим прозрениям; но эта же сила делает их «слабыми» в отношении таких вопросов, как P против NP . Н П О О О ' П О = Н П ОPONPOOOPO=NPOPONPOPNPPNP

Вышесказанное, конечно, игрушечный пример - есть много других более сложных примеров сложных аргументов, которые все еще релятивизируются (т. Е. Сохраняются, когда вводятся произвольные оракулы).

Райан Уильямс
источник