In computational complexity, an NP-complete problem is weakly NP-complete if there is an algorithm for the problem whose running time is polynomial in the dimension of the problem and the magnitudes of the data involved, rather than the base-two logarithms of their magnitudes. Wikipedia