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!
 

 

Zusammenhang NP-schwer, NP und entscheidbar

0 Punkte
28 Aufrufe
Guten Abend,

könnte mir jemand kurz die NP Problematik erklären. Folgende Punkte erschließen sich mir nicht ganz:

1) Die Probleme in NP sind alle polynomiell lösbar, was ist mit den Problemen in NP-schwer und in entscheidbar, sind diese auch polynomiell lösbar?

 

2) Kann man nur Probleme z.B. aus NP polynomiell auf ein NP-schweres Problem reduzieren oder geht es auch anders herum (von NP schwer nach NP)?

 

Es sind einfach kleine Verständnisfragen, die mir nicht ganz klar si
Gefragt 17 Jul in Allgemeine Fragen von utxob utxob Lernwillige(r) (120 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.
...