Problemas intermediários entre L e NL

26

É sabido que a conectividade st direcionada é completa. Resultado da descoberta de Reingold mostrou que não direcionado conectividade st está em . Sabe -se que a conectividade st direcionada planar está na . Cho e Huynh definiram um problema de mochila parametrizado e exibiram uma hierarquia de problemas entre e .L U L c o U LNLLULcoULN LLNL

Eu estou procurando mais problemas que são intermediários entre e N G ou seja, problemas que são:LNL

  • Sabe-se que em mas não conhecida (ou pouco provável) ser N L -completo eNLNL
  • conhecido por ser -Hard mas não é conhecida a estar em L .LL
Shiva Kintali
fonte

Respostas:

13

O problema RL-completo de acessibilidade nos gráficos dirigidos com mistura de tempo polinomial (mostrado por Reingold, Trevisan, e Vadhan em Pseudorandom caminha sobre digrafos regulares e o problema RL vs G ) é no espaço (ver BPHSPACE ( S ) DSPACE ( S 3 / 2 ) por Saks e Zhou ), que é estritamente entre L e Savitch do ligado em NL de o ( log 2 N ) espaço.log3/2(n)BPHSPACE(S)DSPACE(S3/2)O(log2n)

Derrick Stolee
fonte
10

O problema completo de RUL de alcançabilidade em manguezais pode ser resolvido no espaço ( Allender, Lange , RUSPACE ( log n ) DSPACE ( log 2 n / log log n ) ). Um mangue é um gráfico direcionado onde existe no máximo um caminho entre dois vértices.O(log2n/loglogn)RUSPACE(logn)DSPACE(log2n/loglogn)

Derrick Stolee
fonte
1
Veja também: Lange, "Uma classe inequívoca que possui um conjunto completo" STACS '97.
Derrick Stolee
6

Bipartido planar correspondência perfeita é conhecido por ser em (embora não em L Lc o L L ). Como a Acessibilidade Planar se reduz a ela, é L- dura.ULULcoULL

Ref: Samir Datta, Raghav Kulkarni, Raghunath Tewari: A correspondência perfeita nos gráficos planares bipartidos está na UL. Colóquio Eletrônico sobre Complexidade Computacional (ECCC) 17: 201 (2010)

SamiD
fonte
Acho que deveria estar um pouco envergonhado com a resposta obsoleta - mas apenas por uma questão de perfeição.
SamiD 18/07/11