Spektrum von Phi < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:56 Di 21.12.2010 | | Autor: | Manu87 |
| Aufgabe | Sei [mm] \phi [/mm] ein Satz in einer Sprache der ersten Stufe L. Das Spektrum von [mm] \phi [/mm] ist wie folgt def niert:
[mm] Spec(\phi ) [/mm] := {n [mm] \in [/mm] n [mm] \IZ_{+} [/mm] : Es existiert M [mm] \vDash \phi [/mm] mit |M|= n}.
Wir nennen eine Menge positiver Zahlen X ein Spektrum, falls eine Sprache L und ein L-Satz [mm] \phi [/mm] existieren, so dass X = [mm] Spec( \phi).
[/mm]
Zeigen Sie:
(a) Ist X [mm] \subset \IZ_{+} [/mm] endlich oder hat ein endliches Komplement in [mm] \IZ_{+}, [/mm] dann ist X ein Spektrum.
(b) Nicht jede Teilmenge von [mm] \IZ_{+} [/mm] ist ein Spektrum.
(c) Die Menge der geraden positiven ganzen Zahlen und die Menge der ungeraden positiven ganze Zahlen sind Sprektra.
(d) Sind X und Y Spektra, so auch X [mm] \cup [/mm] Y und X [mm] \cap [/mm] Y .
Die Frage, ob die Klasse der Spektra abgeschlossen unter Komplementbildung ist, ist offen, seit sie in den 1950ern gestellt wurde. Es ist bekannt, dass eine Menge positiver ganzer Zahlen genau
dann ein Spektrum ist, wenn die Menge in NE liegt, d.h. wenn sie in exponentieller Laufzeit durch eine nicht-deterministische Turingmaschine entscheidbar ist. Aber, ebenso wie für andere nicht-deterministische Komplexitätsklassen, ist es nicht bekannt ob NE abgeschlossen unter
Komplementbildung ist. Dies ist verwandt zur logischen Charakterisierung von NP gegeben durch den Satz von Fagin. Details findet man hier:
![[]](/images/popup.gif) Generalized First-Order Spectra and Polynomial-Time Recognizable Sets |
Hilfe! Ich vertseh kein Wort!
Ich bin für alles dankbar! Lösungsansätze, Gedankenstützen, Anregungen usw...
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Do 23.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
