Losowa hierarchia wielomianowa?


12

Zastanawiam się, co by się stało, gdyby w definicji (wielomianowa hierarchia, patrz np. Tutaj ) rola zostałaby zastąpiona przez ?PHNPRP

Wydaje się, że można jeszcze zbudować hierarchię, tak samo jak jest zbudowany, tylko za pomocą wszędzie zamiast i zamiast . Nazwijmy to Randomized Polynomial Hierarchy ( ).PHRPNPcoRPcoNPRPH

Moje pierwsze przypuszczenie to , a może . Opiera się na znanym fakcie, że oznacza . Niemniej jednak, jeśli , to może nadal być właściwą, nieskończoną hierarchią w .RPHBPPRPH=BPPNP=RPPH=BPPPRPRPHBPP

Oczywiście, brzeg emisji stępiono tym, że Przypuszcza się (nawet ), które spłaszczają do . Jednak nie jest obecnie znane i oparł się wszelkim próbom dowodowym do tej pory. Dlatego wciąż ma przynajmniej szansę na odpowiednią hierarchię.P=RPP=BPPRPHPP=RPRPH

Chociaż , co prawda, ma spore szanse na bycie „płaskim”, to czy ta koncepcja może być przydatna w przypadku czegoś nietrywialnego? Oto przykład: jeśli można udowodnić, że , to dałoby to, że oznacza , co, moim zdaniem, byłoby interesującym rezultatem.RPHRPH=BPPP=RPP=BPP

Czy coś o tym wiadomo?


2
Co to znaczy dokładnie mieć RP jako wyrocznię, np. ? PRP
usul

Odpowiedzi:


8

Oczywiście, . Z drugiej strony ( Buhrman i Fortnow , pdf ), więc jedyny sposób, w jaki hierarchia nie upadła (co najwyżej) na drugi poziom i nie wyczerpała się byłoby z mało prawdopodobnego powodu, że wyrocznie były znacznie słabsze niż wyrocznie .RPHBPPBPP=ZPPpromiseRPBPPRPpromiseRP

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.