Pytania oznaczone «polynomial-hierarchy»

37
Czy ?

Wiemy, że pierwszy poziom hierarchii wielomianowej (tj. NP i co-NP) znajduje się w PP i że . Wiemy również z twierdzenia Tody, że .PP⊆PSPACEPP⊆PSPACEPP \subseteq PSPACEPH⊆PPPPH⊆PPPPH \subseteq P^{PP} Czy wiemy, czy ? Jeśli nie, to dlaczego z wyrocznią jest silniejszy niż ? Czy to możliwe, że i PP...

16
Przykłady

Potrzebuję listę pełnych językach. Istnieją dwa takie problemy wymienione w zoo złożoności , a mianowicie:Σp2Σ2p\Sigma_2^p Minimalny równoważny DNF. Biorąc pod uwagę formułę DNF F i liczbę całkowitą k, czy istnieje formuła DNF równoważna F z k lub mniejszą liczbą literałów? Najkrótszy implant....

12
Czy upadek

Zawarte w między każdym poziomie hierarchii wielomianowej złożoności są różne klasy, w tym , DP , BH k oraz Σ P I ∩ Õ P ja . Z powodu braku lepszej terminologii będę odwoływał się do tych i innych klas pośrednich między poziomami i i i + 1 w hierarchii wielomianowej. Dla celów tego pytania,...