Pertama-tama, saya minta maaf sebelumnya atas kebodohan. Saya sama sekali bukan ahli teori kompleksitas (jauh dari itu! Saya seorang sarjana mengambil kelas pertama saya dalam teori kompleksitas) Inilah pertanyaan saya. Sekarang Teorema Savitch menyatakan bahwa Sekarang saya ingin tahu apakah jika batas bawah ini ketat, yaitu itu adalah sesuatu di sepanjang baris tidak dapat dicapai.
Sepertinya ada sesuatu yang harus ada argumen kombinatorial langsung untuk dibuat di sini - setiap node dalam grafik konfigurasi untuk mesin Deterministic Turing hanya memiliki satu tepi keluar, sementara setiap node dalam grafik konfigurasi mesin Turing Non-Deterministic dapat memiliki lebih banyak dari satu tepi keluar. Algoritme yang dilakukan oleh Savitch adalah mengonversi grafik konfigurasi dengan angka berapa pun yang keluar menjadi grafik konfigurasi dengan tepi yang keluar.
Karena grafik konfigurasi mendefinisikan TM unik (tidak yakin tentang ini), ukuran kombinatorial yang terakhir hampir pasti lebih besar daripada yang sebelumnya. "Perbedaan" ini mungkin merupakan faktor , mungkin kurang - saya tidak tahu. Tentu saja, ada banyak masalah teknis kecil yang harus diselesaikan, seperti bagaimana Anda perlu memastikan tidak ada loop dan sebagainya, tetapi pertanyaan saya adalah apakah ini adalah cara yang masuk akal untuk mulai membuktikan hal seperti ini.