$ P ^ {NPI} $ $ P ^ {NP} $ айырмашылығы бар ма?

$ \ Mathsf {NP} $ - қиын емес (бұл $ \ mathsf P \ ne \ mathsf {NP} $ деп қарастырылған) $ L \ in \ mathsf {NP} $ әрбір тіл үшін $ \ mathsf { P} ^ L \ ne \ mathsf {P} ^ {\ text {SAT}} $? Сонымен қатар, бұл кез-келген ақылға қонымды болжамдармен дәлелдене ме?

12
Менің ойымша, бұл сұрақтың ақылға қонымды жауабы бар: $ L \ in \ mathsf P \ subeteq \ mathsf {NP} $, ал содан кейін әрине $ \ mathsf P ^ L \ neq \ mathsf P ^ {\ text {SAT}} $ $ \ mathsf P \ neq \ mathsf {NP} $ деп есептейік. Яғни $ \ mathsf P \ neq \ mathsf {NP} $, $ L $ $ \ mathsf {NP} \ setminus \ mathsf P $ және $ \ mathsf {NP} $ - қиын болу үшін әлі де қажет болуы мүмкін. [Өңдеу: О, төменде сіздің түсініктемеңізді оқып беремін, сондықтан сіздің сұрағыңыз: «Осындай $ L $ бар ма, жоқ па? => Сұрағыңызды түзетемін!]
қосылды автор Ozgur Ozcitak, көзі

1 жауаптар

NPI анықтамасына байланысты. Егер Turing қысқарту үшін A толық емес болса, онда жауап - иә, өйткені SAT $ P ^ A $ емес.

Егер А-ны тек біреу ғана толық емес болса, онда оны дәлелдеуді білмейміз. Бізде NP-де A көптеген NP-жетілдірілмеген арқылы көптеген салыстырмалы қысқартулар арқылы релятивизирленген әлем бар, бірақ SAT-ге бір сұраныммен есептелуі мүмкін (Теорема 1.9-те бұл қағаздар ).

16
қосылды
Сіздікі жөн. Тұрақты.
қосылды автор Juan, көзі
Теорема 1.9 дегенді білдіресіз бе?
қосылды автор hysteryteacher, көзі