This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. We continue the Complexity Theory section with NP...
这是一系列博客文章中的最新一篇，旨在解决“每个博士生都应该知道的 52 件事”来做密码学：一组问题汇编，让博士生在第一年结束时了解他们应该知道什么。我们继续使用 NP 的复杂性理论部分......
Last week, Ryan introduced us to complexity classes, and in particular to P:
上周，Ryan 向我们介绍了复杂度类，尤其是 P：
- P is the class of languages decidable in polynomial time by a deterministic Turing machine.
P 是确定性图灵机在多项式时间内可判定的语言类。
本周，我们将介绍另一个复杂性类：
- NP is the class of languages decidable in polynomial time by a nondeterministic Turing machine.
NP 是一类可由非确定性图灵机在多项式时间内判定的语言。
What is a Nondeterministic Turing Machine (NDTM)?
什么是非确定性图灵机（NDTM）？ Well, an NDTM is a Turing Machine for which the transition function can have multiple values for the same tape value/state pair (meaning it is not technically a function any more, so the correct thing would be to call it a transition relation). Thus evaluation of an NDTM on any particular input can be thought of as a tree, branching at each point the transition function provides more than one possible value. Now, an NDTM evaluates all of these possible branches at once, and accepts if at least one of these computations halts in the accept state. This definition generalizes from language membership to decision to computational problems in the same way as P did in last weeks blog.好吧，NDTM 是一个图灵机，它的转换函数可以有多个值用于同一个磁带值/状态对（这意味着它在技术上不再是一个函数，所以正确的做法是称它为转换关系）。因此，对任何特定输入的NDTM的评估可以被认为是一棵树，在转移函数的每个点上分支，提供多个可能的值。现在，NDTM 会同时评估所有这些可能的分支，如果这些计算中至少有一个停止在接受状态，则接受。这个定义从语言隶属关系到决策再到计算问题，就像 P 在上周的博客中所做的那样。
Some Examples of NP problems
NP问题的一些例子 We begin with an easy example: path finding. Given a directed graph (on n vertices) is there a path from vertex A to vertex B. How do we know this is in NP? Well, there is an NDTM that solves it, which basically works by simply trying every route by branching each time there is a junction. If one of these branches (ie one of the trial routes) reaches B, then that branch terminates in the accept state. Any branch that does not reach B within n steps (ie after traversing n edges) terminates in the reject state. Since any path will involve at most n-1 edges, any valid route will be detected, and so this machine correctly decides whether the path exists.我们从一个简单的例子开始：路径查找。给定一个有向图（在 n 个顶点上），是否有一条从顶点 A 到顶点 B 的路径。我们怎么知道这是在NP中？好吧，有一个 NDTM 可以解决这个问题，它基本上只需在每次有交汇点时通过分支来尝试每条路线即可。如果其中一个分支（即试验路由之一）到达 B，则该分支将终止为接受状态。任何在 n 步内（即遍历 n 条边后）未到达 B 的分支都将在拒绝状态下终止。由于任何路径最多涉及 n-1 条边，因此将检测到任何有效路径，因此此计算机可以正确确定路径是否存在。
One of the key examples of an NP problem is the satisfiability problem:
NP 问题的一个关键示例是满足性问题：
- SAT: Given an expression in n boolean variables, is there an assignment of the variables such that the expression evaluates to True?
SAT：给定 n 个布尔变量中的表达式，是否存在变量赋值，使表达式的计算结果为 True？
例如，表达式 <span id="MathJax-Span-2" class="mrow"><span id="MathJax-Span-3" class="mo">(<span id="MathJax-Span-4" class="mi">A<span id="MathJax-Span-5" class="mo">∧<span id="MathJax-Span-6" class="mi">B<span id="MathJax-Span-7" class="mo">)<span id="MathJax-Span-8" class="mo">∨<span id="MathJax-Span-9" class="mo">(<span id="MathJax-Span-10" class="mi">A<span id="MathJax-Span-11" class="mo">∧<span id="MathJax-Span-12" class="mi">¬<span id="MathJax-Span-13" class="mi">B<span id="MathJax-Span-14" class="mo">) 是令人满意的，其中一个有效赋值为 A=B=True。请注意，在标准形式中，SAT 是一个决策问题：决定是否存在这样的作业就足够了，我们不必找到它。
Ok, so there are problems in NP. What is interesting about it?
好的，NP有问题。它有什么有趣的地方？ Firstly, we see that P⊆NP since a DTM is an NDTM that just happens not to ever branch (in fact, our first example can actually be solved by a DTM and so is within P). So, the real question is what sort of things can we do in NP that we couldn't do in P? Well, this is the root of the P<span id="MathJax-Span-16" class="mrow"><span id="MathJax-Span-17" class="mover"><span id="MathJax-Span-18" class="mo">=<span id="MathJax-Span-19" class="mo">?NP millenium problem, which is a major open problem. There are certainly problems that we have found that are known to be in NP that we do not know to be in P, but perhaps future research will show that these are also in P.首先，我们看到 P⊆NP，因为 DTM 是一个 NDTM，它恰好永远不会分支（事实上，我们的第一个例子实际上可以通过 DTM 求解，因此在 P 中）。所以，真正的问题是，我们可以在NP中做哪些事情，而我们在P中做不到？嗯，这就是P <span id="MathJax-Span-16" class="mrow"><span id="MathJax-Span-17" class="mover"><span id="MathJax-Span-18" class="mo">=<span id="MathJax-Span-19" class="mo">? NP千年问题的根源，这是一个主要的开放性问题。当然，我们已经发现了一些已知存在于NP中的问题，而我们不知道这些问题存在于P中，但也许未来的研究表明这些问题也存在于P中。 Lots of interesting cryptographic systems (particularly in the public key setting) are secure based on the assumption that a computational problem is "hard", which generally means "at least as hard as any problem in NP". That is, many schemes are based on problems which we think are difficult to solve, and that if you can create an algorithm that solves them you could also use this algorithm to solve lots of other problems that we currently believe to be difficult.
许多有趣的加密系统（特别是在公钥设置中）是安全的，基于计算问题是“困难的”的假设，这通常意味着“至少与NP中的任何问题一样困难”。也就是说，许多方案都是基于我们认为难以解决的问题，如果你能创建一个算法来解决这些问题，你也可以用这个算法来解决我们目前认为困难的许多其他问题。
The Cook-Levin theorem provides an interesting result in this direction: No problem in NP is any harder than SAT. What his means is that if I had an oracle (basically an algorithm that I can see the input/output of but none of the workings) that solved SAT, by asking it to solve cleverly constructed queries I could use it to solve any other NP problem. This made SAT the first example of an NP-complete problem. So, to show that a problem X is at least as hard as solving an NP problem (it is NP-hard), it suffices to show that if I could solve X, I could use it to solve SAT.
库克-莱文定理在这个方向上提供了一个有趣的结果：NP中没有比SAT更难的问题了。他的意思是，如果我有一个预言机（基本上是一种算法，我可以看到它的输入/输出，但没有工作原理）来解决 SAT，通过要求它解决巧妙构造的查询，我可以用它来解决任何其他 NP 问题。这使得 SAT 成为 NP 完全问题的第一个例子。因此，为了证明问题 X 至少与解决 NP 问题一样难（它是 NP 难的），它足以表明如果我能解决 X，我就可以用它来解决 SAT。 标签：meant,What,gt,Span,Things,lt,MathJax,amp,class From： https://www.cnblogs.com/3cH0-Nu1L/p/18104666