NP πρόβλημα

[Mathletic]

Μακρύτερο μονοπάτι

Έχουμε έναν γράφο , μήκη για κάθε , έναν θετικό ακέραιο και δύο κόμβους .

Τίθεται το ερώτημα αν υπάρχει απλό μονοπάτι στον από το στο μήκους τουλάχιστον .


Πώς μπορούμε να δείξουμε ότι το πρόβλημα Μακρύτερο μονοπάτι ανήκει στο NP;

Επίσης, πώς μπορούμε να δείξουμε ότι είναι NP-πλήρες, ανάγοντάς το Hamiltonian path σε αυτό;

[Mathletic]

Για να δείξω ότι το πρόβλημα είναι στο NP μπορώ να πω το εξής;

Μια μη-αιτιοκρατική μηχανή Turing πρώτα "μαντεύει" ποιοί δύο κόμβοι μπορούν να αποτελέσουν τον αρχικό και τελικό κόμβο αντίστοιχα του μακρύτερου μονοπατιού και στη συνέχεια επιβεβαιώνει ότι το μονοπάτι από το στο είναι απλό και ότι έχει μήκος τουλάχιστον σε βήματα.