Kompleksitas masalah jaringan switch

Jaringan switch (namanya diciptakan) dibuat dengan tiga jenis node:

• satu simpul Mulai
• satu simpul ujung
• satu atau lebih Switch node

Node switch memiliki 3 pintu keluar: Kiri, Atas, Kanan; memiliki dua status L dan R dan status target TL atau TR . Setiap sakelar dapat dilintasi dengan aturan berikut:

• selalu dari Kiri ke Atas; status sakelar berubah menjadi L
• selalu dari Right to Up; status untuk sakelar berubah menjadi R
• dari Atas ke Kiri hanya jika sakelar dalam keadaan L; negara tidak berubah
• dari Atas ke Kanan jika sakelar dalam keadaan R; negara tidak berubah
• tidak pernah dari Kiri ke Kanan atau Kanan ke Kiri

Gambar 1. Ganti node dalam status L dengan status target TR

Properti ini juga tahan:

• 0, 1 atau 2 dari switch dapat diisolasi (tidak terhubung ke switch lain);
• sebuah jalan dapat "menyentuh" sebuah sakelar untuk mengubah kondisinya: masuk dari Kiri dan keluar dari Kiri atau masuk dari Kanan dan keluar dari Kanan;
• tidak ada batasan berapa kali switch dapat dilalui / disentuh.

Masalah keputusannya adalah: "Apakah jalur dari simpul Mulai ke simpul Akhir ada sedemikian rupa sehingga semua keadaan akhir sakelar cocok dengan keadaan target yang sesuai?"

Jelas, semua sakelar yang awalnya tidak dalam status target mereka harus dilalui (atau disentuh) setidaknya sekali;

Ini adalah penarikan cepat dari jaringan yang sepele (dibuat dengan Excel ... Saya akan membuat yang lebih baik):

Solusi sepele adalah:

S -> 1 -> 2 -> 3 -> 2 -> E -> 1 -> E

EDIT 2:

1. Apakah masalah ini diketahui? ---> Anda memberi saya referensi yang bagus untuk tesis Hearn (grafik kendala);

Masalahnya ada di ; sebelum memposting sketsa bukti saya bahwa itu dalam NP, saya menemukan kesalahan; jadi pertanyaan terbuka lagi:$NPSPACE = PSPACE$

2. Apakah itu ?$\mathsf{NP}$

3. Apakah masalah ada kemungkinan menjadi ?$\mathsf{NP\text{-}complete}$

Masalahnya setidaknya NP-keras, dengan pengurangan dari 3-SAT.

Pertama-tama pertimbangkan masalah menemukan jalur dari Mulai ke Keluar dari grafik terarah berikut dengan batasan bahwa tidak ada jalur yang dapat mengunjungi ketiga simpul (persegi) dari klausa:

$(X1 \lor X2 \lor X3)\land(X1\lor\neg X2\lor X4)$

Kami mentransformasikan grafik ini ke jaringan switch. Untuk ini kami menggunakan tiga gadget:

1. Setiap simpul lingkaran dan tepi dua arah menjadi Kawat , membentuk koneksi antar sakelar.
2. Setiap tepi terarah menjadi gadget satu arah yang terdiri dari satu sakelar (lihat di bawah).
3. Setiap simpul kuadrat mewakili satu dari tiga sakelar yang merupakan bagian dari gadget Klausa (lihat di bawah).

Dalam ilustrasi berikut, sakelar digambarkan sebagai dua panah masuk, salah satunya putus-putus (dinonaktifkan). Arah target digambar dengan lingkaran hitam (sehingga panah padat pada akhirnya harus berada di sisi lingkaran).

Catatan: Kami akan menggunakan huruf tebal untuk membedakan Keluar dari grafik dari keluar dari gadget.

Untuk satu arah gadget, masuk tidak dapat dicapai dari pintu keluar B sampai B telah dicapai dari A . Untuk gadget Clause , pintu masuk $A$$B$$B$$A$$X1$$X2$$X3$$X1'$$X2'$$X3'$

Ingatlah bahwa untuk grafik asli, menemukan jalur yang mengarah ke Keluar dan tidak mengunjungi ketiga simpul kuadrat dari klausa apa pun adalah NP-complete. Sekarang pertimbangkan masalah untuk mencapai Exit dari grafik yang diubah tanpa khawatir tentang posisi target switch.

Perhatikan bahwa setiap jalur yang merupakan solusi untuk masalah grafik asli juga merupakan solusi untuk grafik yang diubah. Jadi asumsikan jalur untuk grafik yang diubah bukan solusi untuk grafik asli. Ini dapat terjadi dalam dua kasus:

1. $B$$A$
2. Sebuah jalur melintasi ketiga jalur dari beberapa gadget Klausul .

Dalam kasus pertama, gadget satu arah harus terlebih dahulu dilintasi ke arah yang dimaksud, dalam hal ini jalur tersebut mungkin juga menghindari melintasinya di tempat pertama.

Jadi pertimbangkan kasus kedua di mana jalur melintasi ketiga sakelar dari beberapa gadget Klausul . Kemudian gadget itu akan memiliki ketiga sakelarnya terbalik (lihat di bawah). Di sinilah kami memanfaatkan posisi target. Perhatikan bahwa abu-abu tulang punggung dari Clause gadget tidak bisa lagi dicapai, yang berarti bahwa switch tidak lagi dapat diarahkan ke posisi target mereka. Dalam hal ini, kami mengatakan bahwa gadget Klausul ini tidak dapat dipulihkan.

Tetap menunjukkan bahwa untuk setiap solusi dari masalah grafik asli, sakelar dari grafik yang diubah dapat ditempatkan di posisi target mereka. Untuk ini, kami menggunakan fakta bahwa kawat Keluar hanya dapat dihubungi ketika ada solusi, atau beberapa gadget Klausul menjadi tidak dapat dipulihkan.

Untuk tempat switch dalam posisi target mereka, kita sekarang dapat menambahkan tambahan satu arah gadget dari Exit kawat ke pintu masuk setiap ada satu arah gadget, serta tiga kabel keluar dari semua Clause gadget. Kemudian, begitu token mencapai Exit , semua gadget Satu Arah tambahan dapat dilintasi (dan dengan demikian dimasukkan ke dalam posisi target mereka), dan juga meletakkan sakelar yang tersisa di posisi target mereka (kecuali ada klausa yang tidak dapat dipulihkan). Akhirnya, token dapat kembali ke Keluar dan teka-teki terpecahkan.

Kami harus berkomentar bahwa gadget Klausul hanya dapat dipulihkan ketika dimasukkan dari pintu keluar yang tidak terbalik; dan karena gadget Satu arah yang ditempatkan di antara gadget Klausa dan variabel berikutnya, ini tidak dapat terjadi sampai kabel Keluar tercapai.

Oleh karena itu, masalah jaringan switch NP-hard.

Masih belum jelas apakah masalahnya ada di NP atau PSPACE-hard. Pengurangan NP-hardness yang membangun jaringan switch planar akan memiliki implikasi besar untuk varian terbatas Sokoban, yaitu karena semua switch setara dengan gadget Sokoban di bawah ini.