Parity-L, auch bekannt als L, ist die Menge von Sprachen, die von einer nicht deterministischen Turing-Maschine erkannt werden, die nur zwischen einer geraden Anzahl oder einer ungeraden Anzahl von "Akzeptanz" -Pfaden unterscheiden kann. Eine kürzlich gestellte verwandte Frage wurde von Niel de Beaudrap gestellt.
Meine Frage lautet wie folgt:
Haben wir , wenn NL wissen & xoplus; L? Oder werden diese beiden Klassen für unvergleichlich gehalten?