Apakah relatisasi didefinisikan dengan baik?

Menurut BGS teorema [1], ada oracle sehingga . $A$ $P^A\neq NP^A$

Jika operasi relativiasi adalah fungsi yang terdefinisi dengan baik, orang akan berharap bahwa dari seseorang akan dapat menyimpulkan bahwa , misalnya akan mengikuti dari BGS. Namun, masih terbuka. $B\mapsto B^A$ $B^A\neq C^A$ $B\neq C$ $P\neq NP$ $P\neq NP$

Apakah itu berarti bahwa relativiasi bukanlah fungsi yang didefinisikan dengan baik?

Jika demikian, apakah kita memiliki contoh dua relativisasi yang terbukti berbeda dari kelas kompleksitas yang sama?

[1] TP Baker, J. Gill, dan R. Solovay, "Relativizations of the P =? NP Question"

cc.complexity-theory oracles relativization Michael
sumber

Baker-Gill-Solovay menunjukkan dua nubuat: satu di mana P dan NP sama dan satu di mana mereka tidak. Itu menjawab pertanyaan terakhir Anda.

Suresh Venkat

@ SureshVenkat: jika Anda maksudkan bahwa ada oracle

sedemikian sehingga

dan

maka hasil ini (teorema Ladner?) Sebenarnya adalah latar belakang pertanyaan saya. Saya bisa melihat mengapa

tidak berarti

, tapi saya tidak melihat mengapa

tidak berarti

A, B

$A,B$

P^{A} \neq N P^{A}

$P^A\neq NP^A$

P^{B} = N P^{B}

$P^B=NP^B$

P^{B} = N P^{B}

$P^B=NP^B$

P = N P

$P=NP$

P^{A} \neq N P^{A}

$P^A\neq NP^A$

P \neq N P

$P\neq NP$

Michael

@Kaveh akan sangat membantu untuk menunjuk ke jawaban spesifik. Saya melakukan scan cepat pertanyaan dan tidak melihat apa pun.

Suresh Venkat

PS: jawaban singkat untuk pertanyaan Anda adalah bahwa relativisasi bukan operator ekstensional / fungsional pada kelas masalah, bahkan jika notasi terlihat menyiratkan sebaliknya. Tidak ada definisi umum relativisasi untuk kelas masalah, relativiasi didefinisikan untuk model mesin dan model mesin tunggal dapat memiliki beberapa versi relativized berbeda.

Kaveh

fyi fortnow mencatat / mengakui dalam abstraknya bahwa ahli teori kompleksitas menggunakan dan "menyalahgunakan" relativiasi .... tampaknya menjadi wilayah abu-abu dari teori kompleksitas pada waktu ....

vzn

Jawaban:

Anda benar sekali. Operasi relativiasi tidak didefinisikan dengan baik. P dan P ^A adalah objek yang didefinisikan secara independen. Nama-nama itu sugestif, tetapi Anda tidak dapat secara formal menentukan P ^A dari himpunan P. (Anda dapat mendefinisikan P dari P ^A dengan mengatur A menjadi himpunan kosong.) $B\mapsto B^A$

Anggap P ^A sebagai semacam generalisasi P, yang sama dengan P ketika A kosong, tetapi sebaliknya mungkin berbeda. Sekarang jika Anda hanya tahu set P, tidak jelas bagaimana untuk menggeneralisasi ini untuk mendapatkan P ^A . Sebagai analogi, jika saya meminta Anda untuk menggeneralisasi bilangan real, tidak jelas generalisasi apa yang saya cari. Apakah saya memikirkan bidang, cincin, ruang vektor, dll? Alasan ini terjadi adalah bahwa sementara P hanyalah seperangkat bahasa, P ^A didefinisikan dalam istilah mesin. Mesin ini memiliki properti yang ketika A kosong itu memutuskan bahasa yang persis sama dengan P. Anda bisa datang dengan beberapa mesin lain, sebut saja Q ^A , yang juga memiliki properti bahwa ketika A kosong memutuskan bahasa yang sama dengan P Ini tidak berarti bahwa P^A = Q ^A untuk semua A. Ini akan analog dengan menyatakan bahwa jika f (0) = g (0), maka f dan g adalah fungsi yang sama.

Mungkin posting oleh Terence Tao ini akan sangat membantu.

Robin Kothari
sumber

Terima kasih, Robin. Itu jawaban yang bagus, dan tautan ke artikel Tao sangat membantu.

Suresh Venkat

(Saya berasumsi pertanyaan ini pada akhirnya akan dimigrasi ke CS.SE, tetapi saya memposting jawaban saya di sini di cstheory untuk saat ini.)

Secara teknis, orang biasanya tidak menganggap relatisasi sebagai "operator" atau "fungsi"; Namun, saya tidak melihat alasan mengapa Anda tidak bisa mengambil pernyataan dan memetakan pernyataan itu ke versi yang relativized.

Kuncinya adalah bahwa, seperti yang dikatakan orang lain, relativisasi tidak benar-benar didefinisikan pada kelas kompleksitas; sebagai gantinya, itu didefinisikan pada model perhitungan yang Anda gunakan. Selanjutnya, apa yang relatif adalah pernyataan, bukan kelas. (Notasi ini sedikit menyesatkan.)

Contoh dari ini adalah bahwa saya secara teoritis dapat mengatakan bahwa pernyataan relativizes (atau, lebih kecil kemungkinannya, tidak relativize) bahkan jika itu tidak merujuk ke mesin Turing sama sekali. Misalnya, saya dapat mengatakan (dengan jujur), "1 + 1 = 2" relativizes, karena relatif terhadap setiap ramalan yang dapat ditambahkan ke definisi mesin Turing universal saya, 1 + 1 = 2 akan tetap benar.

Jadi jawaban singkatnya adalah: Ya, itu jelas, tetapi tidak di kelas.

Philip White
sumber

P^{A} \neq N P^{A}

$P^A \ne NP^A$

P = N P

$P = NP$

A

$A$

Itulah yang saya maksudkan dalam jawaban saya ... Saya berkata, Anda tidak dapat merelatifkan kelas, Anda merelatifkan pernyataan. Kemampuan untuk merelatifkan lebih dari P dan NP hilang jika Anda tidak dapat meratifikasi lebih dari kelas secara individual; argumen tidak berfungsi jika saya hanya mengatakan "Saya merelatifkan pernyataan, sekarang membalikkan relativiasi dan itu masih harus menahan" lebih dari itu mungkin untuk dikatakan (menggunakan fungsi f (x) = x ^ 2 sebagai contoh) " 5 ^ 2 adalah komposit "->" 5 adalah komposit. "

Philip White

Tidak ada definisi umum tentang relatisasi pernyataan. Hanya ada model komputasi yang relativized. Relativiasi P vs NP mengandaikan bahwa kita telah memperbaiki model P dan NP yang ter-relativisasi sebelumnya.

Kaveh