Dare un algoritmo NL per il complemento di 2-Sat

Question

Domanda 1: Qual è la differenza tra 2sat e il complemento di 2sat?

Domanda 2: È noto che NL è contenuto in P, ma ciò che sappiamo di P su NL? Si può dire che un algoritmo che funziona in P, usa lo spazio NL?

Informazioni che raccolgo

Seguo l'algoritmo di Papadimitriou per risolvere 2-Sat con let dare a 2-Sat un grafico dei nodi connessi in base alle specifiche contenute letterali e clausole in cui le informazioni dei nodi e delle connessioni sono un contenitore in un CNF di 2 letterali per clausola del problema deve essere contenuto in NL supponiamo che stiamo solo lavorando per risolverlo in 1 nastro di scrittura e 1 solo nastro di input per eseguire l'algoritmo

    for i=0 repeat log2(n times)
      Choose Random initial assignment for every literal
         Repeat 2n^2
           -If
             The assignment satisfies all the paths in the sequence
             of clauses, Halt and report 
           -else
             Pick arbitrary unsatisfied clauses and flip the value of its literals
     Report unsatisfiable

Secondo la raggiungibilità a 2-Sat una condizione per la possibilità di non essere portata, se un percorso del grafico in cui vi sono nodi collegati con lo stesso letterale e uno di essi è una negazione, allora il grafico non ha un risultato soddisfacente e Questo sarebbe il caso dell'algoritmo. Questo è lo stesso caso per un complemento di 2sat.

Nella soluzione non deterministica, l'algoritmo potrebbe fornire solo una risposta corretta o un falso negativo a seconda della condizione della disposizione delle clausole, ma non recuperare mai un falso positivo a causa della condizione che stabilisce nell'operatore condizionale.

Con la clausola altro, gli algoritmi coprono diverse clausole possibili che capovolgono il letterale in cui la condizione non era soddisfatta e provava nuove opzioni.

L'algoritmo utilizza solo la memoria per mantenere il contatore in esecuzione perché il contatore corrisponde alla dimensione dell'input nello spazio log2 (n)*2n^2 sul nastro di scrittura.

È inoltre dimostrato che 2SAT corrisponde a NL e NL-completi e sappiamo che NL = conl