Ιδιότητες συναρτήσεων μέτρησης πλήθους λύσεων σε προβλήματα με εύκολη απόφαση ύπαρξης λύσης: πληρότητα, προσεγγισιμότητα, μαρκοβιανές αλυσίδες, αλλαγές φάσης

Θεωρούμε συναρτήσεις που μετράν το πλήθος των λύσεων σε προβλήματα απόφασης στην NP.Το πλήθος των λύσεων από NP-πλήρη προβλήματα είναι δύσκολο να μετρηθούν, αλλά υπάρχουν δύσκολα προβλήματα καταμέτρησης με τo αντίστοιχο πρόβλημα απόφασης στο P. Η TotP είναι μια υποκλάση της #P που περιέχει όλα τα αυτοαναγώγιμα προβλήματα μέτρησης με εύκολη απόφαση ύπαρξης λύσης.
Πρώτον θα παρουσιάσουμε τα πρώτα αποτελέσματα πληρότητας για την TotP, ως προς φειδωλές αναγωγές, που είναι το αυστηρότερο είδος αναγωγών.
Δεύτερον παρουσιάζουμε αποτελέσματα προσεγγισιμότητας για την TotP: Δείχνουμε πώς προσεγγίζονται τα προβλήματα σε στιγμιότυπα με πολύ μεγάλο ή με πολύ μικρό πλήθος λύσεων. Βρίσκουμε μια οικογένεια στιγμιοτύπων που αποδεικνύουμε ότι περιλαμβάνει μη προσεγγίσιμα σε πολυωνυμικό χρόνο στιγμιότυπα (εκτός αν NP=RP). Δείχνουμε ότι κάθε πρόβλημα στην TotP επιδέχεται προσέγγιση σε καλύτερο εκθετικό χρόνο από τα προβλήματα στην #P. Μελετούμε τη σχέση της TotP και της FPRAS σε σχέση με το P vs RP και RP vs NP, δείχνοντας αφενός ότι η TotP είναι υποσύνολο της FPRAS αν και μόνο αν NP=RP, αφετέρου η FPRAS δεν είναι υποσύνολο της TotP εκτός αν RP=P.
Tρίτον σχεδιάζουμε και  μελετούμε μαρκοβιανές αλυσίδες των οποίων ο χώρος καταστάσεων είναι οι λύσεις προβλημάτων στην TotP. Παρατηρούμε ότι τα αποτελέσματα γενικεύονται από ένα ενιαίο μοντέλο βεβαρημένης μέτρησης, που περιλαμβάνει μια παράμετρο λ, και ότι για διαφορετικές τιμές του λ έχουμε τελείως διαφορετικές συμπεριφορές. Για κάποιο λ έχουμε αργό χρόνο σύγκλισης της αντίστοιχης αλυσίδας και δύσκολη προσέγγιση του αντίστοιχου προβλήματος βεβαρημένης μέτρησης. Για κάποιο άλλο λ έχουμε γρήγορη σύγκλιση και γρήγορη προσέγγιση του προβλήματος βεβαρημένης μέτρησης.
Τέλος θεωρούμε αλγόριθμο που χρησιμοποιείται στη στατιστική φυσική για την προσομοίωση φυσικών συστημάτων και την ανακάλυψη αλλαγών φάσεων στη φύση, και τον εφαρμόζουμε σε βεβαρημένες εκδοχές από TotP-πλήρη προβλήματα, και συγκεκριμένα για να προσεγγίσουμε το προαναφερθέν πρόβλημα βεβαρημένης μέτρησης. Ανακαλύπτουμε και αποδεικνύουμε φαινόμενα αλλαγής φάσης: Σε κάποιο λ_c1 έχουμε αλλαγή φάσης από εκθετικό χρόνο εκτέλεσης σε πολυωνυμικό χρόνο εκτέλεσης του αλγορίθμου. Σε κάποιο λ_c2 έχουμε αλλαγή φάσης από ΝP-hard to approximate σε εύκολα προσεγγίσιμο του αντίστοιχου προβλήματος βεβαρημένης μέτρησης. Τέλος δείχνουμε ότι αυτά τα δύο λ ταυτίζονται, πράγμα που είναι εντυπωσιακό διότι σημαίνει ότι αυτός ο αλγόριθμος της φύσης είναι αντιπροσωπευτικός της πολυπλοκότητας  του συγκεκριμένου προβλήματος βεβαρημένης μέτρησης, όπως και όλων των αντίστοιχων που μπορούν να οριστούν για κάθε συνάρτηση στην TotP.