Dieses Problem ergab sich aus meinem letzten Blogeintrag . Angenommen, Sie erhalten eine TSP-Tour. Ist es co-NP-vollständig, um festzustellen, ob es sich um ein Minimum handelt? Genauer ist das folgende Problem NP-vollständig: Instanz: Gegeben ist ein vollständiger Graph G mit Kanten, die mit...