是什么让一个问题比另一个问题更根本？
对于什么使一个问题比另一个问题更根本，是否有任何正式的定义？否则，可接受的非正式定义是什么？
一个比其他问题更基本的问题的例子是排序与字体渲染。
Is there any formal definition for what makes a problem more fundamental than another? Otherwise, what would be an acceptable informal definition?
An example of a problem that is more fundamental than another would be sorting vs font rendering.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
例如，当许多问题可以使用一种算法解决时。任何最佳排序算法都是这种情况。顺便说一句，也许你正在混合问题和算法？一个问题可以简化为另一个问题有一个正式的定义。请参阅http://en.wikipedia.org/wiki/Reduction_(complexity)
When many problems can be solved using one algorithm, for instance. This is the case for any optimal algorithm for sorting. BTW, perhaps you're mixing problems and algorithms? There is a formal definition of one problem being reducible to another. See http://en.wikipedia.org/wiki/Reduction_(complexity)
最初的问题是一个有效的问题，并且不必像 @slebetman 建议的那样假设/考虑复杂性和可简化性。 （从而使问题变得更加基本：）
如果我们尝试一个正式的定义，我们可以有这样的定义：如果 P1 的解决方案影响更广泛的其他问题的结果，那么问题 P1 比问题 P2 更基本。 /强>。这可能意味着 P1 将影响计算机科学不同领域的问题，甚至可能影响其他领域的问题。
实际上，我会再次纠正@slebetman。我不会说“如果某件事使用或挑战一个假设，那么它就没有该假设那么重要”，我会说“如果一个问题使用或挑战一个假设，那么它就没有没有假设的同一问题那么重要”。即对象的排序比整数的排序更基本；或者，打印机上的字体渲染不如任何设备上的字体渲染那么重要。
The original question is a valid one, and does not have to assume/consider complexity and reducibility as @slebetman suggested. (Thus making the question more fundamental :)
If we attempt a formal definition, we could have this one: Problem P1 is more fundamental than problem P2, if a solution to P1 affects the outcome of a wider set of other problems. This likely implies that P1 will affect problems in different domains of computer science - and possibly beyond.
In practical terms, I would correct again @slebetman. Instead of "if something uses or challenges an assumption then it is less fundamental than that assumption", I would say "if a problem uses or challenges an assumption then it is less fundamental than the same problem without the assumption". I.e. sorting of Objects is more fundamental than sorting of Integers; or, font rendering on a printer is less fundamental than font rendering on any device.
如果我理解你的问题的话。
当你可以通过应用多种算法来解决同一问题时，在内存和CPU上都证明其轻量级的算法被认为是更基础的。我能想到的另一件事是，一个基本的算法不会使用其他算法，否则它将是一个复杂的算法。
If I understood your question right.
When you can solve the same problem by applying many algorithms, the algorithm which proves its lightweight on both of memory and CPU is considered more fundamental. And I can think of another thing which is, a fundamental algorithm will not use other algorithms, otherwise it would be a complex one.
有更多应用的问题或解决方案更基础。
（排序有很多应用，P!=NP 也有很多应用（或含义），渲染只有很少的应用。）
The problem or solution that has more applications is more fundamental.
(Sorting has many appications, P!=NP too has many applications (or implications), rendeering only has a few applications.)
Inf 是对的，他暗示了复杂性和可简化性，而不仅仅是算法实现中涉及/包含的内容。这是你做出的假设。
所有代码都是基于对其运行环境的假设而编写的。这些假设比用这些假设编写的代码更为基本。简而言之，我想说：如果某件事使用或挑战某个假设，那么它的基础性就不如该假设。
举个例子：排序。排序的问题在于，如果以简单的方式进行排序，则排序所需的时间会增长得非常快。用技术术语来说，排序问题趋向于 NP 完全问题。因此，排序算法的开发就是为了避免 NP 完全问题。但是 NP 完备总是很慢吗？这本身就是一个问题，这个问题被称为 P!=NP，到目前为止还没有被证明是真是假。所以 P!=NP 比排序更基础。
但即使 P!=NP 也做出了一些假设。它假设 NP 完全问题总是可以运行完成，即使需要很长时间才能完成。换句话说，NP 完全问题的大 O 表示法永远不是无限的。这就引出了一个问题：所有问题都保证有一个完成点吗？答案是否定的，并非所有问题都有一个保证完成的点，其中最微不足道的是无限循环：
while (1) {print "still running!"}。那么我们能检测出程序无限运行的所有情况吗？不，证明就是停止问题。因此，停止问题比 P!=NP 更根本。但即使是停止问题也会做出假设。我们假设所有程序都在特定类型的 CPU 上运行。我们可以将所有 CPU 视为等效吗？有没有一种 CPU 可以解决停机问题？嗯，答案是只要CPU是图灵完备的，它们就和其他图灵完备的CPU是等价的。因此，图灵完备性是比停机问题更根本的问题。
我们可以不断地质疑我们的假设，例如：所有类型的信号都是等价的吗？流体计算机或机械计算机是否有可能与电子计算机有根本不同？它将引导我们了解香农信息论和布尔代数等，我们发现的每一个假设都比上面的假设更基本。
Inf is right when he hinted at complexity and reducibility but not just of what is involved/included in an algorithm's implementation. It's the assumptions you make.
All pieces of code are written with assumptions about the world in which it operates. Those assumptions are more fundamental than the code written with those assumptions. In short, I would say: if something uses or challenges an assumption then it is less fundamental than that assumption.
Lets take an example: sorting. The problem of sorting is that when done the naive way the time it takes to sort grows very quickly. In technical terms, the problem of sorting tends towards being NP complete. So sorting algorithms are developed with the aim of avoiding being NP complete. But is NP complete always slow? That's a problem unto itself and the problem is called P!=NP which so far has not been proven either true or false. So P!=NP is more fundamental than sorting.
But even P!=NP makes some assumptions. It assumes that NP complete problems can always be run to completion even if it takes a long time to complete. In other words, the big-O notation for an NP complete problem is never infinite. This begs the question are all problems guaranteed to have a point of completion? The answer to that is no, not all problems have a guaranteed point of completion, the most trivial of which is the infinite loop:
while (1) {print "still running!"}. So can we detect all cases of programs running infinitely? No, and the proof of that is the halting problem. Hence the halting problem is more fundamental than P!=NP.But even the halting problem makes assumptions. We assume that we are running all our programs on a particular kind of CPU. Can we treat all CPUs as equivalent? Is there a CPU out there that can be built to solve the halting problem? Well, the answer is as long as a CPU is Turing complete, they are equivalent with other CPUs that are Turing complete. Turing completeness is therefore a more fundamental problem than the halting problem.
We can go on and on and question our assumptions like: are all kinds of signals equivalent? Is it possible that a fluidic or mechanical computer be fundamentally different than an electronic computer? And it will lead us to things like Shannon's information theory and Boolean algebra etc and each assumption that we uncover are more fundamental than the one above it.