Pytania otagowane jako nexp

Problemy z NEXP-complete

Wokół jest mnóstwo problemów z kompletnym NP i źródła je zbierające, np. Patrz książka Garey i Johnsona. Byłbym również zainteresowany, aby zobaczyć listę problemów uzupełniających NEXP. Czy jest dostępny? Ponieważ zakładam, że nie ma, otwieram to pytanie (czy to ma być wiki społeczności? Nie wiem o tych rzeczach). W idealnym …

31 cc.complexity-theory complexity-classes big-list nexp

Czy to możliwe, że ? Czy są interesujące konsekwencje takiego ograniczenia? Czy byłoby to sprzeczne z hipotezą o wykładniczym czasie?S.A T.¯¯¯¯¯¯¯¯¯¯∈ N.T.jaM.mi( exp( n0,9) )S.ZAT.¯∈N.T.jaM.mi(exp⁡(n0,9))\overline{SAT} \in NTIME(\exp(n^{0.9}))

12 sat exp-time-algorithms nexp

Klasa złożoności NEXP

Mam problem, który jest w NEXP NP i który może być rozwiązany przez przemienną TM przy użyciu czasu wykładniczego i tylko jednej alternacji (zaczynając od stanu egzystencjalnego).NPNP^{\text{NP}} Czy jest coś znanego na temat NEXP NP ? Czy jest równy NEXP lub innej klasie? Czy istnieją inne problemy niż ogólne (biorąc …

11 cc.complexity-theory reference-request complexity-classes nexp

Czy

Czy oznacza ?E = N EE X P = N E X PmiXP.=N.miXP.\mathsf{EXP}=\mathsf{NEXP}E = N Emi=N.mi\mathsf{E}=\mathsf{NE}

10 cc.complexity-theory conditional-results nexp structural-complexity

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.