目前为止，所有已知解NPC问题的算法需要依照资料数量而定的超多项式（superpolynomial）时间，目前也不知道是否有任何更快的算法存在。因此要在输入资料量大的时候解决一个NPC问题，通常我们使用下列的手段来解：
近似算法：这类算法可以快速发现离最佳解在一定差距内的次佳解。
乱数算法：此类算法可提供一乱数产生的输入资料，让本质上解答分布均匀的受测程式可以有良好的求解效率。对于解答分布不均匀的程式，则可以降低乱数程度以改变输入资料。
特例：此算法可以在题目呈献某些特殊情况时快速得解。参数化复杂度（Parameterized complexity）可视为广义的此类算法。
启发式算法：这种算法在许多时候可以产生理性解答（即运用评比或线索找出解），但无法保证它效率的良莠与解答的好坏程度。
一个启发式算法的例子是用在图着色问题以O（n log n）的贪婪算法找次佳解，用在某些编译器的暂存器配置阶段上，此技术又叫图着色全域暂存器配置（graph-coloring global register allocation）。每顶点视为一变量，每边代表两变量同时使用的情况，颜色则代表配置给每一变量的暂存器编号。由于大多数的RISC机器拥有大量通用暂存器，因此启发式算法很适合用来解这类题目。 依照上述NPC的定义，所谓的变换其实是多项式时间多对一变换的简称。
另一种化约法称为多项式时间图灵归约（polynomial-time Turing reduction）。若我们提供一个副函式（subroutine）可以在多项式时间解出Y，又可写出呼叫此副函式的程式并在多项式时间解出问题X，代表我们可以将X多项式时间图灵变换成Y。相较起来，不同处在于多对一变换只能呼叫上述副函式一次，且副函式的回传值必须就是整个变换程式回传的值。
如果有人使用图灵变换而非多对一变换来解析NPC，此问题的解答集合不一定会小于NPC。孰大孰小其实是个开放问题。如果两个概念相同，则可导出NP=反NP（co-NP）。此结论成立的道理在于NPC与反NPC的定义以图灵归约来看是相等的，且图灵变换定义的NPC包含多对一变换定义的NPC，反NPC也是相同情况。所以若是两种变换定义的NPC一样大的话，反NPC也会比照办理（在两者的定义之下）。例如SAT的反问题也会是NPC（在两者的定义之下）。因此推得NP = 反NP（证明在反NP条目中）。虽然NP是否等于反NP是个开放问题，但一般认为这似乎不大可能，也因此那两类的NPC定义也不大可能相等。
另一种很常用于NPC证明的变换手法是对数空间多对一变换（logarithmic-space many-one reduction），它是一种可以在对数量级空间运用的多对一变换法。由于每道可以在对数空间完成的运算也可以在多项式时间做完，因此能使用对数空间多对一变换的场合也可以使用多项式时间多对一变换。本方法较多项式时间多对一变换优雅，它也可以让我们对算法复杂度细分出更多分类，例如P完备复杂度。而NPC的定义是否会因为使用不同变换手法而产生差异，仍是一个未知的问题。
