Problemy pośrednie między L i NL

26

Jest dobrze wiadomo, że skierowane st-łączność jest -Complete. Przełom wynik Reingold wykazała, że nieukierunkowane st-łączność jest w L . Płaskie skierowane st-łączności jest znany w U L C O U L . Cho Huynh zdefiniowano sparametryzowanego problemu plecakowego i wykazywał hierarchię problemów między L i N l .NLLULcoULLNL

Szukam więcej problemów, które są pośrednie między i N L, tj. Problemów, które są:LNL

  • Wiadomo, że w , ale nie jest znana (lub raczej) jest N L -Complete iNLNL
  • Wiadomo, że -hard ale wiadomo, że w L .LL
Shiva Kintali
źródło

Odpowiedzi:

13

Problem RL kompletne osiągalności w skierowanych wykresów wielomianowej mieszania w czasie (wskazanym Reingold, Trevisan i Vadhan w pseudolosowy wchodzi w zwykłych digrafach i problem RL wobec L ) w przestrzeń (patrz BPHSPACE ( S ) dSPACE ( S 3 / 2 ) przez Saks Zhou ), która jest ściśle między L i Savitch na związane na NI o ( log 2 n ) przestrzeni.log3/2(n)BPHSPACE(S)DSPACE(S3/2)O(log2n)

Derrick Stolee
źródło
10

O(log2n/loglogn)RUSPACE(logn)DSPACE(log2n/loglogn)

Derrick Stolee
źródło
1
Zobacz także: Lange, „Jednoznaczna klasa posiadająca kompletny zestaw” STACS '97.
Derrick Stolee,
6

ULULcoULL

Ref: Samir Datta, Raghav Kulkarni, Raghunath Tewari: Idealne dopasowanie na dwustronnych wykresach planarnych jest w UL. Electronic Colloquium on Computational Complexity (ECCC) 17: 201 (2010)

SamiD
źródło
Chyba powinienem się trochę zawstydzić z powodu starej odpowiedzi - ale tylko ze względu na kompletność.
SamiD