苏联计算理论背景中的研究者
列昂尼德·列文（Leonid Levin）是研究计算复杂性、密码理论和算法信息论的计算机科学家，早年在苏联开展研究，师从莫斯科大学的安德烈·柯尔莫哥洛夫，后来成为波士顿大学教授。2012年，他获得克努特奖，获奖工作包括对NP完全性的独立研究。
他的早期问题来自苏联关于穷举搜索的讨论：某些任务虽然有明确算法，直接枚举所有可能性的成本却大得无法实际执行。列文关心的不仅是能否计算，还包括不同搜索任务之间是否有共同的困难，以及一个通用方法能在多大程度上模拟专门方法。
把寻找答案与判断存在分开
1973年的《Universal Sequential Search Problems》把搜索任务写成这样的形式：给定输入，寻找长度受多项式约束的答案，而答案是否满足条件可以高效检验。论文还单独讨论只判断这样的答案是否存在的对应问题。因此，“找出一个证据”和“回答有没有证据”在表述上并不是同一件事。
文中考察覆盖、布尔表达式和带相邻限制的方格填充等问题，并以归约比较它们。若任意一类受考察的搜索任务都能高效转换为某个任务，该任务就具有通用性。其意义是把许多表面不同的困难连接起来：找到一个通用问题的高效解法，便会影响整类问题，而不是只解决一个孤立例子。
这种结论并未证明P不等于NP，也没有证明每个实例都必须穷举。原论文明确把真正的时间下界问题保留下来。
参考：[2]
通用搜索的最优性意味着什么
列文还提出，在相应模型中，可以构造一个搜索算法，其运行时间相对于任意给定的有效求解方法，只增加常数倍及适当的输入处理开销。这是一种理论上的比较结果，不是说实际计算机已经拥有能够轻易解决所有难题的软件。
如果被比较的方法本来就需要很长时间，常数倍最优的方法仍然可能很慢；比较中的常数也不一定适合工程实践。列文后来回忆，柯尔莫哥洛夫对通用搜索算法本身兴趣较少，却重视把其他问题归约到填充问题的通用性。这段回忆解释了两条研究线索如何在同一篇短文中相遇。
独立发现与平均情形
列文的自述称，他于1972年提交相关工作；原论文随后于1973年发表。美国的斯蒂芬·库克在不同学术环境中独立得到相关完全性结果，理查德·卡普又扩展了许多重要归约。后来“库克—列文”这一并称不表示两人曾合写论文，俄文原始表述与后续英文传播也应与研究发生的时间区分。
列文继续追问最坏情形与平均情形的差异。某类问题包含困难实例，并不保证随机选出的实例也难，更不能直接保证以它为基础的密码系统安全。其平均情形复杂性研究把实例分布纳入分析，使“困难”不再只是一种脱离输入来源的标签。