Post on 20-Dec-2020
transcript
Berechenbarkeit Berechenbarkeit üüber algebraischen Strukturenber algebraischen Strukturen
Christine GaChristine Gaßßnerner
Greifswald Greifswald 2. Dezember 20082. Dezember 2008
gassnerc@uni-greifswald.de
Berechenbarkeit Berechenbarkeit üüber algebraischen Strukturenber algebraischen Strukturen
Ziel:Ziel:
EinfEinfüührunghrung in die Berechnungsmin die Berechnungsmööglichkeiten unter der glichkeiten unter der Voraussetzung verschiedener StrukturenVoraussetzung verschiedener Strukturen
ZusammenfassungZusammenfassung einiger wichtiger bekannter Resultate in Bezug einiger wichtiger bekannter Resultate in Bezug auf Pauf P--NPNP--ProblemeProbleme
VeranschaulichungVeranschaulichung einer Idee zur Konstruktion von Strukturen mit einer Idee zur Konstruktion von Strukturen mit P= NPP= NP
Wie kWie köönnen neue Relationen von Orakeln abgeleitet werden?nnen neue Relationen von Orakeln abgeleitet werden?
Unter Verwendung von Folien, die fUnter Verwendung von Folien, die füür Vortrr Vorträäge auf Konferenzen erstellt wurden.ge auf Konferenzen erstellt wurden.
gassnerc@uni-greifswald.de
Gegeben: ein Flur und Teppichreste.Gegeben: ein Flur und Teppichreste.
Problem:Problem:(Wegen Mangel an passendem Werkzeug k(Wegen Mangel an passendem Werkzeug köönnen die Reste nicht zerschnitten werden.)nnen die Reste nicht zerschnitten werden.)
Kann der Flur mit Teppichresten ausgelegt werden?Kann der Flur mit Teppichresten ausgelegt werden?
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches Beispiel
TeppichresteEin Flur
gassnerc@uni-greifswald.de
1. L1. Löösungssuche durch sungssuche durch ÜÜberprberprüüfung jeder Mfung jeder Mööglichkeit der Reihe nach,glichkeit der Reihe nach,Anlegen und Kontrolle auf gleiche LAnlegen und Kontrolle auf gleiche Läänge.nge.
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches BeispielEin erster AlgorithmusEin erster Algorithmus
usw.
usw.
gassnerc@uni-greifswald.de
2. L2. Löösungssuche durch sungssuche durch Sortieren der GrSortieren der Größöße nach (unter Verwendung des Ordnungstestes) e nach (unter Verwendung des Ordnungstestes) und danachund danachAnlegen der GrAnlegen der Größöße nach, falls noch nicht zu lang.e nach, falls noch nicht zu lang.
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches BeispielEin zweiter AlgorithmusEin zweiter Algorithmus
gassnerc@uni-greifswald.de
3. L3. Löösungssuche durch sungssuche durch Anlegen der Reihenfolge nach, falls noch nicht zu lang Anlegen der Reihenfolge nach, falls noch nicht zu lang (Vewendung des Ordnungstestes).(Vewendung des Ordnungstestes).
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches BeispielEin dritter AlgorithmusEin dritter Algorithmus
Teppichreste
gassnerc@uni-greifswald.de
Zwei geratene LZwei geratene Löösungen:sungen:
4. L4. Löösungssuche durch sungssuche durch Raten der richtigen LRaten der richtigen Löösung und Anlegen sung und Anlegen (ohne Verwendung des Ordnungstestes).(ohne Verwendung des Ordnungstestes).
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches BeispielNichtdeterminstische LNichtdeterminstische Löösungssuchesungssuche
Ein Flur
TeppichresteEin Flur
gassnerc@uni-greifswald.de
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches BeispielTechnische UmsetzungTechnische Umsetzung
TuringmaschineTuringmaschine ComputerComputer DirektDirekt
Ermittlung d. Ermittlung d. EingabewerteEingabewerte
LLäängen kngen köönnen bis zu einer gewissen Genauigkeit nnen bis zu einer gewissen Genauigkeit gemessen werden.gemessen werden.
entfentfäälltllt
Speicherung Speicherung der Werteder Werte
binbinäär kodiert,r kodiert,jede Ziffer in einer jede Ziffer in einer SpeichereinheitSpeichereinheit
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen
in einer Speichereinheitin einer Speichereinheit
entfentfäälltllt
AdditionAddition exakt,exakt,in mehreren in mehreren
SchrittenSchritten
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
exakt, exakt, durch Anlegen durch Anlegen in einem Schrittin einem Schritt
VergleichVergleich exakt,exakt,in mehreren in mehreren
SchrittenSchritten
exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
ausreichend ausreichend genau auf genau auf einen Blickeinen Blick
Verwendete Verwendete StrukturStruktur
({0, 1}; 0, 1; ({0, 1}; 0, 1; ; ; ==)) ((MM; 0; +; ; 0; +; ≤≤), (), (MM; 0; +; ; 0; +; ==) ) mitmit MM ⊆ℚ⊆ℚ
((ℝℝ; 0; 0 ; +; + ; ; ≤≤),),((ℝℝ; 0; 0 ; +; + ; ; ==))
gassnerc@uni-greifswald.de
TuringmaschineTuringmaschine ComputerComputer DirektDirekt
Ermittlung d. Ermittlung d. EingabewerteEingabewerte
LLäängen kngen köönnen bis zu einer gewissen Genauigkeit nnen bis zu einer gewissen Genauigkeit gemessen werden.gemessen werden.
entfentfäälltllt
Speicherung Speicherung der Werteder Werte
binbinäär kodiert,r kodiert,jede Ziffer in einer jede Ziffer in einer SpeichereinheitSpeichereinheit
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen
in einer Speichereinheitin einer Speichereinheit
entfentfäälltllt
AdditionAddition exakt,exakt,in mehreren in mehreren
SchrittenSchritten
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
exakt, exakt, durch Anlegen durch Anlegen in einem Schrittin einem Schritt
VergleichVergleich exakt,exakt,in mehreren in mehreren
SchrittenSchritten
exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
ausreichend ausreichend genau auf genau auf einen Blickeinen Blick
Verwendete Verwendete StrukturStruktur
({0, 1}; 0, 1; ({0, 1}; 0, 1; ; ; ==)) ((MM; 0; +; ; 0; +; ≤≤), (), (MM; 0; +; ; 0; +; ==) ) mitmit MM ⊆ℚ⊆ℚ
((ℝℝ; 0; 0 ; +; + ; ; ≤≤),),((ℝℝ; 0; 0 ; +; + ; ; ==))
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches BeispielTechnische UmsetzungTechnische Umsetzung
gassnerc@uni-greifswald.de
TuringmaschineTuringmaschine ComputerComputer DirektDirekt
Ermittlung d. Ermittlung d. EingabewerteEingabewerte
LLäängen kngen köönnen bis zu einer gewissen Genauigkeit nnen bis zu einer gewissen Genauigkeit gemessen werden.gemessen werden.
entfentfäälltllt
Speicherung Speicherung der Werteder Werte
binbinäär kodiert,r kodiert,jede Ziffer in einer jede Ziffer in einer SpeichereinheitSpeichereinheit
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen
in einer Speichereinheitin einer Speichereinheit
entfentfäälltllt
AdditionAddition exakt,exakt,in mehreren in mehreren
SchrittenSchritten
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
exakt, exakt, durch Anlegen durch Anlegen in einem Schrittin einem Schritt
VergleichVergleich exakt,exakt,in mehreren in mehreren
SchrittenSchritten
exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
ausreichend ausreichend genau auf genau auf einen Blickeinen Blick
Verwendete Verwendete StrukturStruktur
({0, 1}; 0, 1; ({0, 1}; 0, 1; ; ; ==)) ((MM; 0; +; ; 0; +; ≤≤), (), (MM; 0; +; ; 0; +; ==) ) mitmit MM ⊆ℚ⊆ℚ
((ℝℝ; 0; 0 ; +; + ; ; ≤≤),),((ℝℝ; 0; 0 ; +; + ; ; ==))
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches BeispielTechnische UmsetzungTechnische Umsetzung
gassnerc@uni-greifswald.de
TuringmaschineTuringmaschine ComputerComputer DirektDirekt
Ermittlung d. Ermittlung d. EingabewerteEingabewerte
LLäängen kngen köönnen bis zu einer gewissen Genauigkeit nnen bis zu einer gewissen Genauigkeit gemessen werden.gemessen werden.
entfentfäälltllt
Speicherung Speicherung der Werteder Werte
binbinäär kodiert,r kodiert,jede Ziffer in einer jede Ziffer in einer SpeichereinheitSpeichereinheit
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen
in einer Speichereinheitin einer Speichereinheit
entfentfäälltllt
AdditionAddition exakt,exakt,in mehreren in mehreren
SchrittenSchritten
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
exakt, exakt, durch Anlegen durch Anlegen in einem Schrittin einem Schritt
VergleichVergleich exakt,exakt,in mehreren in mehreren
SchrittenSchritten
exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
ausreichend ausreichend genau auf genau auf einen Blickeinen Blick
Verwendete Verwendete StrukturStruktur
({0, 1}; 0, 1; ({0, 1}; 0, 1; ; ; ==)) ((MM; 0; +; ; 0; +; ≤≤), (), (MM; 0; +; ; 0; +; ==) ) mitmit MM ⊆ℚ⊆ℚ
((ℝℝ; 0; 0 ; +; + ; ; ≤≤),),((ℝℝ; 0; 0 ; +; + ; ; ==))
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches BeispielTechnische UmsetzungTechnische Umsetzung
gassnerc@uni-greifswald.de
TuringmaschineTuringmaschine ComputerComputer DirektDirekt
Ermittlung d. Ermittlung d. EingabewerteEingabewerte
LLäängen kngen köönnen bis zu einer gewissen Genauigkeit nnen bis zu einer gewissen Genauigkeit gemessen werden.gemessen werden.
entfentfäälltllt
Speicherung Speicherung der Werteder Werte
binbinäär kodiert,r kodiert,jede Ziffer in einer jede Ziffer in einer SpeichereinheitSpeichereinheit
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen
in einer Speichereinheitin einer Speichereinheit
entfentfäälltllt
AdditionAddition exakt,exakt,in mehreren in mehreren
SchrittenSchritten
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
exakt, exakt, durch Anlegen durch Anlegen in einem Schrittin einem Schritt
VergleichVergleich exakt,exakt,in mehreren in mehreren
SchrittenSchritten
exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
ausreichend ausreichend genau auf genau auf einen Blickeinen Blick
Verwendete Verwendete StrukturStruktur
({0, 1}; 0, 1; ({0, 1}; 0, 1; ; ; ==)) ((MM; 0; +; ; 0; +; ≤≤), (), (MM; 0; +; ; 0; +; ==) ) mitmit MM ⊆ℚ⊆ℚ
((ℝℝ; 0; 0 ; +; + ; ; ≤≤),),((ℝℝ; 0; 0 ; +; + ; ; ==))
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches BeispielTechnische UmsetzungTechnische Umsetzung
gassnerc@uni-greifswald.de
TuringmaschineTuringmaschine ComputerComputer DirektDirekt
Ermittlung d. Ermittlung d. EingabewerteEingabewerte
LLäängen kngen köönnen bis zu einer gewissen Genauigkeit nnen bis zu einer gewissen Genauigkeit gemessen werden.gemessen werden.
entfentfäälltllt
Speicherung Speicherung der Werteder Werte
binbinäär kodiert,r kodiert,jede Ziffer in einer jede Ziffer in einer SpeichereinheitSpeichereinheit
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen
in einer Speichereinheitin einer Speichereinheit
entfentfäälltllt
AdditionAddition exakt,exakt,in mehreren in mehreren
SchrittenSchritten
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
exakt, exakt, durch Anlegen durch Anlegen in einem Schrittin einem Schritt
VergleichVergleich exakt,exakt,in mehreren in mehreren
SchrittenSchritten
exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
ausreichend ausreichend genau auf genau auf einen Blickeinen Blick
Verwendete Verwendete StrukturStruktur
({0, 1}; 0, 1; ({0, 1}; 0, 1; ; ; ==)) ((MM; 0; +; ; 0; +; ≤≤), (), (MM; 0; +; ; 0; +; ==) ) mitmit MM ⊆ℚ⊆ℚ
((ℝℝ; 0; 0 ; +; + ; ; ≤≤),),((ℝℝ; 0; 0 ; +; + ; ; ==))
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches BeispielTechnische UmsetzungTechnische Umsetzung
gassnerc@uni-greifswald.de
TuringmaschineTuringmaschine ComputerComputer DirektDirekt
Ermittlung d. Ermittlung d. EingabewerteEingabewerte
LLäängen kngen köönnen bis zu einer gewissen Genauigkeit nnen bis zu einer gewissen Genauigkeit gemessen werden.gemessen werden.
entfentfäälltllt
Speicherung Speicherung der Werteder Werte
binbinäär kodiert,r kodiert,jede Ziffer in einer jede Ziffer in einer SpeichereinheitSpeichereinheit
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen
in einer Speichereinheitin einer Speichereinheit
entfentfäälltllt
AdditionAddition exakt,exakt,in mehreren in mehreren
SchrittenSchritten
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
exakt, exakt, durch Anlegen durch Anlegen in einem Schrittin einem Schritt
VergleichVergleich exakt,exakt,in mehreren in mehreren
SchrittenSchritten
exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
ausreichend ausreichend genau auf genau auf einen Blickeinen Blick
Verwendete Verwendete StrukturStruktur
({0, 1}; 0, 1; ({0, 1}; 0, 1; ; ; ==)) ((MM; 0; +; ; 0; +; ≤≤), (), (MM; 0; +; ; 0; +; ==) ) mitmit MM ⊆ℚ⊆ℚ
((ℝℝ; 0; 0 ; +; + ; ; ≤≤),),((ℝℝ; 0; 0 ; +; + ; ; ==))
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches BeispielTechnische UmsetzungTechnische Umsetzung
gassnerc@uni-greifswald.de
TuringmaschineTuringmaschine ComputerComputer DirektDirekt
Ermittlung d. Ermittlung d. EingabewerteEingabewerte
LLäängen kngen köönnen bis zu einer gewissen Genauigkeit nnen bis zu einer gewissen Genauigkeit gemessen werden.gemessen werden.
entfentfäälltllt
Speicherung Speicherung der Werteder Werte
binbinäär kodiert,r kodiert,jede Ziffer in einer jede Ziffer in einer SpeichereinheitSpeichereinheit
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen
in einer Speichereinheitin einer Speichereinheit
entfentfäälltllt
AdditionAddition exakt,exakt,in mehreren in mehreren
SchrittenSchritten
bis zu einer beschrbis zu einer beschräänkten nkten GrGrößöße der Zahlen e der Zahlen exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
exakt, exakt, durch Anlegen durch Anlegen in einem Schrittin einem Schritt
VergleichVergleich exakt,exakt,in mehreren in mehreren
SchrittenSchritten
exakt,exakt,in einer festen Zeiteinheitin einer festen Zeiteinheit
ausreichend ausreichend genau auf genau auf einen Blickeinen Blick
Verwendete Verwendete StrukturStruktur
({0, 1}; 0, 1; ({0, 1}; 0, 1; ; ; ==)) ((MM; 0; +; ; 0; +; ≤≤), (), (MM; 0; +; ; 0; +; ==) ) mitmit MM ⊆ℚ⊆ℚ
((ℝℝ; 0; 0 ; +; + ; ; ≤≤),),((ℝℝ; 0; 0 ; +; + ; ; ==))
Der erste Teil Der erste Teil –– ein praktisches Beispielein praktisches BeispielTechnische UmsetzungTechnische Umsetzung
gassnerc@uni-greifswald.de
1.1. The uniform model The uniform model of of computationcomputation
2.2. Diagonalization techniques and halting problemsDiagonalization techniques and halting problems
3.3. Structures with Structures with P P ≠≠ NPNP
4.4. Structures and oracles with Structures and oracles with PPAA ≠≠ NPNPA A and and PPA A == NPNPAA
5.5. An idea for the construction of structures with An idea for the construction of structures with P P == NPNP
The second partThe second part
gassnerc@uni-greifswald.de
Representations of programsRepresentations of programs
1: Input: (x1, …, xn) . Guess: (y1, …, yn) ∈ {0, 1}.
2: I2 ≔ I1 + 1;3: Z1 ≔ 1 + Z1 * ZI2;4: if I1 = I3 then goto 9
else goto 5;5: I2 ≔ I2 + 1;6: I3 ≔ I3 + 1;7: Z1 ≔ Z1 + ZI3 *
ZI2;8: goto 4;9: if Z1 = 1 then goto 11
else goto 10;10: Z1 ≔ 0;11: I1 ≔ 1;12: Output: Z1.
A program
A flowchart
Computation Computation pathspaths
gassnerc@uni-greifswald.de
A structure:A structure: ΣΣ = (= (UU ; ; cc11 ,,……, , ccu u ; ; ff11 ,,……, , ffv v ; ; RR11 ,,……, , RRww , =), =)ΣΣ = (= (UU ; (; (ccii))ii∈∈F F ; (; (ffii))ii∈∈GG ; (; (RRii))ii∈∈HH , =), =)
Computation:Computation: ll: : ZZk k ≔≔ ffjj((ZZkk 11,,……, , ZZkkmmj j ));;
ll: : ZZkk ≔≔ ccjj;;
Branching:Branching: ll: : ifif RRjj((ZZkk 11,,……, , ZZkknnjj)) then goto then goto ll1 1 else goto else goto ll22; ;
ll: : ifif ZZkk == ZZjj then goto then goto ll1 1 else goto else goto ll22; ;
Copy:Copy: ll: : ZZIIkk≔≔ ZZIIjj;;
Index computation:Index computation: IIkk≔≔ 1; 1; IIkk≔≔ IIk k + + 1; 1; if if IIkk == IIjj then goto then goto ll1 1 else goto else goto ll22;;
The uniform model of computationThe uniform model of computation
gassnerc@uni-greifswald.de
A structure:A structure: ΣΣ = (= (UU ; ; cc11 ,,……, , ccu u ; ; ff11 ,,……, , ffv v ; ; RR11 ,,……, , RRww , =), =)ΣΣ = (= (UU ; (; (ccii))ii∈∈F F ; (; (ffii))ii∈∈GG ; (; (RRii))ii∈∈HH , =), =)
Computation:Computation: ll: : ZZk k ≔≔ ffjj ((ZZkk 11,,……, , ZZkkmmj j ));;
ll: : ZZkk ≔≔ ccjj ;;
Branching:Branching: ll: : ifif RRjj((ZZkk 11,,……, , ZZkknnjj)) then goto then goto ll1 1 else goto else goto ll22; ;
ll: : ifif ZZkk == ZZjj then goto then goto ll1 1 else goto else goto ll22; ;
Copy:Copy: ll: : ZZIIkk≔≔ ZZIIjj;;
Index computation:Index computation: IIkk≔≔ 1; 1; IIkk≔≔ IIk k + + 1; 1; if if IIkk == IIjj then goto then goto ll1 1 else goto else goto ll22;;
The uniform model of computationThe uniform model of computation
gassnerc@uni-greifswald.de
A structure:A structure: ΣΣ = (= (UU ; ; cc11 ,,……, , ccu u ; ; ff11 ,,……, , ffv v ; ; RR11 ,,……, , RRww , =), =)ΣΣ = (= (UU ; (; (ccii))ii∈∈F F ; (; (ffii))ii∈∈GG ; (; (RRii))ii∈∈HH , =), =)
Computation:Computation: ll: : ZZk k ≔≔ ffjj ((ZZkk 11,,……, , ZZkkmmj j ));;
ll: : ZZkk ≔≔ ccjj ;;
Branching:Branching: ll: : ifif RRjj((ZZkk 11,,……, , ZZkknnjj)) then goto then goto ll1 1 else goto else goto ll22; ;
ll: : ifif ZZkk == ZZjj then goto then goto ll1 1 else goto else goto ll22; ;
Copy:Copy: ll: : ZZIIkk≔≔ ZZIIjj;;
Index computation:Index computation: IIkk≔≔ 1; 1; IIkk≔≔ IIk k + + 1; 1; if if IIkk == IIjj then goto then goto ll1 1 else goto else goto ll22;;
The uniform model of computationThe uniform model of computation
gassnerc@uni-greifswald.de
A structure:A structure: ΣΣ = (= (UU ; ; cc11 ,,……, , ccu u ; ; ff11 ,,……, , ffv v ; ; RR11 ,,……, , RRww , =), =)ΣΣ = (= (UU ; (; (ccii))ii∈∈F F ; (; (ffii))ii∈∈GG ; (; (RRii))ii∈∈HH , =), =)
Computation:Computation: ll: : ZZk k ≔≔ ffjj ((ZZkk 11,,……, , ZZkkmmj j ));;
ll: : ZZkk ≔≔ ccjj ;;
Branching:Branching: ll: : ifif RRjj((ZZkk 11,,……, , ZZkknnjj)) then goto then goto ll1 1 else goto else goto ll22; ;
ll: : ifif ZZkk == ZZjj then goto then goto ll1 1 else goto else goto ll22; ;
Copy:Copy: ll: : ZZIIkk≔≔ ZZIIjj;;
Index computation:Index computation: IIkk≔≔ 1; 1; IIkk≔≔ IIk k + + 1; 1; if if IIkk == IIjj then goto then goto ll1 1 else goto else goto ll22;;
The uniform model of computationThe uniform model of computation
gassnerc@uni-greifswald.de
A structure:A structure: ΣΣ = (= (UU ; ; cc11 ,,……, , ccu u ; ; ff11 ,,……, , ffv v ; ; RR11 ,,……, , RRww , =), =)ΣΣ = (= (UU ; (; (ccii))ii∈∈F F ; (; (ffii))ii∈∈GG ; (; (RRii))ii∈∈HH , =), =)
Computation:Computation: ll: : ZZk k ≔≔ ffjj ((ZZkk 11,,……, , ZZkkmmj j ));;
ll: : ZZkk ≔≔ ccjj ;;
Branching:Branching: ll: : ifif RRjj((ZZkk 11,,……, , ZZkknnjj)) then goto then goto ll1 1 else goto else goto ll22; ;
ll: : ifif ZZkk == ZZjj then goto then goto ll1 1 else goto else goto ll22; ;
Copy:Copy: ll: : ZZIIkk≔≔ ZZIIjj;;
Index computation:Index computation: IIkk≔≔ 1; 1; IIkk≔≔ IIk k + + 1; 1; if if IIkk == IIjj then goto then goto ll1 1 else goto else goto ll22;;
The uniform model of computationThe uniform model of computation
gassnerc@uni-greifswald.de
ℤℤ22 == ({0, 1}; 0, 1; +, ({0, 1}; 0, 1; +, ·· ; ; ==)) ((⇨⇨ Turing machines)Turing machines)
ℝℝ = = ((ℝℝ ; ; ℝℝ ; +; + , , –– , , ·· ; ; ≤≤) ) ((⇨⇨ BSS model)BSS model)
ΣΣstringstring = = ({0, 1}({0, 1}** ; ; εε , , 0, 10, 1; add; add , sub, subll ,, subsubrr ; =); =)
ΣΣtree tree = (tree(= (tree(ℝℝ)) ; nil; concat; nil; concat , root, root , sub, subll , sub, subrr ; = ); = )
concat(concat(aa, , ) , , ) ==
Examples for several structuresExamples for several structures
a
t1 t2
t1 t2
gassnerc@uni-greifswald.de
···
Z11Z10Z9Z8Z7Z6Z5Z4Z3Z2Z1
Z1
TheThe inputinput:: ((ZZ11 ,,……, , ZZnn) ) ≔≔ ((xx11,,……, , xxnn); ); II11≔≔ nn; ; II22≔≔ 1;1;…… ; ; IIkkMM≔≔ 1;1;
Z1
1
1
…
…I1
I2
IkMM
The machine and the inputThe machine and the input
gassnerc@uni-greifswald.de
···
Z11Z10Z9Z8Z7Z6Z5Z4Z3Z2Z1
Z1
TheThe inputinput:: ((ZZ11 ,,……, , ZZnn) ) ≔≔ ((xx11,,……, , xxnn); ); II11≔≔ nn; ; II22≔≔ 1;1;…… ; ; IIkkMM≔≔ 1;1;
Z1
1
1
…
…I1
I2
IkMM
The machine and the inputThe machine and the input
x1 x2 x3 x4
gassnerc@uni-greifswald.de
···
Z11Z10Z9Z8Z7Z6Z5Z4Z3Z2Z1
Z1
TheThe inputinput:: ((ZZ11 ,,……, , ZZnn) ) ≔≔ ((xx11,,……, , xxnn); ); II11≔≔ nn; ; II22≔≔ 1;1;…… ; ; IIkkMM≔≔ 1;1;
4
x1 x2 x3 x4
Z4
Z1
1
1
x4x1 x2 x3 x4 x4 x4 x4 x4
…
…I1
I2
IkMM
The machine and the inputThe machine and the input
The size of the input
gassnerc@uni-greifswald.de
The class DECThe class DECΣΣDecidable problemsDecidable problems
B B ⊆⊆ U U ∞∞, , aa,, bb∈∈ U U areare constants with constants with a a ≠≠ b. b.
B B ∈∈ DECDECΣΣ
if the characteristic function is computable,if the characteristic function is computable,
if there is a machine withif there is a machine with
Input:Input: ((xx11,,……, , xxnn) ) ∈∈ U U ∞∞;;
OutputOutput aa (or halt) if (or halt) if ((xx11,,……, , xxnn) ) ∈∈ BB. . AcceptanceAcceptance..
Output Output b b (or no halt) if (or no halt) if ((xx11,,……, , xxnn) ) ∉∉ BB.. Deterministic rejection.Deterministic rejection.
gassnerc@uni-greifswald.de
The class DECThe class DECΣΣDecidable problemsDecidable problems
B B ⊆⊆ U U ∞∞, , aa,, bb∈∈ U U areare constants with constants with a a ≠≠ b. b.
B B ∈∈ DECDECΣΣ
if the characteristic function is computable,if the characteristic function is computable,
if there is a machine withif there is a machine with
Input:Input: ((xx11,,……, , xxnn) ) ∈∈ U U ∞∞;;
OutputOutput aa (or halt) if (or halt) if ((xx11,,……, , xxnn) ) ∈∈ BB. . AcceptanceAcceptance..
Output Output b b (or no halt) if (or no halt) if ((xx11,,……, , xxnn) ) ∉∉ BB.. Deterministic rejection.Deterministic rejection.
gassnerc@uni-greifswald.de
The class DECThe class DECΣΣDecidable problemsDecidable problems
B B ⊆⊆ U U ∞∞, , aa,, bb∈∈ U U areare constants with constants with a a ≠≠ b. b.
B B ∈∈ DECDECΣΣ
if the characteristic function is computable,if the characteristic function is computable,
if there is a machine withif there is a machine with
Input:Input: ((xx11,,……, , xxnn) ) ∈∈ U U ∞∞;;
OutputOutput aa (or halt) if (or halt) if ((xx11,,……, , xxnn) ) ∈∈ BB. . AcceptanceAcceptance..
Output Output b b (or no halt) if (or no halt) if ((xx11,,……, , xxnn) ) ∉∉ BB.. Deterministic rejection.Deterministic rejection.
gassnerc@uni-greifswald.de
The class DECThe class DECΣΣDecidable problemsDecidable problems
B B ⊆⊆ U U ∞∞, , aa,, bb∈∈ U U areare constants with constants with a a ≠≠ b. b.
B B ∈∈ DECDECΣΣ
if the characteristic function is computable,if the characteristic function is computable,
if there is a machine withif there is a machine with
Input:Input: ((xx11,,……, , xxnn) ) ∈∈ U U ∞∞;;
OutputOutput aa (or halt) if (or halt) if ((xx11,,……, , xxnn)) ∈∈ BB. . AcceptanceAcceptance..
Output Output b b (or no halt) if (or no halt) if ((xx11,,……, , xxnn) ) ∉∉ BB.. Deterministic rejection.Deterministic rejection.
gassnerc@uni-greifswald.de
The class DECThe class DECΣΣDecidable problemsDecidable problems
B B ⊆⊆ U U ∞∞, , aa,, bb∈∈ U U areare constants with constants with a a ≠≠ b. b.
B B ∈∈ DECDECΣΣ
if the characteristic function is computable,if the characteristic function is computable,
if there is a machine withif there is a machine with
Input:Input: ((xx11,,……, , xxnn) ) ∈∈ U U ∞∞;;
OutputOutput aa (or halt) if (or halt) if ((xx11,,……, , xxnn)) ∈∈ BB. . AcceptanceAcceptance..
Output Output b b (or no halt) if (or no halt) if ((xx11,,……, , xxnn)) ∉∉ BB.. Deterministic rejectionDeterministic rejection..
gassnerc@uni-greifswald.de
xx
HHΣΣ = {(= {(xx11,,……,, xxnn, , CodeCode((MM)) | )) |
xx ∈∈ UU∞∞ & & MM is a deterministic is a deterministic ∑∑--machinemachine
& & M M haltshalts onon xx}}
HHΣΣspec spec = {= {CodeCode((MM) |) | MM is a deterministic is a deterministic ∑∑--machinemachine
& & M M halts onhalts on CodeCode((MM))}}
Halting problems for Halting problems for ∑∑
gassnerc@uni-greifswald.de
1.1. The set of machines is cThe set of machines is countable.ountable. Assume that Assume that HHΣΣspecspec is decidable.is decidable.
⇒⇒ There is anThere is an MM recognizingrecognizing the complementthe complement of of HHΣΣspecspec. .
Halt?Halt? bin(1)bin(1) ······ bin(bin(ii)) ······ bin(bin(jj)) ······ ······MM11 yes / noyes / no∶∶ ······
MMii yesyes∶∶ ······
MMjj nono∶∶ ······∶∶MM no / yes ··· no ··· yes ··· ···
Diagonalization techniquesDiagonalization techniquesThe undecidability of the Halting problem The undecidability of the Halting problem HHΣΣ (for Turing machines)(for Turing machines)
gassnerc@uni-greifswald.de
1.1. The set of machines is cThe set of machines is countable.ountable. Assume that Assume that HHΣΣspecspec is decidable.is decidable.
⇒⇒ There is anThere is an MM recognizingrecognizing the complementthe complement of of HHΣΣspecspec. .
Halt?Halt? bin(1)bin(1) ······ bin(bin(ii)) ······ bin(bin(jj)) ······ ······MM11 yes / noyes / no∶∶ ······
MMii yesyes∶∶ ······
MMjj nono∶∶ ······∶∶MM no / yes ··· no ··· yes ··· ···
Diagonalization techniquesDiagonalization techniquesThe undecidability of the Halting problem The undecidability of the Halting problem HHΣΣ (for Turing machines)(for Turing machines)
gassnerc@uni-greifswald.de
1.1. The set of machines is cThe set of machines is countable.ountable. Assume that Assume that HHΣΣspecspec is decidable.is decidable.
⇒⇒ There is anThere is an MM recognizingrecognizing the complementthe complement of of HHΣΣspecspec..
Halt?Halt? bin(1)bin(1) ······ bin(bin(ii)) ······ bin(bin(jj)) ······ ······MM11 yes / noyes / no∶∶ ······
MMii yesyes∶∶ ······
MMjj nono∶∶ ······∶∶MM no / yesno / yes ······ nono ······ yesyes ······ ······
Diagonalization techniquesDiagonalization techniquesThe undecidability of the Halting problem The undecidability of the Halting problem HHΣΣ (for Turing machines)(for Turing machines)
gassnerc@uni-greifswald.de
2.2. The codes of machines are ordered.The codes of machines are ordered. Assume that Assume that HHΣΣspecspec is decidable.is decidable.
⇒⇒ There is anThere is an MM recognizingrecognizing the complementthe complement of of HHΣΣspecspec..
Diagonalization techniquesDiagonalization techniquesThe undecidability of the Halting problem The undecidability of the Halting problem HHΣΣ (for (for ((ℝℝ ; ; ℝℝ ; +, ; +, ––, , ·· ; ; ≤≤))))
Halt?Halt? ······ ······ CodeCode((MMii)) ······ CodeCode((MMjj)) ······ ······∶∶ ······∶∶ ······
MMii yesyes∶∶ ······
MMjj nono∶∶ ······∶∶MM ······ ······ nono ······ yesyes ······ ······
gassnerc@uni-greifswald.de
3.3. ∑∑ arbitrary (We can generalize the result.)arbitrary (We can generalize the result.)
Assume:Assume: HHΣΣ is decidableis decidable..⇒⇒ HHΣΣ
specspec is decidableis decidable..⇒⇒ The complement of The complement of HHΣΣ
specspec
is semiis semi--decidable by adecidable by a ∑∑--machinemachine MM..
⇒⇒ MM halts halts onon CodeCode((MM))⇔⇔ MM does not haltdoes not halt onon CodeCode((MM))..
⇒⇒
Diagonalization techniquesDiagonalization techniquesThe undecidability of the Halting problem The undecidability of the Halting problem HHΣΣ (for any structure)(for any structure)
gassnerc@uni-greifswald.de
A machine A machine M M decides a problem decides a problem in polynomial timein polynomial time
if there is some if there is some polynomialpolynomial ppM M ssuch that uch that
MM halts forhalts for x =x = ((xx11,,……, , xxnn) ) withinwithin ppM M ((nn)) steps.steps.
Each instruction is executedEach instruction is executed within within oneone fixed time unit.fixed time unit.
⇨⇨ PPΣΣ ⊆⊆ DECDECΣΣ ((PPΣΣ ≙≙ problems are decidable in polynomial time)problems are decidable in polynomial time)
The class PThe class PΣΣComputation in polynomial timeComputation in polynomial time
gassnerc@uni-greifswald.de
The nonThe non--determinism:determinism:
guess(guess(ZZkk);); Arbitrary elements can be guessed!Arbitrary elements can be guessed!
⇨⇨ PPΣΣ⊆⊆ NPNPΣΣ
NonNon--deterministicdeterministic acceptance:acceptance: output output aa by means of guessed elements.by means of guessed elements.NonNon--deterministicdeterministic rejection:rejection: if the input cannot be accepted.if the input cannot be accepted.
NPNPΣΣ⊈⊈DECDECΣΣ⇒⇒ PPΣΣ ≠≠ NPNPΣΣ wegen wegen PPΣΣ⊆⊆ DECDECΣΣ und und PPΣΣ⊆⊆ NPNPΣΣ..
The class NPThe class NPΣΣThe nonThe non--deterministic instructionsdeterministic instructions
gassnerc@uni-greifswald.de
The nonThe non--determinism:determinism:
guess(guess(ZZkk);); Arbitrary elements can be guessed!Arbitrary elements can be guessed!
⇨⇨ PPΣΣ⊆⊆ NPNPΣΣ
NonNon--deterministicdeterministic acceptance:acceptance: output output aa by means of guessed elements.by means of guessed elements.NonNon--deterministicdeterministic rejection:rejection: if the input cannot be accepted.if the input cannot be accepted.
NPNPΣΣ⊈⊈DECDECΣΣ⇒⇒ PPΣΣ ≠≠ NPNPΣΣ wegen wegen PPΣΣ⊆⊆ DECDECΣΣ und und PPΣΣ⊆⊆ NPNPΣΣ..
The class NPThe class NPΣΣThe nonThe non--deterministic instructionsdeterministic instructions
gassnerc@uni-greifswald.de
∑∑ PP∑∑ = = NPNP∑∑??
((ℂℂ ; ; ℂℂ ; +, ; +, ––, , ·· ; ; ==)) ??
((ℝℝ ; ; ℝℝ ; +, ; +, ––, , ·· ; ; ≤≤)) ??
((ℝℝ ; ; ℝℝ ; +, ; +, ––, , ·· ; ; ==)) no no ((≤≤))
((ℚℚ; ; ℚℚ ; +, ; +, ––, , ·· ; ; ≤≤), (), (ℚℚ; ; ℚℚ ; +, ; +, ––, , ·· ; ; ==)) no no (rational square numbers)(rational square numbers)
((ℝℝ ; ; ℝℝ ; +, ; +, –– ; ; ≤≤)) ??
((ℝℝ ; ; ℝℝ ; +, ; +, –– ; ; ==)) no no (Meer / Koiran) (Meer / Koiran)
((ℤℤ ; ; ℤℤ ; +, ; +, –– ; ; ≤≤), (), (ℤℤ ; ; ℤℤ ; +, ; +, –– ; ; ==)) no no (even integers)(even integers)
((ℤℤ ; ; 11; (; (φφss))ss∈∈ℤℤ; ; ==) ) φφss((xx) = ) = sxsx no no (no (no NPNP--complete problem)complete problem)
Some PSome P∑∑ ≟≟ NPNP∑∑ problemsproblems for several structures for several structures
gassnerc@uni-greifswald.de
∑∑= = ℤℤ = = ((ℤℤ; 0, 1; ; 0, 1; ··, , +, +, −−; =); =)
A =A ={({(x,x,……,x,x)) | | ∃∃y y ((x=yx=y²²))}. }.
AA ∈∈ NPNP∑∑ (we can guess (we can guess y y ∈∈ℤℤ).).
AA ∉∉ PP∑∑::
ExampleExample for Pfor P∑∑ ≠≠ NPNP∑∑
p1(x)=0
p2(x)=0
pk(x)=0
no
no
no
yes
yes
yesThe machine halts after t steps.
We cannot separate
A and ℤ \ A.Only a finite number of zeros.
gassnerc@uni-greifswald.de
∑∑= = ℤℤ = = ((ℤℤ; 0, 1; ; 0, 1; ··, , +, +, −−; =); =)
A =A ={({(x,x,……,x,x)) | | ∃∃y y ((x=yx=y²²))}. }.
AA ∈∈ NPNP∑∑ ((we can guesswe can guess y y ∈∈ℤℤ).).
AA ∉∉ PP∑∑::
ExampleExample for Pfor P∑∑ ≠≠ NPNP∑∑
p1(x)=0
p2(x)=0
pk(x)=0
no
no
no
yes
yes
yesThe machine halts after t steps.
Only a finite number of zeros.
gassnerc@uni-greifswald.de
∑∑= = ℤℤ = = ((ℤℤ; 0, 1; ; 0, 1; ··, , +, +, −−; =); =)
A =A ={({(x,x,……,x,x)) | | ∃∃y y ((x=yx=y²²))}. }.
AA ∈∈ NPNP∑∑ ((we can guesswe can guess y y ∈∈ℤℤ).).
AA ∉∉ PP∑∑::
ExampleExample for Pfor P∑∑ ≠≠ NPNP∑∑
p1(x)=0
p2(x)=0
pk(x)=0
no
no
no
yes
yes
yesThe machine halts after t steps.
We cannot separate
AA and and ℤℤ \\ A.A.
Only a finite number of zeros.
gassnerc@uni-greifswald.de
Some PSome P∑∑--NPNP∑∑ problemsproblemsfor structures over numbersfor structures over numbers
∑∑ PP∑∑ = = DDNPNP∑∑?? DNPDNP∑∑ == NPNP∑∑??
((ℂℂ ; ; ℂℂ ; +, ; +, ––, , ·· ; ; ==)) ?? ??
((ℝℝ ; ; ℝℝ ; +, ; +, ––, , ·· ; ; ≤≤)) ?? ??
((ℝℝ ; ; ℝℝ ; +, ; +, ––, , ·· ; ; ==)) ?? no no ((≤≤))
((ℝℝ ; ; ℝℝ ; +, ; +, –– ; ; ≤≤)) ?? yes yes (Koiran)(Koiran)
((ℝℝ ; ; ℝℝ ; +, ; +, –– ; ; ==)) no no (Meer)(Meer) yes yes (Koiran)(Koiran)((ℤℤ ; ; ℤℤ ; +, ; +, –– ; ; ≤≤)) ?? no no (even integers)(even integers)
((ℤℤ ; ; ℤℤ ; +, ; +, –– ; ; ==)) no no (for groups)(for groups) no no (even integers)(even integers)
DN DN ≙≙ digitally nondigitally non--deterministic:deterministic:yy11,,……, , yym m ∈∈ {0{0 , 1} , 1}
gassnerc@uni-greifswald.de
∑∑==ℤℤaddadd == ((ℤℤ; 0, 1;; 0, 1; +, +, −− ; =); =)
A = A = ∪∪nn≥≥11{({(x,x,……,x,x)) ∈∈ ℤℤnn| | xx < < 22nn}. }.
AA∈∈DNPDNP∑∑ ((we can guess the binary code ofwe can guess the binary code of xx: (: (yy11,,……,,yynn))∈∈{0,1}{0,1}nn ).).
A ∉ P∑:
ExampleExample for Pfor P∑∑ ≠≠ DNPDNP∑∑
k1x=m1 no
no
noThe machine halts after p(n) steps
We cannot separate A and ℤn \ Aif 2n > p(n).
k2x=m2
yes
Only a polynomial number of solutions.
yes
kp(t)x=mp(t)
yes
D D ≙≙ digitally.digitally.
gassnerc@uni-greifswald.de
∑∑==ℤℤaddadd == ((ℤℤ; 0, 1;; 0, 1; +, +, −− ; =); =)
A = A = ∪∪nn≥≥11{({(x,x,……,x,x)) ∈∈ ℤℤnn| | xx < < 22nn}. }.
AA∈∈DNPDNP∑∑ ((we can guess the binary code ofwe can guess the binary code of xx:: ((yy11,,……,,yynn))∈∈{0,1}{0,1}nn ).).
A ∉ P∑:
ExampleExample for Pfor P∑∑ ≠≠ DNPDNP∑∑
k1x=m1 no
no
noThe machine halts after p(n) steps
We cannot separate A and ℤn \ Aif 2n > p(n).
k2x=m2
yes
Only a polynomial number of solutions.
yes
kp(t)x=mp(t)
yes
D D ≙≙ digitally.digitally.
gassnerc@uni-greifswald.de
∑∑==ℤℤaddadd == ((ℤℤ; 0, 1;; 0, 1; +, +, −− ; =); =)
A = A = ∪∪nn≥≥11{({(x,x,……,x,x)) ∈∈ ℤℤnn| | xx < < 22nn}. }.
AA∈∈DNPDNP∑∑ ((we can guess the binary code ofwe can guess the binary code of xx:: ((yy11,,……,,yynn))∈∈{0,1}{0,1}nn ).).
AA ∉∉ PP∑∑::
ExampleExample for Pfor P∑∑ ≠≠ DNPDNP∑∑
k1x=m1 no
no
noThe machine halts after p(n) steps
We cannot separate AA andand ℤℤnn \\ AAif if 22nn > > p(n).
k2x=m2
yes
Only a polynomial number of solutions.
yes kp(t)x=mp(t)
yes
D D ≙≙ digitally.digitally.
gassnerc@uni-greifswald.de
DECDECΣΣ ,, PPΣΣ , NP, NPΣΣ
The size of an input The size of an input ((xx11,,……, , xxnn)):: nn..Every Every uu∈∈ UU can be stored in one register.can be stored in one register.
The execution of any instruction:The execution of any instruction: one time unitone time unit (one step)(one step)..The execution of one operation The execution of one operation ≙≙ one time unit.one time unit.
Computation in polynomial time:Computation in polynomial time: output after output after pp((nn)) stepsstepsfor any input for any input ((xx11 ,,……, , xxnn)) and some polynomial and some polynomial pp..
PPΣΣ⊆⊆ NPNPΣΣPPΣΣ⊆⊆ DECDECΣΣNPNPΣΣ⊈⊈DECDECΣΣ ⇒⇒ PPΣΣ ≠≠ NPNPΣΣ
gassnerc@uni-greifswald.de
NPNP--complete problemscomplete problems
The Satisfiability ProblemThe Satisfiability Problem
The NPThe NP--complete problem recognized by a usual universal machinecomplete problem recognized by a usual universal machine
SATSATΣΣ = {(= {(xx,, codecode((ψψ )))) ∈∈ U U ∞∞| | ψψ quantifierquantifier -- freefree ((¬¬, , ∨∨, , ∧∧))-- formulae formulae && ΣΣ ⊨⊨ ∃∃YY ψψ ((xx,, YY )} )}
UNIUNIΣΣ = {= {((bb,,……, , bb,, xx11 ,,……,, xxnn,, CodeCode((MM )))) ∈∈ U U tt++nn++kk| | MM is a nonis a non--deterministic deterministic ∑∑--machinemachine&& MM acceptsaccepts ((xx11 ,,……,, xxnn)) within within tt stepssteps} } ⊆⊆ U U ∞∞
gassnerc@uni-greifswald.de
—————
UNIUNIΣΣ
The meaning The meaning of these NPof these NP--complete problemscomplete problems
A5
The class NP∑
A4
A3
A2
SATSATΣΣ
A1
gassnerc@uni-greifswald.de
—————
UNIUNIΣΣ
The meaning The meaning of these NPof these NP--complete problemscomplete problems
Any problem can be reduced toAny problem can be reduced to SATSATΣΣ and toand to UNIUNIΣΣ in polynomial time.in polynomial time.
A5
The class NP∑
—pol→
← pol —
—pol→
A4
A3
A2
SATSATΣΣ
A1
←pol —
—pol→
—pol→
gassnerc@uni-greifswald.de
—————
UNIUNIΣΣ
The meaning The meaning of these NPof these NP--complete problemscomplete problems
Any problem can be reduced toAny problem can be reduced to SATSATΣΣ and toand to UNIUNIΣΣ in polynomial time.in polynomial time.
A5
The class NP∑
—pol→
—pol→
← pol —
—pol→
A4
A3
A2
SATSATΣΣ
A1—pol→
—pol→
—pol→
—————————pol —————→
——
——
pol ——
-—→
←pol —
gassnerc@uni-greifswald.de
SATSATΣΣ∈∈ NPNPΣΣ . . SATSATΣΣ isis NPNPΣΣ--complete.complete.
SATSATΣΣ∈∈ PPΣΣ ⇒⇒ PPΣΣ = = NPNPΣΣ
SATSATΣΣ∉∉ DECDECΣΣ ⇒⇒ PPΣΣ ≠≠ NPNPΣΣ
UNIUNIΣΣ∈∈ NPNPΣΣ . . UNIUNIΣΣ isis NPNPΣΣ--complete.complete.
UNIUNIΣΣ∈∈ PPΣΣ ⇒⇒ PPΣΣ = = NPNPΣΣ
UNIUNIΣΣ∉∉ DECDECΣΣ ⇒⇒ PPΣΣ ≠≠ NPNPΣΣ
Properties of Properties of SATSATΣΣ and and UNIUNIΣΣ
gassnerc@uni-greifswald.de
Oracle query:Oracle query:
ll: : if if ((ZZ11,,……, , ZZII11)) ∈∈ B B then goto then goto ll1 1 else goto else goto ll2 2 ;;
The length can be computedThe length can be computed by by II11≔≔ 1; 1; II11≔≔ II1 1 + 1; + 1; ……..
B B oracle, oracle, B B ⊆⊆ UU∞∞ = = ∪∪n n ≥≥11UU n n
We will define oracles such thatWe will define oracles such that
PPΣΣQQ ≠≠ NPNPΣΣ
QQ,,
PPΣΣOO = = NPNPΣΣ
OO..
Oracle machinesOracle machines
gassnerc@uni-greifswald.de
UU infinite, infinite, a finite number of operations and relations,a finite number of operations and relations,
{{αα11, , αα22, , αα33,...} ,...} ⊆⊆ U U enumerable enumerable andand decidabledecidable..
Q Q = = QQΣΣ = { (= { (αα tt ,, xx, , CodeCode((M M )) | )) |
xx ∈∈ U U ∞∞ & & MM is a deterministic is a deterministic ∑∑--machinemachine
& & MM((xx))↓↓tt} }
MM acceptsaccepts x =x = ((xx1 1 ,,……, , xxnn) ) ∈∈ UU∞∞ withinwithin tt steps.steps.
Proposition: Proposition: HHΣΣ ∈∈ NPNPΣΣQQ \\ PPΣΣ
QQ. . ((PPΣΣQ Q ⊆⊆ DECDECΣΣ))
An oracleAn oracle QQ with with PPΣΣQQ ≠≠ NPNPΣΣ
Q Q
Using the undecidability of the Halting problem Using the undecidability of the Halting problem HHΣΣ
gassnerc@uni-greifswald.de
A universal oracle:A universal oracle:
∈∈ U U t t
OO = = OOΣΣ = { (= { (bb,,……, , bb,, xx, , CodeCode((M M )) | )) |
xx ∈∈ U U ∞∞ & & MM is a is a nonnon--deterministicdeterministic ∑∑--machinemachine usingusing OO
& & MM((xx))↓↓tt} }
(cp. also Baker, Gill, and Solovay; Emerson; ... for Turing mach(cp. also Baker, Gill, and Solovay; Emerson; ... for Turing machines... )ines... )
Proposition: Proposition: PPΣΣOO = = NPNPΣΣ
OO ..
An oracleAn oracle OOΣΣ with with PPΣΣOOΣΣ = = NPNPΣΣ
OOΣΣ
gassnerc@uni-greifswald.de
Structures over stringsStructures over strings
ΣΣ = = ((U*U* ; ; εε, , aa, , bb,, cc33,,……, , ccuu ; ; addadd, , subsubll, , subsubrr, , ff11,,……, , ffvv ; ; RR11,,……,,RRww, =, =))
((dd11,...,,..., ddkk) ) ∈∈ UU k k ⊂⊂ UU∞∞ stored instored in kk registersregisters
s = ds = d1 1 ······ ddk k ∈∈ U*U* stored in stored in oneone registerregister
d d ∈∈ UU
addadd((ss, , dd) = ) = ssdd subsubll((sdsd) = ) = s s subsubrr((sdsd) = ) = dd
An oracleAn oracle OOΣΣ containing only tuples of length 1containing only tuples of length 1with with PPΣΣ
OOΣΣ = = NPNPΣΣOOΣΣ ??
!!
gassnerc@uni-greifswald.de
Recall: Recall: PPΣΣOOΣΣ = = NPNPΣΣ
OOΣΣ and and PPΣΣQQΣΣ ≠≠ NPNPΣΣ
QQΣΣ forfor
OOΣΣ = { (= { (bb,,……, , bb,, xx, , CodeCode((M M )) | )) | xx ∈∈ ((UU**))∞∞& & MM is a nonis a non--deterministic deterministic ∑∑--machine usingmachine using OOΣΣ & & MM((xx))↓↓tt} }
QQΣΣ = { (= { (bb······bb,, xx, , CodeCode((M M )) | )) | xx ∈∈ ((UU**))∞∞& & MM is a deterministic is a deterministic ∑∑--machinemachine & & MM((xx))↓↓tt} }
Theorem: Theorem: There isThere is notnot an oracle an oracle OO with with
bb ······bb ··string(string(xx)) ·· string(string(CodeCode((M M )) )) ∈∈ OO⇔⇔ xx ∈∈ ((UU**))∞∞
& & MM is a nonis a non--deterministic deterministic ∑∑--machine usingmachine using OO& & MM((xx))↓↓t t ..
An oracleAn oracle OOΣΣ containing only tuples of length 1containing only tuples of length 1with with PPΣΣ
OOΣΣ = = NPNPΣΣOOΣΣ ??
t t ××
t t ××
No set !
gassnerc@uni-greifswald.de
An additional relation An additional relation RRon on paddedpadded codescodes
of the elements of a universal oracle of the elements of a universal oracle OOwith with PPΣΣ
OO = = NPNPΣΣOO
Binary treesBinary treeswith decidable identity with decidable identity
relationrelation(Ga(Gaßßner, Dagstuhl 2004)ner, Dagstuhl 2004)
StringsStringswith operations for with operations for
adding and deleting the adding and deleting the last characterlast character
(Ga(Gaßßner, CiE 2007)ner, CiE 2007)
Structures with P = NP Structures with P = NP
P = N
Pfor
P = NPfor
gassnerc@uni-greifswald.de
The idea The idea -- similar treessimilar trees
A tree of computation paths The paths corresponding to the strings satisfying R
gassnerc@uni-greifswald.de
The description of UNIThe description of UNIΣΣRR by a treeby a tree
dk dk−1 dk−2 ··· d2 d1
≙ d1··· dk−1dk∈ U*
gassnerc@uni-greifswald.de
The description of UNIThe description of UNIΣΣRR by a treeby a tree
dk dk−1 dk−2 ··· d2 d1
≙ d1··· dk−1dk∈ U*
in UNIΣR∩ (U*)k
in UNIΣR∩ (U*)k+1
in UNIΣR∩ (U*)k+2
The codes of the tuples
gassnerc@uni-greifswald.de
SomeSome R R with with UNIUNIΣΣRR ∈∈ DECDECΣΣRR
RR((‹‹bbtt, , xx11,..., ,..., xxnn, , CodeCode((MM))››dbldbl)) == truetrue
iff iff ((bbtt, , xx11,..., ,..., xxnn, , CodeCode((MM)))) ∈∈ UNIUNIΣΣRR
a|‹bt, x1,..., xn,Code(M)›|
‹‹ss11,..., ,..., sskk›› ∈∈ U* is the code ofis the code of ((ss11,..., ,..., sskk) ) ∈∈((U*)kk
‹bt, x1,..., xn,Code(M)›
ss ∈∈ U* ⇒⇒ ssdbldbl ==df df ssaa||ss|| ∈∈ U*
The codes:
gassnerc@uni-greifswald.de
SomeSome R R with with UNIUNIΣΣRR ∈∈ DECDECΣΣRR
RR((‹‹bbtt, , xx11,..., ,..., xxnn, , CodeCode((MM))››dbldbl)) == truetrue
iff iff ((bbtt, , xx11,..., ,..., xxnn, , CodeCode((MM)))) ∈∈ UNIUNIΣΣRR
a|‹bt, x1,..., xn,Code(M)›|
‹‹ss11,..., ,..., sskk›› ∈∈ U* is the code ofis the code of ((ss11,..., ,..., sskk) ) ∈∈((U*)kk
‹bt, x1,..., xn,Code(M)›
ss ∈∈ U* ⇒⇒ ssdbldbl ==df df ssaa||ss|| ∈∈ U*
The codes:
⇨ PaddingPadding of strings(by doubling the length)
gassnerc@uni-greifswald.de
ΣΣ == (( U U ; ; cc11 ,,……, , ccuu ; ; ff11,,……, , ffvv ; ; RR11,,……, , RRww , , ==)),,
ΣΣRR= = ((U*U* ; ; εε, , aa, , bb,, cc1 1 ,,……, , ccu u ; ; addadd, , subsubl l , , subsubr r , , ff11'',,……, , ffvv''; ; RR11'',,……, , RRww'', , R R , , ==))
The new operations for slow (!!!) computationThe new operations for slow (!!!) computation
addadd((ss, , dd) =) = sd subsd subll((sdsd) = ) = s subs subrr((sdsd) = ) = dd s s ∈∈ U*U*,, dd∈∈ UU
d dk dk−1 ··· d2 d1
s = d1··· dk−1dk
add(s, d) = d1··· dkd
s
gassnerc@uni-greifswald.de
A tree of computation paths The paths corresponding to the strings satisfying R
Similar treesSimilar trees
gassnerc@uni-greifswald.de
A tree of computation paths The paths corresponding to the strings satisfying R
contains the inputs traversing the red path
Similar treesSimilar trees
gassnerc@uni-greifswald.de
Similar treesSimilar trees
contains the codes of the k-tuples belonging toUNIΣR
∩ (U*)k
A tree of computation paths The paths corresponding to the strings satisfying R
contains the inputs traversing the red path
gassnerc@uni-greifswald.de
Trees and polynomial timeTrees and polynomial time
A tree of computation paths The paths corresponding to the strings satisfying R
cutcuta
cutcut
gassnerc@uni-greifswald.de
Trees and polynomial timeTrees and polynomial time
A tree of computation paths The paths corresponding to the strings satisfying R
a
We cannot distinguish between the codes of the tuples which satisfy Rand which begin here
We cannot distinguish between the inputs traversing these paths
cutcut cutcut
gassnerc@uni-greifswald.de
PPΣΣRR = = NPNPΣΣRR
Proof of Proof of PPΣΣRR = = NPNPΣΣR.R. by a reduction. by a reduction.
UNI UNI =={({(bb,..., ,..., b, b, xx11,..., ,..., xxnn,, CodeCode((M M )) | )) | xx ∈∈ ((U*U*))∞∞ & & MM is is NPNPΣΣRR--mach.mach. & & MM((xx))↓↓tt}}
UNIUNI = RES= RES--UNIUNI (the length of guesses can be restricted)(the length of guesses can be restricted)
Output: Output: a a / / bb
SUBSUB--UNIUNI ((short input strings)short input strings) SUBSUB--UNIUNI⊂⊂ RESRES--UNIUNI
-- Transform the input tuple into a string, Transform the input tuple into a string, -- double the length,double the length,- check the new string by means of check the new string by means of RR..
-- Decompose {Decompose {xx11,..., ,..., xxnn} into equivalence classes, } into equivalence classes, -- replace replace xx11,..., ,..., xxnn by suitable short strings by suitable short strings
such that possible chains are not destroyed.such that possible chains are not destroyed.
gassnerc@uni-greifswald.de
PPΣΣRR = = NPNPΣΣRR
Proof of Proof of PPΣΣRR = = NPNPΣΣR.R. by a reduction. by a reduction.
UNI UNI =={({(bb,..., ,..., b, b, xx11,..., ,..., xxnn,, CodeCode((M M )) | )) | xx ∈∈ ((U*U*))∞∞ & & MM is is NPNPΣΣRR--mach.mach. & & MM((xx))↓↓tt}}
UNIUNI = RES= RES--UNIUNI (the length of guesses can be restricted)(the length of guesses can be restricted)
Output: Output: a a / / bb
SUBSUB--UNIUNI ((short input strings)short input strings) SUBSUB--UNIUNI⊂⊂ RESRES--UNIUNI
-- Transform the input tuple into a string, Transform the input tuple into a string, -- double the length,double the length,- check the new string by means of check the new string by means of RR..
-- Decompose {Decompose {xx11,..., ,..., xxnn} into equivalence classes, } into equivalence classes, -- replace replace xx11,..., ,..., xxnn by suitable short strings by suitable short strings
such that possible chains are not destroyed.such that possible chains are not destroyed.
gassnerc@uni-greifswald.de
PPΣΣRR = = NPNPΣΣRR
Proof of Proof of PPΣΣRR = = NPNPΣΣR.R. by a reduction. by a reduction.
UNI UNI =={({(bb,..., ,..., b, b, xx11,..., ,..., xxnn,, CodeCode((M M )) | )) | xx ∈∈ ((U*U*))∞∞ & & MM is is NPNPΣΣRR--mach.mach. & & MM((xx))↓↓tt}}
UNIUNI = RES= RES--UNIUNI (the length of guesses can be restricted)(the length of guesses can be restricted)
Output: Output: a a / / bb
SUBSUB--UNIUNI ((short input strings)short input strings) SUBSUB--UNIUNI⊂⊂ RESRES--UNIUNI
-- Transform the input tuple into a string, Transform the input tuple into a string, -- double the length,double the length,- check the new string by means of check the new string by means of RR..
-- Decompose {Decompose {xx11,..., ,..., xxnn} into equivalence classes, } into equivalence classes, -- replace replace xx11,..., ,..., xxnn by suitable short strings by suitable short strings
such that possible chains are not destroyed.such that possible chains are not destroyed.
gassnerc@uni-greifswald.de
PPΣΣRR = = NPNPΣΣRR
Proof of Proof of PPΣΣRR = = NPNPΣΣR.R. by a reduction. by a reduction.
UNI UNI =={({(bb,..., ,..., b, b, xx11,..., ,..., xxnn,, CodeCode((M M )) | )) | xx ∈∈ ((U*U*))∞∞ & & MM is is NPNPΣΣRR--mach.mach. & & MM((xx))↓↓tt}}
UNIUNI = RES= RES--UNIUNI (the length of guesses can be restricted)(the length of guesses can be restricted)
Output: Output: a a / / bb
SUBSUB--UNIUNI ((short input strings)short input strings) SUBSUB--UNIUNI⊂⊂ RESRES--UNIUNI
-- Transform the input tuple into a string, Transform the input tuple into a string, -- double the length,double the length,- check the new string by means of check the new string by means of RR..
-- Decompose {Decompose {xx11,..., ,..., xxnn} into equivalence classes, } into equivalence classes, -- replace replace xx11,..., ,..., xxnn by suitable short strings by suitable short strings
such that possible chains are not destroyed.such that possible chains are not destroyed.
gassnerc@uni-greifswald.de
Vielen Dank Vielen Dank ffüür Ihre Aufmerksamkeit.r Ihre Aufmerksamkeit.
Christine GaChristine Gaßßnerner
Greifswald.Greifswald.
Vielen Dank auchVielen Dank auchffüür die Unterstr die Unterstüützung bei der Vorbereitung von Prtzung bei der Vorbereitung von Prääsentationen ansentationen an
Gerald van den Boogaart, Volkmar Liebscher, Rainer Schimming, Gerald van den Boogaart, Volkmar Liebscher, Rainer Schimming, Michael SchMichael Schüürmann u.v.a.rmann u.v.a.
ffüür frr früühere Diskussionen anhere Diskussionen an
Mihai Prunescu, GMihai Prunescu, Güünter Asser, Pascal Koiran (nter Asser, Pascal Koiran (üüber M. P.), Dieter ber M. P.), Dieter Spreen u.v.a. Spreen u.v.a.
Berechenbarkeit Berechenbarkeit üüber algebraischen Strukturenber algebraischen Strukturen
gassnerc@uni-greifswald.de
Our goal:Our goal:A relation A relation R R allows to decide whether allows to decide whether z z ∈∈ OOΣΣ..R R can be definedcan be defined recursively.recursively.
Problems:Problems:Each relation has a fixed arity.Each relation has a fixed arity.OOΣΣ contains tuples of any length.contains tuples of any length.
For many structures: For many structures: The tuples of arbitrary length cannot be encoded by tuples of fiThe tuples of arbitrary length cannot be encoded by tuples of fixed length.xed length.
A solution: A solution: Strings.Strings.
Why do we use strings?Why do we use strings?
gassnerc@uni-greifswald.de
Our goal:Our goal:A relation A relation R R allows to decide whether allows to decide whether z z ∈∈ OOΣΣ..R R can be definedcan be defined recursively.recursively.
Problems:Problems:Each relation has a fixed arity.Each relation has a fixed arity.OOΣΣ contains tuples of any length.contains tuples of any length.
For many structures: For many structures: The tuples of arbitrary length cannot be encoded by tuples of fiThe tuples of arbitrary length cannot be encoded by tuples of fixed length.xed length.
A solution: A solution: Strings.Strings.
Why do we use strings?Why do we use strings?
gassnerc@uni-greifswald.de
Our goal:Our goal:A relation A relation R R allows to decide whether allows to decide whether z z ∈∈ OOΣΣ..R R can be definedcan be defined recursively.recursively.
Problems:Problems:Each relation has a fixed arity.Each relation has a fixed arity.OOΣΣ contains tuples of any length.contains tuples of any length.
For many structures: For many structures: The tuples of arbitrary length cannot be encoded by tuples of fiThe tuples of arbitrary length cannot be encoded by tuples of fixed length.xed length.
A solution: A solution: Strings.Strings.
Why do we use strings?Why do we use strings?
gassnerc@uni-greifswald.de
Our goal:Our goal:A relation A relation R R allows to decide whether allows to decide whether z z ∈∈ OOΣΣ..R R can be definedcan be defined recursively.recursively.
Problems:Problems:Each relation has a fixed arity.Each relation has a fixed arity.OOΣΣ contains tuples of any length.contains tuples of any length.
For many structures: For many structures: The tuples of arbitrary length cannot be encoded by tuples of fiThe tuples of arbitrary length cannot be encoded by tuples of fixed length.xed length.
A solution: A solution: Strings.Strings.
Why do we use strings?Why do we use strings?
gassnerc@uni-greifswald.de
ΣΣ = = ((U* U* ; ; εε, , aa, , bb,, cc33,,……, , ccu u ;; addadd, , subsubll, , subsubrr,, ff11,,……, , ffv v ; ; RR11,,……,,RRww, , RR,, ==))s = ds = d1 1 ······ ddk k ∈∈ U*U* stored in one registerstored in one register((dd11,...,,..., ddkk) ) ∈∈ UU k k ⊂⊂ UU∞∞ stored in stored in kk registersregisters
addadd((ss, , dd) = ) = sd sd subsubll((sdsd) = ) = s s subsubrr((sdsd) = ) = dds s ∈∈ U*U*,, dd∈∈ UU
RRi i ⊆⊆ UU nni i ⊆⊆ ((U*U*)) nni i andand RR⊆⊆ U*U*ffii((ss11, , ……, , ssmmii) ) = = εε ifif ||ssjj| >1| >1 for somefor some jj
Structures over stringsStructures over strings
d1 d2 ··· dk-1 dk d
s s = d1··· dk−1dk
sd = d1··· dkd
gassnerc@uni-greifswald.de
ΣΣ = = ((U* U* ; ; εε, , aa, , bb,, cc33,,……, , ccu u ;; addadd, , subsubll, , subsubrr,, ff11,,……, , ffv v ; ; RR11,,……,,RRww, , RR,, ==))s = ds = d1 1 ······ ddk k ∈∈ U*U* stored in one registerstored in one register((dd11,...,,..., ddkk) ) ∈∈ UU k k ⊂⊂ UU∞∞ stored in stored in kk registersregisters
addadd((ss, , dd) = ) = sdsd subsubll((sdsd) = ) = s s subsubrr((sdsd) = ) = dds s ∈∈ U*U*,, dd∈∈ UU
RRi i ⊆⊆ UU nni i ⊆⊆ ((U*U*)) nni i andand RR⊆⊆ U*U*ffii((ss11, , ……, , ssmmii) ) = = εε ifif ||ssjj| >1| >1 for somefor some jj
Structures over stringsStructures over strings
d1 d2 ··· dk-1 dk d
s s = d1··· dk−1dk
sd = d1··· dkd
gassnerc@uni-greifswald.de
ΣΣ = = ((U* U* ; ; εε, , aa, , bb,, cc33,,……, , ccu u ;; addadd, , subsubll, , subsubrr,, ff11,,……, , ffv v ; ; RR11,,……,,RRww, , RR,, ==))s = ds = d1 1 ······ ddk k ∈∈ U*U* stored in one registerstored in one register((dd11,...,,..., ddkk) ) ∈∈ UU k k ⊂⊂ UU∞∞ stored in stored in kk registersregisters
addadd((ss, , dd) = ) = sdsd subsubll((sdsd) = ) = s s subsubrr((sdsd) = ) = dds s ∈∈ U*U*,, dd∈∈ UU
RRi i ⊆⊆ UU nni i ⊆⊆ ((U*U*)) nni i andand RR⊆⊆ U*U*ffii((ss11, , ……, , ssmmii) ) = = εε ifif ||ssjj| >1| >1 for somefor some jj
Structures over stringsStructures over strings
d1 d2 ··· dk-1 dk d
s s = d1··· dk−1dk
sd = d1··· dkd
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma. Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k ..2.2. The maximal chains form trees. Every tree has only one minimal eThe maximal chains form trees. Every tree has only one minimal element.lement.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma. Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k ..2.2. The maximal chains form trees. Every tree has only one minimal eThe maximal chains form trees. Every tree has only one minimal element.lement.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
ss
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma. Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k . . 2.2. The maximal chains form trees. Every tree has only one minimal eThe maximal chains form trees. Every tree has only one minimal element.lement.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
ss
r
a 1) r = sa add(s, a) = r subl(r) =s
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma. Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k ..2.2. The maximal chains form trees. Every tree has only one minimal eThe maximal chains form trees. Every tree has only one minimal element.lement.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
ss
r
a 1) r = sa add(s, a) = r subl(r) =s
b 2) r = sb add(s, b) = r subl(r) =s
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma. Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k ..2.2. The maximal chains form trees. Every tree has only one minimal eThe maximal chains form trees. Every tree has only one minimal element.lement.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
ss
r
a 1) r = sa add(s, a) = r subl(r) =s
b 2) r = sb add(s, b) = r subl(r) =s
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma. Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k ..2.2. The maximal chains form trees. Every tree has only one minimal eThe maximal chains form trees. Every tree has only one minimal element.lement.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
s a
b
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma. Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k ..2.2. The maximal chains form trees. Every tree has only one minimal eThe maximal chains form trees. Every tree has only one minimal element.lement.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
s
s1
a
b
1.
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma.Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k . . 2.2. The maximal chains form trees. Every tree has only one minimal eThe maximal chains form trees. Every tree has only one minimal element.lement.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
s
s1
a
b
1.
s2
s1
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma.Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k ..2.2. The maximal chains form trees. Every tree has only one minimal eThe maximal chains form trees. Every tree has only one minimal element.lement.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
s
s1
s2
a
b
1.
s3
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma.Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k . . 2.2. The maximal chains form trees. Every tree has only one minimal eThe maximal chains form trees. Every tree has only one minimal element.lement.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
s
s1
s2
s3
s4
a
b
1.
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma. Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k ..2.2. The maximal chains form trees.The maximal chains form trees. Every tree has only one minimal element.Every tree has only one minimal element.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
s a
b
2.
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma.Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k . . 2.2. The maximal chains form trees. The maximal chains form trees. Every tree has only one minimal element.Every tree has only one minimal element.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
s a
b
2.one minimal element
a second minimal element
a third minimal element
2.
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma.Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k . . 2.2. The maximal chains form trees. Every tree has only one minimal eThe maximal chains form trees. Every tree has only one minimal element.lement.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
s a
b
3.one minimal element
a second minimal element
a third minimal element
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Example:Example: ΣΣ = = ({({aa, , bb}}* * ; ; εε, , aa, , bb; ; addadd, , subsubll; =; =))
Definition:Definition: s s ⊂⊂11 r r ⇔⇔ subsubll((rr) = ) = ss..
Lemma.Lemma. For For tt steps of a machine holds:steps of a machine holds:1.1. The input values, the guesses, and the new computed values form The input values, the guesses, and the new computed values form maximal chains maximal chains
ss1 1 ⊂⊂11 ······ ⊂⊂11 ssk k ..2.2. The maximal chains form trees. Every tree has only one minimal eThe maximal chains form trees. Every tree has only one minimal element.lement.3.3. The predecessors The predecessors r r ⊂⊂11 ss11 of the minimal elementsof the minimal elements ss11 are not computed.are not computed.
Corollary: Corollary: The minimal elements can be replaced without changing the coThe minimal elements can be replaced without changing the computation path.mputation path.
s a
b
one minimal element
a second minimal element
a third minimal element
Computation over stringsComputation over strings
gassnerc@uni-greifswald.de
Our goal:Our goal:Structures Structures ΣΣ with with NPNPΣΣ⊆⊆ DECDECΣΣ ..
Problems:Problems:Arbitrary strings can be guessed.Arbitrary strings can be guessed.A new A new RR could imply Hcould imply HΣΣR R ∈∈NPNPΣΣR R \\ DECDEC ΣΣRRfor the halting problem Hfor the halting problem HΣΣR R ..
Solution: Solution: Padding strings: Padding strings:
RR((ss) ) ⇒⇒ ((∃∃r r ∈∈ U*U* )) (( s s = = rara||rr|| ).).
It allows to replace It allows to replace long inputs and guesses long inputs and guesses by short strings over by short strings over {{aa, , bb}.}.
Why do we pad the codes?Why do we pad the codes?
gassnerc@uni-greifswald.de
Our goal:Our goal:Structures Structures ΣΣ with with NPNPΣΣ⊆⊆ DECDECΣΣ ..
Problems:Problems:Arbitrary strings can be guessed.Arbitrary strings can be guessed.A new A new RR could imply Hcould imply HΣΣR R ∈∈NPNPΣΣR R \\ DECDEC ΣΣRR
for the halting problem Hfor the halting problem HΣΣR R ..
Solution: Solution: Padding strings: Padding strings:
RR((ss) ) ⇒⇒ ((∃∃r r ∈∈ U*U* )) (( s s = = rara||rr|| ).).
It allows to replace It allows to replace long inputs and guesses long inputs and guesses by short strings over by short strings over {{aa, , bb}.}.
Why do we pad the codes?Why do we pad the codes?
gassnerc@uni-greifswald.de
Our goal:Our goal:Structures Structures ΣΣ with with NPNPΣΣ⊆⊆ DECDECΣΣ ..
Problems:Problems:Arbitrary strings can be guessed.Arbitrary strings can be guessed.A new A new RR could imply Hcould imply HΣΣR R ∈∈NPNPΣΣR R \\ DECDEC ΣΣRR
for the halting problem Hfor the halting problem HΣΣR R ..
Solution: Solution: Padding strings: Padding strings:
RR((ss) ) ⇒⇒ ((∃∃r r ∈∈ U*U* )) (( s s = = rara||rr|| ).).
It allows to replace It allows to replace long inputs and guesses long inputs and guesses by short strings over by short strings over {{aa, , bb}.}.
…
…
…
…
The paths corresponding to the strings satisfying R
Why do we pad the codes?Why do we pad the codes?
gassnerc@uni-greifswald.de
Our goal:Our goal:Structures Structures ΣΣ with with NPNPΣΣ⊆⊆ DECDECΣΣ ..
Problems:Problems:Arbitrary strings can be guessed.Arbitrary strings can be guessed.A new A new RR could imply Hcould imply HΣΣR R ∈∈NPNPΣΣR R \\ DECDEC ΣΣRR
for the halting problem Hfor the halting problem HΣΣR R ..
Solution: Solution: Padding strings: Padding strings:
RR((ss) ) ⇒⇒ ((∃∃r r ∈∈ U*U* )) (( s s = = rara||rr|| ).).
It allows to replace It allows to replace long inputs and guesses long inputs and guesses by short strings over by short strings over {{aa, , bb}.}.
The paths corresponding to the strings satisfying R
…
…
…
…
∈U(=k)
∈U(=k+1)
Compare talk at CiE 2006.
U(=m) ={r : |r |= m}
k
Why do we pad the codes?Why do we pad the codes?
gassnerc@uni-greifswald.de
Our goal:Our goal:Structures Structures ΣΣ with with NPNPΣΣ⊆⊆ DECDECΣΣ ..
Problems:Problems:Arbitrary strings can be guessed.Arbitrary strings can be guessed.A new A new RR could imply Hcould imply HΣΣR R ∈∈NPNPΣΣR R \\ DECDEC ΣΣRR
for the halting problem Hfor the halting problem HΣΣR R ..
Solution: Solution: Padding strings: Padding strings:
RR((ss) ) ⇒⇒ ((∃∃r r ∈∈ U*U* )) (( s s = = rara||rr|| ).).
It allows to replace It allows to replace long inputs and guesses long inputs and guesses by short strings over by short strings over {{aa, , bb}.}.
The paths corresponding to the strings satisfying R
strings satisfying Rstrings satisfying R
Why do we pad the codes?Why do we pad the codes?
gassnerc@uni-greifswald.de
Our goal:Our goal:Structures Structures ΣΣ with with NPNPΣΣ⊆⊆ DECDECΣΣ ..
Problems:Problems:Arbitrary strings can be guessed.Arbitrary strings can be guessed.A new A new RR could imply Hcould imply HΣΣR R ∈∈NPNPΣΣR R \\ DECDEC ΣΣRR
for the halting problem Hfor the halting problem HΣΣR R ..
Solution: Solution: Padding strings: Padding strings:
RR((ss) ) ⇒⇒ ((∃∃r r ∈∈ U*U* )) (( s s = = rara||rr|| ).).
It allows to replace It allows to replace long inputs and guesses long inputs and guesses by short strings over by short strings over {{aa, , bb}.}.
The paths corresponding to the strings satisfying R
strings satisfying Rstrings satisfying R
r1
r ∈ U *
Why do we pad the codes?Why do we pad the codes?
gassnerc@uni-greifswald.de
ΣΣ == ((U* U* ; ; aa, , bb, , cc3 3 ,,……, , ccu u ; ; ff1 1 ,,……, , ffv v ; ; RR1 1 ,,……, , RRw w , =) , =) ΣΣRR = Expansion of = Expansion of ΣΣ by by RR
A universal oracle:A universal oracle:
Let Let WWΣΣ ⊂⊂ ((U*U*))∞∞ withwith PPΣΣWWΣΣ = = NPNPΣΣ
WWΣΣ (derived from (derived from OOΣΣ ))..
The relation The relation RR::
rr11······ rrk k aa ||rr11······ rrkk| | ∈∈ RR ⇔⇔ ((rr11,...,,..., rrk k ) ) ∈∈ WWΣΣ
Theorem: Theorem: PPΣΣRR = = NPNPΣΣR R ..
The new relation The new relation RR
gassnerc@uni-greifswald.de
ΣΣ == ((U* U* ; ; aa, , bb, , cc3 3 ,,……, , ccu u ; ; ff1 1 ,,……, , ffv v ; ; RR1 1 ,,……, , RRw w , =) , =) ΣΣRR = Expansion of = Expansion of ΣΣ by by RR
A universal oracle:A universal oracle:
Let Let WWΣΣ ⊂⊂ ((U*U*))∞∞ withwith PPΣΣWWΣΣ = = NPNPΣΣ
WWΣΣ (derived from (derived from OOΣΣ ))..
The relation The relation RR::
rr11······ rrk k aa ||rr11······ rrkk| | ∈∈ RR ⇔⇔ ((rr11,...,,..., rrk k ) ) ∈∈ WWΣΣ
Theorem: Theorem: PPΣΣRR = = NPNPΣΣR R ..
The new relation The new relation RR
gassnerc@uni-greifswald.de
ΣΣ == ((U* U* ; ; aa, , bb, , cc3 3 ,,……, , ccu u ; ; ff1 1 ,,……, , ffv v ; ; RR1 1 ,,……, , RRw w , =) , =) ΣΣRR = Expansion of = Expansion of ΣΣ by by RR
A universal oracle:A universal oracle:
Let Let WWΣΣ ⊂⊂ ((U*U*))∞∞ withwith PPΣΣWWΣΣ = = NPNPΣΣ
WWΣΣ (derived from (derived from OOΣΣ ))..
The relation The relation RR::
rr11······ rrk k aa ||rr11······ rrkk| | ∈∈ RR ⇔⇔ ((rr11,...,,..., rrk k ) ) ∈∈ WWΣΣ
Theorem: Theorem: PPΣΣRR = = NPNPΣΣR R ..
The new relation The new relation RR
gassnerc@uni-greifswald.de
Vielen Dank Vielen Dank ffüür Ihre Aufmerksamkeit.r Ihre Aufmerksamkeit.
Christine GaChristine Gaßßnerner
Greifswald.Greifswald.
Vielen Dank auchVielen Dank auchffüür die Unterstr die Unterstüützung bei der Vorbereitung von Prtzung bei der Vorbereitung von Prääsentationen ansentationen an
Gerald van den Boogaart, Volkmar Liebscher, Rainer Schimming, Gerald van den Boogaart, Volkmar Liebscher, Rainer Schimming, Michael SchMichael Schüürmann u.v.a.rmann u.v.a.
ffüür frr früühere Diskussionen anhere Diskussionen an
Mihai Prunescu, GMihai Prunescu, Güünter Asser, Pascal Koiran (nter Asser, Pascal Koiran (üüber M. P.), Dieter ber M. P.), Dieter Spreen u.v.a. Spreen u.v.a.
Berechenbarkeit Berechenbarkeit üüber algebraischen Strukturenber algebraischen Strukturen