Bukti bahwa PPAD sulit?

32

Ada justifikasi filosofis yang sering dikutip untuk meyakini bahwa P! = NP bahkan tanpa bukti. Kelas kompleksitas lainnya memiliki bukti bahwa mereka berbeda, karena jika tidak, akan ada konsekuensi "mengejutkan" (seperti runtuhnya hierarki polinomial).

Pertanyaan saya adalah, apa dasar untuk keyakinan bahwa kelas PPAD tidak bisa ditembus? Jika ada algoritma waktu polinomial untuk menemukan kesetimbangan Nash, akankah ini menyiratkan apa pun tentang kelas kompleksitas lainnya? Apakah ada argumen heuristik mengapa itu harus sulit?

cc.complexity-theory complexity-classes gt.game-theory conditional-results Aaron Roth
sumber

Jawaban:

28

PPAD cukup "rendah" di atas P dan tidak banyak yang akan berubah dalam pemahaman kita tentang kompleksitas jika ditunjukkan sama dengan P (kecuali bahwa beberapa masalah dalam PPAD sekarang akan berada di P). "Bukti" utama bahwa PPAD! = P adalah pemisahan oracle, yang pada dasarnya setara dengan fakta kombinatorial bahwa tidak ada "simulasi kotak hitam" ada.

Noam
sumber
8

Buhrman et al. menunjukkan ada oracle relatif di mana semua fungsi TFNP adalah poly-time computable, namun Hirarki Polinomial tidak terbatas. TFNP adalah kelas yang berisi PPAD dan sepupunya. Ini adalah hasil lain yang memperkuat perasaan kami bahwa PPAD yang mudah tidak akan menghasilkan konsekuensi yang tidak mungkin dalam kompleksitas.

Makalah ini adalah "Apakah Hirarki Polinomial Turun jika Fungsi Ke Atas Tidak Terbalik?"

tersedia di situs web Lance Fortnow. Tampaknya versi sebelumnya dari makalah ini berjudul "Melompat ke fungsi dan hierarki polinomial" (versi baru di bawah nama lama ini di situs Lance).

Andy Drucker
sumber
10
Penelusuran TFNP akan secara signifikan lebih mengejutkan daripada PPAD karena yang sebelumnya akan mengesampingkan keberadaan permutasi 1 arah serta menyiratkan P = (NPN persimpangan interseksi).
Noam
8

(Saya kira tidak ada yang pernah menjawab pertanyaan lama ini dengan hasil yang lebih baru; ini dia :)

  • PPSEBUAHD
  • PPSEBUAHD

PPSEBUAHD

Daniel Apon
sumber
2

Meskipun ini telah terbentur, mungkin saya dapat memiliki kesombongan untuk menyebutkan heuristik yang muncul dalam pikiran.

Masalah NP-complete adalah, diberikan sirkuit, apakah ada input yang mengevaluasi ke True?

  • Masalah ini jelas akan mudah jika input diwakili "secara eksplisit" sebagai daftar pasangan input-output, daripada "ringkas" sebagai sirkuit.

  • Masalahnya jelas informasi-secara teori sulit jika inputnya adalah fungsi oracle black-box daripada sirkuit (membutuhkan mencoba semua input).

  • Masalah dalam memisahkan P dari NP, jika benar, terletak pada menunjukkan bahwa program tidak dapat memotong sirkuit secara efisien.

Masalah lengkap PPAD berbagi beberapa karakteristik menarik di sini. Jika Anda memikirkan End-of-the-Line, itu "diberi grafik yang diwakili secara ringkas dengan beberapa batasan, dan sebuah sumber, cari wastafel". Dan itu berbagi tiga poin di atas, saya pikir.

usul
sumber
-1

Makalah ini relevan dengan ini, karena berupaya menunjukkan bahwa PPAD = P: https://arxiv.org/abs/1609.08934

Samuel Schlesinger
sumber
7
Ada banyak makalah yang menunjukkan P = NP. Saya tidak akan menganggapnya relevan sampai peer-review dan diterbitkan dengan benar.
Emil Jeřábek mendukung Monica
Kesalahan pertama adalah baris terakhir dari bukti Lemma 10 di halaman 18, karena "f (alpha, eps) <0 untuk eps = 0 dan lim_alpha f (alpha, eps) = infinity untuk eps> 0" bukan tidak mungkin, bahkan jika f (alpha, epsilon) adalah fungsi kontinu dari alpha dan epsilon. Tetapi karena makalah ini memberikan algoritme eksplisit, Anda tentu juga menginginkan contoh tandingan eksplisit di mana algoritme itu gagal, sebelum Anda dapat mengklaim bahwa Anda menyangkal makalah itu.
Thomas Klimpel