Apa alasan kuat untuk meyakini ?

23

Apa alasan kuat untuk meyakini ? L adalah kelas algoritma ruang log dengan pointer ke input. $L\neq P$

Misalkan L = P untuk saat ini. Seperti apa algoritma ruang-log untuk masalah P-complete dalam garis besarnya?

cc.complexity-theory complexity-classes Jumer
sumber

2

dalam arti itu akan menjadi algoritma kompresi ruang untuk perhitungan mesin T-waktu Turing yang biasanya mengambil ruang P. maka jika L ≠ P maka ada beberapa "(dalam) batas kompresibilitas" dari P. kemungkinan arah konstruksi / pertanyaan / penelitian berdasarkan sudut ini, kompresi urutan run TM

vzn

1

lihat juga memisahkan posting blog L / P & kintalis yang dikutip di sana

vzn

28

Hasil Mulmuley (dari halaman web Mulmuley tanpa paywall) bahwa, dalam model PRAM tanpa operasi bit, " ". (Dalam model boolean biasa di mana tinggal, .) Model ini cukup kuat sehingga hasilnya menyiratkan setiap untuk masalah -complete harus terlihat sangat berbeda dari algoritma yang paling dikenal untuk masalah lengkap. $\mathsf{P} \neq \mathsf{NC}$ $\mathsf{L}$ $\mathsf{L} \subseteq \mathsf{NC}$ $\mathsf{L}$ $\mathsf{P}$ $\mathsf{P}$

Model PRAM tanpa operasi bit adalah model aljabar nonuniform atas (mirip dengan pohon perhitungan aljabar atau model RAM aljabar Blum - Shub - Smale) di mana program tidak seragam dapat bergantung tidak hanya pada jumlah input integer, tetapi juga pada total bitlength mereka. Dengan cara ini itu bukan model aljabar "murni", tetapi hidup di suatu tempat antara aljabar dan boolean. Model ini mencakup algoritma poly-time untuk pemrograman linier, maxflow, mincut, spanning tree tertimbang, jalur terpendek, dan masalah optimisasi kombinatorial lainnya, algoritma ruang log untuk isomorfisma pohon (lihat komentar di bawah), dan algoritma untuk memperkirakan akar polinomial yang kompleks, itulah sebabnya saya mengatakan untuk $\mathbb{Z}$ $\mathsf{L}$ $\mathsf{P}$ Masalah-lengkap (yang, seperti pertanyaan Anda menunjukkan Anda tahu, kebanyakan orang berpikir tidak ada) harus terlihat sangat berbeda dari semua ini.

Joshua Grochow
sumber

Dalam dugaan nya pada halaman 62, bagaimana Mulmuley terkait

dengan mincost-aliran? Mengapa

harus linier dan

a bijection? Dugaan yang tampaknya menyiratkan ada Rank

linear peta (karena peta terbalik dari linear 1-1 peta adalah linear) dievaluasi nol set

dapat menutupi

. Apakah interpretasi saya benar?

S L_{m} (C)

$SL_m(C)$

L

$L$

F

$F$

k

$k$

S L_{m} (C)

$SL_m(C)$

L (n)

$L(n)$

T ....

φ

$\varphi$

φ (x) = det (F (x))

$\varphi(x) = \det(F(x))$

x \in L (n)

$x \in L(n)$

det (F (x)) = 1

$\det(F(x)) = 1$

x \in F^{- 1} (S L_{m})

$x \in F^{-1}(SL_m)$

satu-satunya asumsi adalah yang tampaknya menjadi kasusnya. Cukup menarik! Seperti halnya asumsi dan bukti kompleksitas lainnya - Apakah cara lain diketahui: yaitu jika , apakah ? Saya belum pernah melihat percakapan seperti itu dalam teori kompleksitas atau apakah konversi seperti itu tidak mungkin?

d e t \notin N C^{1}

$det\notin NC^{1}$

d e t \in N C^{1}

$det\in NC^1$

P = N C

$P=NC$

T ....

@ JAS: Saya tidak melihat apa yang Anda maksud dengan "asumsi satu-satunya adalah ...": Saya tidak berpikir itu mengikuti bahwa , jika itu yang Anda katakan ...

det \notin N C^{1} \Rightarrow P \neq N C

$\det \notin NC^1 \Rightarrow P \neq NC$

Joshua Grochow

1

@ JAS: Keyakinan bahwa mendukung dugaan tersebut, tetapi itu tidak menyiratkan dugaan tersebut. Dia menyebutkan yang sebaliknya, bahwa jika pencocokan sempurna maka dugaan itu salah untuk kecil . Sama dengan itu, jika dugaan itu benar maka pencocokan sempurna . Perhatikan bahwa ini adalah arah yang berlawanan dari apa yang Anda katakan.

d e t \notin N C^{1}

$det \notin NC^1$

\in N C^{1}

$\in NC^1$

a

$a$

\notin N C^{1}

$\notin NC^1$

Joshua Grochow

15

Ada serangkaian karya M. Hofmann dan U. Schöpp yang memformalkan gagasan intuitif "algoritma ruang logaritmik tipikal", hanya menggunakan sejumlah pointer konstan ke struktur data input, sebagai bahasa pemrograman PURPLE (program pointer murni dengan perulangan.)

Meskipun program PURPLE tidak menangkap semua (mereka telah terbukti tidak dapat memutuskan koneksi yang tidak diarahkan), ekstensi mereka dengan penghitungan ditampilkan untuk menangkap sebagian besar , tetapi bukan masalah P-lengkap Horn-SAT . Ini ditunjukkan dalam makalah terbaru dalam seri: M. Hofmann, R. Ramyaa dan U. Schöpp: Program Pure Pointer dan Tree Isomorphism, FOSSACS 2013. $\mathsf{L}$ $\mathsf{L}$

Kesimpulannya tampaknya bahwa algoritma ruang logaritmik untuk - masalah lengkap harus sangat tidak tipikal dan melampaui apa yang dapat diterapkan dalam PURPLE dengan penghitungan. $\mathsf{P}$

Jan Johannsen
sumber

5

UNGU dengan penghitungan adalah model yang menarik, dan sesuai dengan intuisi algoritma logspace saya yang naif. Tetapi saya tidak tahu apakah hasil ini adalah bukti yang baik untuk

: mereka bahkan mengatakan "Jadi, satis ﬁ tis Horn tidak dapat diputuskan dalam UNGU ditambah dengan nondeterminisme dan penghitungan juga, tetapi karena alasan itulah masalah LOGSPACE tertentu, yaitu pohon isomorfisme tidak bisa. " Ini pada dasarnya mengatakan bahwa hasilnya benar-benar tentang kelemahan PURPLE + count (sesuai dengan intuisi naif logspace algos) daripada kelemahan L ...

L \neq P

$L \neq P$

Joshua Grochow

3

Kompleksitas deskriptif telah berusaha memberikan beberapa jawaban.

FO (urutan logika pertama), dengan Ord (pemesanan domain) dan TC (transitif penutupan) . $= L$

FO + ord + LFP (titik paling tetap) . $= P$

Jadi muncul pertanyaan - Apakah FO + ord + TC FO + ord + LFP? $\subset$

Di sisi lain, FO + LFP (tanpa ord) bahkan tidak bisa dihitung! Misalnya, tidak dapat mengungkapkan fakta bahwa kardinalitas domain adalah genap. Logika ini tentu saja tidak dapat menangkap - tetapi pertanyaannya adalah, dapatkah ia menangkap atau ? $P$ $L$ $NL$

Lihat misalnya http://www.cs.umass.edu/%7Eimmerman/pub/EATCScolumn.pdf

Dan kemudian, logika orde dua (SO) + Horn menangkap P, sedangkan SO + Krom menangkap NL. Lihat Erich Gradel, Menangkap kelas kompleksitas oleh fragmen-fragmen logika orde dua , Theoretical Computer Science, 1992.

Martin Seymour
sumber

3

FO + LFP tanpa memesan pasti tidak dapat menangkap

, dengan alasan yang Anda kutip: itu tidak dapat dihitung, bahkan modulo 2.

L

$\mathsf{L}$

Jan Johannsen

Setuju. Maka pertanyaannya (atau lebih tepatnya, salah satu pertanyaan) adalah - Apakah FO + LFP (tanpa ord) merupakan subset ketat dari FO + LFP (dengan ord)?

Martin Seymour

0

$\sf{P}$ $\sf{GEN}$ $k$ $\Theta(k \log n)$

NisaiVloot
sumber

Apa alasan kuat untuk meyakini ?

Jawaban: