Thoir sùil air an earrann gu h-ìosal agus an uairsin freagair a 'cheist às deidh sin anns an aon chànan ris an earrann: Earrann: Chaidh a shealltainn le Ladner ma tha P ≠ NP an uairsin tha duilgheadasan ann an NP nach eil ann an P no NP-iomlan. Canar duilgheadasan mar sin NP-meadhanach. Is e an duilgheadas isomorphism grafa, an duilgheadas logarithm neo-eisimeileach agus an duilgheadas factarachaidh àireamhan iomlan eisimpleirean de dhuilgheadasan a thathas a 'creidsinn gu bheil iad NP-meadhanach. Tha iad nan cuid de na glè bheag de dhuilgheadasan NP nach eil aithnichte a bhith ann am P no a bhith NP-iomlan. Ceist: Dè an t-ainm a th' air na duilgheadasan sin?
Duilgheadasan eadar-mheadhanach NP