Raum-Zeit-Kompromiss Untergrenzen

13

Nach der Diskussion über untere Schranken für 3SAT [ 1 ] frage ich mich, was die wichtigsten Ergebnisse für untere Schranken sind, die als Raum-Zeit-Kompromisse formuliert wurden. Ich schließe Ergebnisse aus, wie zum Beispiel den Satz von Savitch; Ein guter Beitrag würde sich auf ein einzelnes Problem und seine Grenzen konzentrieren. Ein Beispiel wäre:

"Sei T und S die Laufzeit und der Raum eines jeden SAT-Algorithmus. Dann müssen wir unendlich oft T⋅S≥n2cos (π / 7) −o (1) haben." (Gegeben in [ 1 ] von Ryan Williams.)

oder

"SAT kann nicht gleichzeitig in n 1 + 0 (1) Zeit und n 1 - ε Raum für ε> 0 auf allgemeinen nicht deterministischen Turing-Maschinen mit wahlfreiem Zugriff gelöst werden." (Lance Fortnow in 10.1109 / CCC.1997.612300)

Außerdem füge ich Definitionen von Komplexitätsklassen für natürliche Raum-Zeit-Kompromisse (ohne Schaltungsklassen) hinzu.

Michaël Cadilhac
quelle
1
hmm. ein weiteres Beispiel dafür, dass das CW-Tag nicht benötigt wird.
Suresh Venkat
Was meinen Sie?
Michaël Cadilhac
1
Suresh meint, dass Sie "Community-Wiki" nicht für diese Frage verwenden müssen, wenn Sie die Frage anders formulieren als auf einer großen Liste, und sich genauer mit dem befassen, wonach Sie suchen. Auch ist es wirklich eine "weiche Frage"?
Ryan Williams
Nun, ich möchte eine große Liste, und die Frage, die nicht spezifisch ist, ist meiner Meinung nach ein guter Weg, eine zu bekommen. Ist diese Art von Liste verboten? (Ich kann ziemlich genau ableiten, dass ich etwas falsch gemacht habe, da keine Antwort gegeben wurde, aber ich weiß nicht was.) Dies ist auch eine weiche Frage, da keine intellektuelle Arbeit erforderlich ist.
Michaël Cadilhac
2
Wir hoffen, dies in den FAQ zu klären. Ich würde sagen, dass dies keine weiche Frage ist, weil es technisch ist. Eine weiche Frage ist mehr über Themen rund um die Forschung - wo zur Schule gehen, wie man Papiere liest, etc.
Suresh Venkat

Antworten:

12

Hier einige zusätzliche Referenzen. Weitere Informationen finden Sie in den Papieren, in denen diese zitiert werden.

PT2SΩ(n3)

O(n)O(1)k+1TSΩ(n2)k

So(n)Tω(n)

TSΩ(n2) gilt für Multitape-Turingmaschinen, die SAT lösen und auf Cobhams analoger Untergrenze für PALINDROMES aufbauen.

Ryan Williams
quelle