Kesimpulan dari kekuatan matematika terbalik dari teorema minor graph

Katakanlah kita memiliki properti grafik yang dapat diperiksa dalam waktu polinomial nondeterministik, dan bukti dalam sistem formal yang lemah (katakanlah RCA ₀ ) bahwa properti tersebut tertutup kecil. Bisakah kita mengatakan sesuatu tentang kekuatan sistem formal, yang mampu membuktikan bahwa himpunan terbatas anak-anak yang dikecualikan mencirikan properti grafik yang diberikan?

Konteks Telah diketahui secara umum bahwa sudah ada versi sederhana (tanpa label yang diatur dengan baik) dari teorema pohon Kruskal tidak dapat dibuktikan dalam ATR ₀ dan teorema minor minor adalah generalisasi dari teorema itu yang bahkan tidak dapat dibuktikan dalam Π ¹ ₁ -CA ₀ . Friedman menggunakan versi sederhana teorema pohon Kruskal untuk membangun fungsi TREE (n) yang tumbuh cepat , dan menggunakan teorema minor minor untuk membangun fungsi SSCG (n) yang lebih cepat tumbuh . Itu adalah demonstrasi yang bagus dari kesimpulan tentang konten komputasi dari kekuatan matematika terbalik, tetapi mereka meninggalkan pertanyaan yang lebih langsung diajukan di atas tidak terjawab.

Yaitu, terkait dengan teorema minor minor adalah bukti bahwa properti tertutup minor dapat diuji dalam waktu kubik deterministik, jika seseorang mengetahui daftar anak di bawah umur yang dikecualikan untuk properti itu. Oleh karena itu wajar untuk bertanya-tanya betapa "tidak mungkin" itu untuk membuktikan bahwa seseorang telah menemukan semua anak di bawah umur untuk diberikan "mudah" (sebagaimana dibuat tepat dalam pertanyaan) properti tertutup kecil. Karena ini adalah tugas "tidak seragam", tidak jelas bagi saya apakah "ketidakmungkinan" dari tugas ini sama sekali berkaitan dengan "kesulitan" (yaitu membalikkan kekuatan matematika) untuk membuktikan teorema minor graf itu sendiri.

Karena versi sederhana teorema pohon Kruskal mengajukan pertanyaan yang persis sama dengan teorema minor, jawaban mungkin fokus pada masalah yang lebih sederhana, jika mereka mau. Saya hanya menggunakan teorema minor graph, karena pertanyaannya terasa lebih alami seperti itu. (Ada kemungkinan bahwa pertanyaan ini mungkin lebih cocok untuk MSE atau MSO, setidaknya sehubungan dengan mendapatkan jawaban yang pasti. Tetapi motivasi dari pertanyaan ini lebih terkait dengan TCS, jadi saya memutuskan untuk menanyakannya di sini.)

Saya tidak yakin saya mengerti pertanyaan Anda, tetapi jika Anda bertanya betapa sulitnya menghitung set penghalang, Anda mungkin tertarik dengan http://www.jucs.org/doi?doi=10.3217/jucs- 003-11-1194 di mana non computabubility terbukti bahkan jika kelas grafik dapat didefinisikan MSOL. Dalam makalah ini http://www.sciencedirect.com/science/article/pii/S0012365X97830798?via%3Dihub komputabilitasnya terbukti ketika kelas grafik diberikan oleh tata bahasa HR.