Contoh saksi panjang logaritmik lebih mudah diverifikasi daripada ditemukan

Pengamatan mudah adalah bahwa jika masalah adalah decidable oleh program non-deterministik waktu polinomial menggunakan O ( log n ) bit nondeterministic (yaitu, semua saksi yang logaritmik panjang), kemudian A ∈ P .$A$$O(\log n)$$A \in \mathsf{P}$

Jika seseorang kemudian mengajukan pertanyaan, "Apakah lebih mudah memverifikasi saksi daripada menemukannya?" untuk masalah seperti itu, dan seseorang menganggap semua polinomial berjalan kali setara, maka jawabannya tidak, karena seseorang dapat menemukan saksi seperti itu dalam waktu polinomial dengan mencari melalui semua saksi potensial.

Tetapi bagaimana jika kita mempertimbangkan perbedaan yang halus antara waktu menjalankan polinomial? Saya bertanya-tanya apakah ada contoh nyata dari masalah alami dalam yang memiliki saksi panjang logaritmik yang lebih mudah diverifikasi daripada menemukan, di mana "lebih mudah" berarti waktu berjalan polinomial yang lebih kecil.$\mathsf{P}$

Misalnya, algoritma yang dikenal untuk pencocokan sempurna dalam grafik membutuhkan waktu polinomial, tetapi lebih dari waktu pada grafik dengan n node. Tetapi mengingat satu set n / 2 pasang node (saksi), mudah untuk memverifikasi dalam waktu O ( n ) bahwa itu adalah pasangan yang cocok. Namun, pencocokan itu sendiri membutuhkan pada Ω ( n ) bit untuk menyandikan.$O(n)$$n$$n/2$$O(n)$$\Omega(n)$

Apakah ada beberapa masalah alami yang mencapai percepatan (jelas) yang sama dalam verifikasi versus temuan, di mana saksi memiliki panjang logaritmik ?

$x$$n$

$O(n^2)$

$\log(n)$$i$$i$$x$$i$$x$$i$$n$$O(n \log n)$