Determining the achromatic number is NP-hard; determining if it is greater than a given number is NP-complete, as shown by Yannakakis and Gavril in 1978 by transformation from the minimum maximal matching problem.
Az akromatikus szám meghatározása NP-nehéz; annak meghatározása, hogy adott számnál nagyobb-e, NP-teljes, ahogy azt Yannakakis és Gavril 1978-ban megmutatták a minimális értékű maximális párosítás problémájából való transzformációval.