Hallo,

kennt jemand irgendwelche nichttrivialen Eigenschaften von Entscheidungsproblemen, vor allem von a) Problemen in der Menge P, b) NP-vollständigen Problemen? Mit nichttrivial meine ich Eigenschaften, die nicht unmittelbar aus der Definition der Problemart folgen. Dass Probleme in der Menge P mit einem Algorithmus mit polynomieller Laufzeit in Bezug auf die Größe der Eingabedaten entschieden werden können, ist beispielsweise eine triviale Eigenschaft.

Mir scheinen solche nichttrivialen Eigenschaften die einzige Möglichkeit zu sein, wie man eventuell beweisen könnte, dass P ungleich NP ist.

LG
Claus (Adok)

P.S.: Bevor jemand diesen Thread als Anlass für unseriöse Wortmeldungen nützt: siehe meine Signatur.