Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

hyperion

Erfahrener Schreiberling

  • "hyperion" is male

Posts: 422

Date of registration: Oct 8th 2004

41

Saturday, September 30th 2006, 12:40pm

Ich hoffe, dass es richtig ist aber...

Was ein LBA kann, kann eine NTM schon immer. NSPACE(n) sind alle Sprachen, die von einer NTM mit Platz O(n) entschieden werden kann. Dann würde ich über den Satz von Savitch gehen um auf SPACE(n²) zu kommen.

Ebenso mit TIME(2^O(n)): NTIME(n) sind ebenfalls alle Sprachen, die von NTMs in Zeit O(n) entschieden werden können. Dann gibt es noch den Satz, dass NTIME(n) \subseteq TIME(2^O(n)).

Hoffe, dass es so stimmt.
"Der Klügere gibt nach! Eine traurige Wahrheit, sie begründet die Weltherrschaft der Dummheit." --Marie von Ebner-Eschenbach
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

42

Saturday, September 30th 2006, 1:11pm

Quoted

Original von DrChaotica
In einer anderen Aufgabe sollten wir die NP-Härte von QUAD-SAT zeigen...leider hatte ich mir das ähnliche Problem DOUBLE-SAT aus den Übungen nicht mehr angesehen, und den Beweis ausgelassen... aber das ginge doch eventuell mit einer Reduktion von SAT auf QUAD-SAT, indem man der zu erfüllenden Formel einfach neue Variablen anhängt, so dass es neben der ursrünglichen erfüllenden Belegung 2^n-1 weitere gibt, oder?

ja, es reicht aus, wenn man einfach vier neue Variablen an die vorherige Formel mit Konjunktion dran hängt, sodass man eben mind. vier verschiedene Belegungen hat, insofern die vorherige Formel erfüllbar ist.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

DrChaotica

Senior Schreiberling

  • "DrChaotica" is male

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

43

Saturday, September 30th 2006, 1:28pm

Danke euch. Leider fällt einem so etwas immer erst dann ein, wenn die Klausur schon geschrieben ist...aber was soll man sich beschweren, die war auch so noch interessant/spaßig genug.

@Hyperion:
Dann fehlt aber noch der Beweis, dass LBAs nur NSPACE(n)-Sprachen erkennen?

Das Konzept der LBAs habe ich sowieso noch nie verstanden. Entweder hat die Maschine zum Erkennen des Eingabewortes genügend Speicher zur Verfügung, dann ist sie äquivalent zur Turingmaschine.
Oder sie hat nicht genügend Platz zur Verfügung, dann kann sie nur genau so viel erreichen, wie ein endlicher Automat....
  • Send private message

SUPERDIM

Junior Schreiberling

  • "SUPERDIM" is male

Posts: 171

Date of registration: Oct 7th 2004

Location: Hannover

Occupation: 1. Semester M.Sc. Informatik

44

Saturday, September 30th 2006, 1:42pm

Quoted

Original von DrChaotica
[SAT] ist doch die Äquivalenzklasse der NP-vollständigen Sprachen, oder?
Ist dementsprechend [A] für A element P, A!={}, A!=E* die Klasse der P-Sprachen? Oder gab es hier eine Besonderheit, auf die man hätte achten müssen?


Bei [SAT] hab ich auch so geantwortet. Bei [A] war ich mir nicht sicher, müsste aber auf jeden Fall nur Elemente aus P enthalten.

Quoted


In einer anderen Aufgabe sollten wir die NP-Härte von QUAD-SAT zeigen...leider hatte ich mir das ähnliche Problem DOUBLE-SAT aus den Übungen nicht mehr angesehen, und den Beweis ausgelassen... aber das ginge doch eventuell mit einer Reduktion von SAT auf QUAD-SAT, indem man der zu erfüllenden Formel einfach neue Variablen anhängt, so dass es neben der ursrünglichen erfüllenden Belegung 2^n-1 weitere gibt, oder?
(ich hoffe QUAD-SAT element NP zu zeigen gab hier mal mehr Punkte... ;) )


Analog zu DOUBLE-SAT habe ich bei der Reduktion von SAT auf QUAD-SAT zwei statt einer neuen Variablen eingeführt.
  • Send private message

hyperion

Erfahrener Schreiberling

  • "hyperion" is male

Posts: 422

Date of registration: Oct 8th 2004

45

Saturday, September 30th 2006, 2:07pm

Quoted

Original von DrChaotica
Dann fehlt aber noch der Beweis, dass LBAs nur NSPACE(n)-Sprachen erkennen?


Naja, LBAs haben ja beschränken Speicher, n. Ob ich dann eine Mehrband NTM nehme anstatt einer LBA ist doch wurst. So habe ich es auf jeden Fall verstanden.
"Der Klügere gibt nach! Eine traurige Wahrheit, sie begründet die Weltherrschaft der Dummheit." --Marie von Ebner-Eschenbach
  • Send private message

DrChaotica

Senior Schreiberling

  • "DrChaotica" is male

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

46

Saturday, September 30th 2006, 2:53pm

Quoted

Original von SUPERDIM
Analog zu DOUBLE-SAT habe ich bei der Reduktion von SAT auf QUAD-SAT zwei statt einer neuen Variablen eingeführt.

Ah, stimmt...dann muss man nur darauf achten, dass die 2 Variablen in der erweiterten Formel tautologisch verwendet werden.
(Also aus der alten Formel F statt F ^ (avb) eher F^((avb)v!(avb)) oder F^(avbv1) machen, sonst reichen 2 Var. nicht aus...)
  • Send private message

SUPERDIM

Junior Schreiberling

  • "SUPERDIM" is male

Posts: 171

Date of registration: Oct 7th 2004

Location: Hannover

Occupation: 1. Semester M.Sc. Informatik

47

Saturday, September 30th 2006, 4:37pm

Fneu = F ^ (a v !a) ^ (b v !b) mit a,b kommen nicht in F vor tuts.
  • Send private message

3St@n

Junior Schreiberling

  • "3St@n" is male

Posts: 204

Date of registration: Aug 31st 2003

Location: Hildesheim

Occupation: FG SE

48

Saturday, September 30th 2006, 10:19pm

Quoted

Original von SUPERDIM
Fneu = F ^ (a v !a) ^ (b v !b) mit a,b kommen nicht in F vor tuts.


So hab ich das auch gemacht. Also ich bin der Meinung das ich damit mindestens 4 belegungen erzeugen kann.

Gibts denn dieses mal wieder die Musterlösung online? Die Seite ist leider im Moment gerade down.
  • Send private message

Rizzo

Trainee

  • "Rizzo" is male

Posts: 54

Date of registration: Oct 9th 2003

Location: Barsinghausen

49

Sunday, October 8th 2006, 5:29pm

Hallo

Ich wollte mal hören, wann denn ungefähr mit den Ergebnissen der Kombiklausur zu rechnen ist.
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

50

Sunday, October 8th 2006, 7:41pm

Quoted

Original von Rizzo
Ich wollte mal hören, wann denn ungefähr mit den Ergebnissen der Kombiklausur zu rechnen ist.
Ich vermute, daß das wohl noch ein paar Tage dauern wird. Das gesamte Institut für Theoretische Informatik war in der heute endenden Woche auf einem Workshop außerhalb Hannovers. Daher nehme ich an, daß die Klausur bisher noch nicht korrigiert wurde.

Genaueres kann ich dazu aber nicht sagen, da ich seit Oktober in einem anderen Bereich tätig bin. :)
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

Jochen

Trainee

Posts: 36

Date of registration: Oct 11th 2004

Location: Deutschland

Occupation: Informatik

51

Thursday, October 12th 2006, 6:16pm

und hat jemand ne ahnung WO das bekanntgegeben wird wenn die erbgebnisse da sind?
auf dieser seite "Information zu den Klausuren..."?
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

52

Thursday, October 12th 2006, 10:05pm

Also ich schätze, wenn kein Hinweis im Forum erscheinen wird, hängen die Ergebnisse wie immer dann am Brett im ersten Stock der Appelstr. 4
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

3St@n

Junior Schreiberling

  • "3St@n" is male

Posts: 204

Date of registration: Aug 31st 2003

Location: Hildesheim

Occupation: FG SE

53

Tuesday, October 17th 2006, 1:57pm

Hat jemand was gehört wann es denn ungefähr die Ergebnisse geben soll? Meine letzte Infos besagte letzte Woche, aber die ist ja nun schon vorbei.
  • Send private message

DrChaotica

Senior Schreiberling

  • "DrChaotica" is male

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

54

Tuesday, October 17th 2006, 8:12pm

Habe gehört: Morgen. Aber jetzt seid doch nicht so ungedulig ;)
  • Send private message

udo33

Praktikant

Posts: 21

Date of registration: Mar 23rd 2006

55

Wednesday, October 18th 2006, 4:04pm

Erwarten

Sind die Ergebnisse von kombiniertem klausur schon da ?Heute nachtmittag ist es wahr ?
  • Send private message

st0n3d

Junior Schreiberling

  • "st0n3d" is male

Posts: 128

Date of registration: Oct 9th 2003

Location: Hildesheim

56

Wednesday, October 18th 2006, 5:35pm

RE: Erwarten

Ich war um ca. 14 Uhr mal da und da waren noch keine Ergebnisse zu finden X(
"Der Computer rechnet mit allem - nur nicht mit seinem Besitzer."

Dieter Hildebrandt
  • Send private message

udo33

Praktikant

Posts: 21

Date of registration: Mar 23rd 2006

57

Wednesday, October 18th 2006, 6:43pm

warte .......... :(
  • Send private message

3St@n

Junior Schreiberling

  • "3St@n" is male

Posts: 204

Date of registration: Aug 31st 2003

Location: Hildesheim

Occupation: FG SE

58

Friday, October 20th 2006, 12:39pm

War heut schon jemand da, gucken ob was hängt?
  • Send private message

derSmutje

Alter Hase

  • "derSmutje" is male

Posts: 295

Date of registration: Dec 7th 2004

59

Friday, October 20th 2006, 1:56pm

Ja, war vor'm Mittagessen da.
Nein, nix neues...

MfG
/join #inf
  • Send private message

//-\\//-\\

Trainee

  • "//-\\//-\\" is female

Posts: 62

Date of registration: Oct 31st 2004

Location: Hannover

Occupation: Informatik

60

Friday, October 20th 2006, 7:27pm

Henning Schnoor meinte heute, dass die Ergebnisse am Montag ausgehängt werden.
"Die Größe jedes Menschen lässt sich als ein Bruch darstellen. Im Zähler steht das, was er ist ist und im Nenner das, was er von sich denkt."
Fjodr Dostojewski
  • Send private message