Parzystość-L vs. NL

13

Parzystość-L, znana również jako , jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko liczbę parzystą lub nieparzystą liczby ścieżek „akceptacji”. Ostatnie powiązane pytanie zadał Niel de Beaudrap.

Moje pytanie jest następujące:

Czy wiemy, czy NL L? Czy te dwie klasy są uważane za nieporównywalne?

Dai Le
źródło

Odpowiedzi: