Bisakah satu menunjukkan kekerasan NP dengan pengurangan Turing?

Dalam tulisan Complexity of the Frobenius Problem oleh Ramírez-Alfonsín, masalah terbukti sebagai NP-complete menggunakan pengurangan Turing. Apakah itu mungkin? Bagaimana sebenarnya? Saya pikir ini hanya mungkin dengan pengurangan banyak waktu polinomial. Apakah ada referensi tentang ini?

Apakah ada dua pengertian NP-hardness yang berbeda, bahkan NP-completeness? Tetapi kemudian saya bingung, karena dari sudut pandang praktis, jika saya ingin menunjukkan bahwa masalah saya NP-hard, yang mana yang saya gunakan?

Mereka memulai deskripsi sebagai berikut:

Waktu polinomial Turing reduksi dari masalah ke masalah lain adalah algoritma A yang memecahkan dengan menggunakan subrutin hipotetis A 'untuk menyelesaikan sehingga, jika A' adalah algoritma waktu polinomial untuk maka A akan menjadi waktu polinomial algoritma untuk . Kami mengatakan bahwa dapat Turing dikurangi menjadi . $P_1$ $P_2$ $P_1$ $P_2$ $P_2$ $P_1$ $P_1$ $P_2$

Masalah disebut (Turing) NP-keras jika ada masalah keputusan NP-lengkap sehingga dapat Turing dikurangi menjadi . $P_1$ $P_2$ $P_2$ $P_1$

Dan kemudian mereka menggunakan pengurangan Turing dari masalah NP-lengkap untuk menunjukkan NP-kelengkapan beberapa masalah lainnya.

complexity-theory time-complexity np-complete reductions pengguna2145167
sumber

Jawaban:

Ada (setidaknya) dua gagasan berbeda tentang kekerasan-NP. Gagasan biasa, yang menggunakan pengurangan Karp, menyatakan bahwa bahasa adalah NP-keras jika setiap bahasa di NP Karp-mengurangi ke . Jika kami mengubah pengurangan Karp ke pengurangan Cook, kami mendapatkan gagasan lain. Setiap bahasa yang mengandung Karp-NP-hard juga Cook-NP-hard, tetapi sebaliknya mungkin salah. Misalkan NP berbeda dari CoNp, dan mengambil favorit Anda NP-lengkap bahasa . Maka komplemen dari adalah Cook-NP-hard tetapi tidak Karp-NP-hard. $L$ $L$ $L$ $L$

Alasan bahwa adalah Masak-NP-keras adalah sebagai berikut: mengambil bahasa di NP. Karena adalah NP-hard, ada fungsi polytime sehingga iff $\overline{L}$ $M$ $L$ $f$ $x \in M$ $f(x) \in L$ iff . Pengurangan Cook dari ke membutuhkan , menghitung , memeriksa apakah , dan menampilkan yang sebaliknya. $f(x) \notin \overline{L}$ $M$ $\overline{L}$ $x$ $f(x)$ $f(x) \in \overline{L}$

Alasan bahwa bukan NP-hard (dengan asumsi NP berbeda dari coNP) adalah sebagai berikut. Misalkan adalah NP-hard. Kemudian untuk setiap bahasa dalam coNP, ada pengurangan polytime sehingga iff , atau dengan kata lain, iff . Karena adalah dalam NP, ini menunjukkan bahwa adalah dalam NP, dan juga coNP NP. Ini segera menyiratkan bahwa NP coNP, dan begitu NP = coNP. $\overline{L}$ $\overline{L}$ $M$ $f$ $x \in \overline{M}$ $f(x) \in \overline{L}$ $x \in M$ $f(x) \in L$ $L$ $M$ $\subseteq$ $\subseteq$

Jika beberapa bahasa Cook-NP-keras $L$ adalah P, maka P = NP: untuk setiap bahasa di NP, menggunakan pengurangan Cook ke untuk memberikan algoritma polytime untuk . Jadi dalam pengertian itu, bahasa Cook-NP-complete juga "paling sulit dalam NP". Di sisi lain, mudah untuk melihat bahwa Cook-NP-hard = Cook-coNP-hard: pengurangan Cook untuk dapat dikonversi menjadi pengurangan Cook untuk . Jadi kami kehilangan presisi dengan menggunakan pengurangan Cook. $M$ $L$ $M$ $L$ $\overline{L}$

Mungkin ada kekurangan lain untuk menggunakan pengurangan Cook, tapi saya akan menyerahkannya pada penjawab lain.

Yuval Filmus
sumber

Saya belum sepenuhnya memahami semua ini yang harus saya katakan. Tapi saya punya pertanyaan lain, mungkin Anda bisa menjawab ini (karena tidak ada begitu banyak jawaban lain): bagaimana jika saya memiliki warna merah Turing. dari NP-menyelesaikan masalah A ke beberapa masalah B dan Karp merah. dari masalah B ke masalah C. Apakah itu menetapkan NP-kelengkapan masalah C (keanggotaan tidak ada masalah)? Dan secara umum, dapatkah saya menyebut masalah B NP-hard atau lebih tepatnya (Turing) NP-hard? Terima kasih!

user2145167

Dua pengurangan Karp menyusun pengurangan Karp, dan dua pengurangan Cook mengkomposisi pengurangan Cook. Karena pengurangan Karp juga merupakan pengurangan Cook, jika Anda membuat pengurangan Karp dan pengurangan Cook maka Anda mendapatkan pengurangan Cook. Tetapi secara umum Anda tidak mendapatkan pengurangan Karp.

Yuval Filmus

@YuvalFilmus, bisa tolong jelaskan apa yang ingin Anda maksud dengan

iff

x \in M

$x \in M$

f (x) \in L

$f(x) \in L$

f (x) \notin \bar{L}

$f(x) \notin \overline{L}$

Omar Shehab

Sebuah Karp-pengurangan dari

adalah fungsi

(polytime dalam kasus ini) sehingga

IFF

. Untuk setiap

selalu menyatakan bahwa

iff

, di mana

adalah komplemen dari

(sehubungan dengan kisaran

M

$M$

L

$L$

f

$f$

x \in M

$x \in M$

f (x) \in L

$f(x) \in L$

f, x

$f,x$

f (x) \in L

$f(x) \in L$

f (x) \notin \bar{L}

$f(x) \notin \overline{L}$

\bar{L}

$\overline{L}$

L

$L$

f

$f$

Yuval Filmus

Tidak apa-apa. Pengurangan Turing waktu polinomial adalah pengurangan Cook (seperti dalam teorema Cook-Levin) dan pengurangan masalah NP-complete untuk masalah baru memberikan NP-hardness (seperti halnya pengurangan polynomial-tiem banyak-satu, pengurangan AKA Karp). Memang, pengurangan Karp hanya dibatasi pengurangan Turing saja.

Di mana mereka berbeda (berkaitan dengan pertanyaan ini) adalah dalam menunjukkan keanggotaan. Pengurangan Karp dari masalah ke masalah di NP menunjukkan yang pertama adalah di NP. Pengurangan Cook dalam arah yang sama tidak.

Luke Mathieson
sumber

Terima kasih. Saya bahkan tidak menyadari bahwa seseorang menunjukkan keanggotaan dengan secara eksplisit menggunakan pengurangan Karp. Tapi itu masuk akal. Tapi orang bisa menunjukkan keanggotaan NP dengan menggunakan pengurangan Turing di kedua arah, kan?

user2145167

@ user2145167 tidak, jawaban Yuval memberikan cerita lengkap di sini, tetapi singkatnya, pengurangan Cook lebih lemah, jadi izinkan lebih banyak dalam - mis. Anda dapat beralih dari masalah co-NP melalui pengurangan Cook ke masalah NP-complete, yang tidak berlaku untuk pengurangan Karp.

Luke Mathieson