Pengurangan mudah dari 3SAT ke masalah jalur Hamiltonian

Ada pengurangan dalam buku Sipser "Pengantar teori komputasi" di halaman 286 dari 3SAT ke masalah jalur Hamilton.

Apakah ada pengurangan yang lebih sederhana?

Secara sederhana yang saya maksud adalah pengurangan yang akan lebih mudah dipahami (untuk siswa).

Apakah ada pengurangan yang menggunakan jumlah variabel linear?

Pengurangan dalam Sipser menggunakan variabel mana k adalah jumlah klausa dan n adalah jumlah variabel. Dengan kata lain, adalah mungkin bagi reduksi untuk meniup ukuran dari s ke O ( s 2 ) . Apakah ada reduksi sederhana di mana ukuran output reduksi linier dalam ukuran inputnya?$O(kn)$$k$$n$$s$$O(s^2)$

Jika tidak memungkinkan, adakah alasannya? Apakah itu menyiratkan hasil yang tidak diketahui dalam kompleksitas / algoritma?

$O(n+k)$$n$$k$

$k$$n$$4k$$4k$$3k$$O(n+k)$