Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Lösungsansätze füt a) & b)

–1 Punkt
165 Aufrufe

a) Reicht es hier schon, wenn man den  polynomialzeitalgorithmus von L noch einmal negiert um einen Algorthmus für L-Komplement zu bekommen? Daraus könnte man schließen, das auch dieses Problem von einem deterministischen Automaten in polynomieller Zeit gelöst werden kann und somit L-Komplement in P liegt.

b) Mein Ansatz ist hier, dass NP-Probleme von nichtdeterministischen Turingmaschinen in polynomieller Zeit gelöst werden können und somit das Problem zu lösen deutlich schwieriger ist und exponenziell so groß ist wie Probleme, die von einer deterministischen Turingmaschine gelöst werden können.

Was fehlt hier noch in der Argumentation?-

 

Gefragt 23, Sep 2015 in 2013-N-05 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Ihre Antwort

Ihr anzuzeigender Name (optional):
Datenschutzhinweis: Ihre E-Mail-Adresse wird ausschließlich benutzt, um Ihnen Benachrichtigungen zu schicken. Es gilt die Datenschutzerklärung.
Anti-Spam-Abfrage (Captcha):
Bitte loggen Sie ein oder registrieren sich, um diese Abfrage (Captcha) zu vermeiden.
...