Hallo,
1) fast richtig, allerdings liegen alle NP-schweren Probleme (nach heutigem Wissensstand, sowie der Annahme in der Aufgabe) außerhalb von P und sind somit deterministisch eben nicht polynomiell berechenbar, sondern nur nichtdeterministisch. Besser wäre es zu sagen, dass NP-Schwere Probleme auch außerhalb von NP liegen können (sich ihre Komplexität von NP-vollständigen Problemen also um mehr als einen polynomiellen Faktor unterscheiden kann)
2) Stimmt
3) Annahme war hier P != NP. C liegt aber in P. Würde sich B (als NP-vollständiges Problem - beachte auch die zweite Eigenschaft von B) auf C polynomialzeit reduzieren lassen, dann wäre C ebenfalls NP-vollständig, es würde also gelten P = NP, was ein Widerspruch zur Annahme ist.
4) Nein, es ist nicht das schwerste Problem, lediglich gehört es zu den "schwersten Problemen in NP", also den NP-vollständigen. Es lassen sich nur Probleme in NP auf NP-vollständige Probleme reduzieren, was aber für B zutrifft.
5) Wir betrachten sonst immer den Fall, dass P != NP ist. Gilt aber P = NP, dann gilt i.A. auch, dass P = NP = NP-vollständig. Aber es gibt eben noch diese zwei Spezialfälle die nicht in NP-vollständig liegen, aber in P=NP.
6) Das hat nichts mit der Zahl der Algorithmen zu tun, sondern mit der Möglichkeit eines Algorithmus, in endlicher Zeit zu entscheiden, ob die Zahl eine Primzahl ist oder nicht. Der einfachste Algorithmus ist der, der alle Zahlen von 2 bis Wurzel(n) durchläuft und eine Division testet. Da n gegeben ist, sind das endlich viele Schritte. Kann n durch keinen der Werte geteilt werden, so ist es eine Primzahl. Kann es durch einen oder mehrere geteilt werden, so ist es keine. Also kann eine Entscheidung (in beide Richtungen) in endlicher Zeit stattfinden
7) Es gilt: Entscheidbare Mengen < aufzählbare Mengen < abzählbare Mengen (< steht dabei für echt Teilmenge). Daraus kann man sich dann die Implikationen herleiten
Ich hoffe, ich konnte dir weiterhelfen.
Viele Grüße
Philippe