Pytania otagowane jako uniformity

3
Czy
Pomyślałem, że podzielę się tym pytaniem, ponieważ może być interesujące dla innych użytkowników tutaj. Załóżmy, że funkcja, która jest klasą jednolitej (jak ) jest także w niewielkim klasy nierównomierne (jak A C 0 / P O l y , czyli niejednolity C 0 ), czy to oznacza, że funkcja ta …
3
Czy istnieje kandydat na naturalny problem w ?
Chcę wiedzieć, czy niejednorodność pomaga w praktyce funkcji obliczeniowych. Łatwo jest pokazać, że istnieją funkcje w , weź dowolną funkcję nieobliczalną i rozważ język { }, który wyraźnie ma proste niejednorodne obwody , ale w ogóle nie da się go obliczyć jednolicie, ale to nie są funkcje, którymi się interesuję.P/poly−PP/poly−PP/poly …
2
Problem egzaminatora (jednolite generowanie instancji / odpowiedzi decyzji SAT)
Asystentowi kursu udało się napisać program, który (deterministycznie) generuje trudne pytania egzaminacyjne. Teraz chciałaby napisać program, który generuje odpowiednie odpowiedzi. Problem egzaminatora pyta, czy jest to zawsze możliwe; przez egzaminatora Hipoteza stwierdza, że zakładając, P ≠ N PP.≠N.P.\mathsf{P} \neq \mathsf{NP} , to nie : wymyślanie problemów jest łatwiejsze niż wymyślanie …
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.