多項式同構

多項式同構(polynomially isomorphic)集合關於多項式可計算的一種分類.設A,B為兩個集合，若存在一個一一對應的函式f，使f和少’都是多項式時間可計算的，並且f [A} -B，則稱A和B為多項式同構或P同構的，記A-PB.伯爾曼(Berman,L.)和哈特曼尼斯(Hartmanis, J.)證明了許多已知的NP完全集都是P等價的.因此，他們猜想所有NP完全集都是P同構的.這個猜想稱為伯爾曼一哈特曼尼斯猜想，簡稱BH猜想.但至今對此尚無證明或否證.注意到BH猜想可以推出P}NP.因此，實際上SH猜想的解決，其難度不比P_NP問題解決的難度低.