仅仅是10个城市，就有这么多的路线。但由于阶乘数增长得如此之快，还没增加几个城市，计算机也不堪重负了。例如，
数学家把以这种方式增长的数学模式称为呈指数增长。阶乘数以指数增长。
近似解列出所有的可能性并对它们进行比较，以找出最短的路线，这是解决这个问题的一个非常天真的方法。还有一个更好的方法吗？因为推销员问题在工业和商业上十分重要，所以数学家使出浑身解数试图找到其他的方法。他们的方法可归为两类，这两类都涉及高深的数学。
一种方法是寻求近似解。我们不是去寻找一条总路程最小的路线，而是去寻找一条与最佳路线的长度偏差落在（比方说）5%以内的路线。
另一种方法是寻求一个准确的答案，但要全面观察这些城市的地理情况，并设法利用这些城市的布局特点，以减少可能路线的数目。但这种方法有个明显的缺点，就是你得到的答案只适用于一组特定的情况。增加或减少一个城市，就得重头再来。
1998年，一个数学家团队找到了巡访美国所有人口在500以上的13509个城市的最短路线。他们用由32台奔腾PC机支持的三台高性能多处理器科学计算机联成一个网络，并在这个网络上进行了三个半月的运算。
然而，如果不考虑近似解，不考虑对一些特定的城市组合求解，那么就没有人知道推销员问题的实用解答。
理论工作者登场了推销员问题是20世纪30年代由维也纳数学家门格首次提出的。此后不久，数学家在工业和管理中发现了同样重要的其他问题，而且同样也不能解决。
例如，有一个过程调度问题。在这个问题中，你面对着许多工作，它们都必须完成，比方说在工厂中就会遇到这样的情况。这些工作中有一些要在另一些工作完成之后才能做，而有一些则是能独立完成的。你能不能把这些工作分成组，使得完成所有这些工作时间最少。每一组中的工作将被视作一个过程，即完成其中的一个工作后才能做其中的下一个工作，但各个过程可以同时进行。
与推销员问题一样，一旦你将这些工作分了组，使得每组工作可以与所有其他组同时进行，那么计算总时间所用的数学便是小菜一碟。你所要做的只是在每组中将完成各项工作的时间加起来，然后在这些时间中找出一个最长的。这个最长的时间就是用这种特定的分组法来完成所有工作所需的时间。问题是为了求出所需时间最少的调度安排，你必须对所有可能的分组都进行这样的计算，而就像推销员问题中可能路线的数目一样，这个可能分组方式的数目随着工序的增长而以指数增长。
当纯粹数学家开始思考这个问题时，他们会问一个非常与众不同的问题。他们说，假设推销员问题根本不存在有效的解法（不考虑近似方法）。那么这个问题就变成，你能证明吗？如果能，那么你至少知道花费大量的时间和计算资源来试图解决它是没有意义的。
要令人信服地证明试图解决这个问题是浪费时间和精力，你必须给出一个扎实可靠的证明，证明不存在明显好于蛮力法（即对所有的可能性进行试验）的方法可以解决这个问题。
解决一个问题需要多少个步骤理论工作者首先面对的一个问题是，找出一种方法来度量在一台计算机上执行一项特定任务需要多长时间。以推销员问题为例，答案（至少）依赖两样东西∶所使用的计算机和城市的数量。从理论上讲，计算机不是一个重要的因素，关键在于城市的数量。
很明显，一个问题所涉及的数据越多，花费在计算上的时间也越长。但是长出多少呢？准确地说，如果数据总量增加了一个确定的数量，计算时间会增加多少呢？例如，如果我们将数据总量翻一番，计算时间是不是也会翻一番？
既然我们关心的是计算时间的相应增长，那么不管是两倍、三倍还是更多，实际上的计算时间是多少是无关紧要的。在这种情况下，我们需要做的只是弄清楚这个计算所涉及的基本步骤有多少。这就把问题从度量时间转化为对基本步骤计数了。
什么是一个基本步骤？以算术为例，一个基本步骤就是将两个单独的数相加或相乘。算上进位，把两个N位数相加至多涉及3N个基本步骤。例如，将两个4位数相加需要3×4=12个基本步骤。
