Konteks: Kami hanya mempertimbangkan digraf. Biarkan CYCLE menjadi bahasa grafik dengan siklus; itu adalah masalah NL-lengkap. Biarkan HASEDGE menjadi bahasa grafik dengan setidaknya satu sisi. Kemudian sepele, tidak lagi NL-hard, sementara tetap seperti itu.
Masalah aktual: Saya ingin tahu apakah bahasa masih NL-hard.
Pertanyaan: Untuk rumus FO mana pada kosa kata grafik adalah NL-hard? Apakah properti ini dapat dipilih?
Terima kasih atas masukan Anda!
sumber
Masalah sebenarnya ada di FO. Menguji apakah ada sedemikian rupa sehingga dan jelas dalam FO.( a , c ) , ( b , d ) ∈ E ( G ) ( a , d ) , ( b , c ) ∉ E ( G )a,b,c,d∈V(G) (a,c),(b,d)∈E(G) (a,d),(b,c)∉E(G)
Asumsikan bahwa tidak ada , maka mengakui siklus terarah jika dan hanya jika mengakui siklus terarah dengan panjang dua. Ini dapat disimpulkan dari fakta bahwa untuk dua simpul dan dari , lingkungan dan sedemikian rupa sehingga atau .G G a b G N - ( a ) N - ( b ) N - ( a ) ⊆ N - ( b ) N - ( b ) ⊆ N - ( a )a,b,c,d G G a b G N−(a) N−(b) N−(a)⊆N−(b) N−(b)⊆N−(a)
Dengan demikian, cukup untuk memeriksa apakah ada sedemikian rupa sehingga , yang ada di FO.( a , b ) , ( b , a ) ∈ E ( G )a,b∈V(G) (a,b),(b,a)∈E(G)
Jadi, ada dalam jika dan hanya jikaC Y C L E ∪ N O D I A G ( ∃ a , b , c , d ) [ ( E ( a , b ) ∧ E ( c , d ) ∧ ¬ E ( a , d ) ∧ ¬ E ( b , c ) ) ∨ ( E ( a ,G CYCLE∪NODIAG (∃a,b,c,d)[(E(a,b)∧E(c,d)∧¬E(a,d)∧¬E(b,c))∨(E(a,b)∧E(b,a))]
sumber