Jest to związane z pytaniem Czy rozmiar członkostwa świadka dla każdego języka NP jest już znany? Niektóre naturalne problemy (-kompletne) mają świadków o długości liniowej: zadowalające przypisanie dla , ciąg wierzchołków dla itp.NPNP\mathsf{NP}SATSATSATHAMPATHHAMPATHHAMPATH Rozważ klasę...