Este evident că şi această problemă se poate uşor transforma într-o instanţă de $2SAT$. Fiecare turist ne dă prin dorinţele sale o expresie literală cu doi literali. Vizitarea sau nevizitarea oraşului de index $i$ va fi reprezentată prin variabila booleană <tex> A_{i} </tex>.  Exemplul din problemă poate fi transformat astfel: <tex> (A_{1} \vee \sim A_{2}) \wedge (A_{2} \vee A_{4}) \wedge (A_{3} \vee A_{1}) </tex>.

h2(#orpath). Orpath (Olimpiadă Rusia)
 
Într-o ţară pacifistă, există $N$ oraşe şi $K$ autobuze $(1 <= N, K <= 100)$. La orele aglomerate ale zilei, nu trebuie să existe două autobuze care merg în acelaşi timp în sensuri opuse. Traseul fiecărui autobuz este un ciclu. Spunem că el merge în sens pozitiv dacă va parcurge oraşele în ordinea $1 2 3 4 1 2 3 4 1 2$ ... sau în sens negativ dacă le parcurge în ordinea $1 4 3 2 1 4 3 2 1 4$ ... Găsiţi o posibilitate de atribuire a sensului fiecărui autobuz astfel ca accidentele de trafic să fie evitate (nu vor exista două autobuze care să se întâlnească şi să aibă sensuri de mers opuse). Pentru fiecare autobuz se vor şti oraşele de pe ruta lui, şi pentru fiecare două oraşe vecine pe rută se va şti timpul necesar autobuzului pentru a ajunge dintr-un oraş în altul. De exemplu, pentru $4$ oraşe unde oricare două sunt la timp de mers egal cu $10$, şi pentru două autobuze cu rutele $1 2 4$ şi $3 4 2$, o soluţie ar fi ca primul autobuz să meargă în sens pozitiv iar celălalt în sens negativ.
 
h3. Soluţie
 
Pentru orice două autobuze vom găsi care sunt sensurile de mers pentru ele astfel ca cele două autobuze să nu se întâlnească şi să provoace un accident. Pentru un sens fixat putem afla pentru un autobuz pe ce interval de timp va fi pe o anumită stradă. El va fi în general pe o stradă $(i, j)$ pe un interval de tipul $[t1 + k*T … t2 + k*T]$ unde $t1$ este timpul din prima rută parcursă pentru a ajunge la $i$, $t2$ timpul pentru a ajunge la $j$ iar $T$ este durata totală a unei rute. Acum, pentru a determina dacă două autobuze se vor întâlni pe o rută $(i, j)$ trebuie ca ele să se deplaseze în sensuri opuse pe această rută, iar intervalele lot $[t1 + k*T1 .. t2 + k*T1]$ se intersectează cu intervalele $[tt1 + p*T2 … tt2 + p*T2]$. Este clar acum că putem transforma problema într-o instanţă de $2-SAT$ prin maparea autobuzelor în variabile logice, a sensurilor de mers în valorile $adevărat$ şi $fals$, iar pentru orice pereche de autobuze să fie o propoziţie logică ce ia valoarea adevărat doar dacă sensurile de mers determinate de variabilele logice asociate autobuzelor sunt compatibile. Mai trebuie determinat într-un mod eficient dacă două clase de intervale de timp se intersectează. Aceasta rămâne ca temă cititorului.