srcmini

2020-03-04半瓶木阅读(2161)评论(0)赞(0)

根据给定的基于决策的NP问题, 你可以设计电路并在P时间内验证给定的输出。电路如下：- 注意：-你可以设计电路并在多项式时间内验证上述输出, 但请记住, 你永远无法在多项式时间内根据输入/高输入组预测产生高输出的门数。因此, 你验证了生成和...

2020-03-04半瓶木阅读(1519)评论(0)赞(0)

本文概述 简化和分解 NP完全问题的例子 判定问题L为NP-Hard 对于所有L’NP, L’≤pL。 定义：如果L是NP完全的, 则 LϵNP和 对于某些已知的NP完全问题L, L’≤pL。给定这个正式...

2020-03-04半瓶木阅读(973)评论(0)赞(0)

NP类问题的定义问题：-所有基于决策的问题的集合进入了NP问题的划分中, 这些问题无法在多项式时间内解决或产生输出, 但需要在多项式时间内进行验证。 NP类包含P类作为子集。 NP问题难以解决。 注意：-术语“ NP”并不表示“非多项式”。...

2020-03-04半瓶木阅读(957)评论(0)赞(0)

合并网络是可以将两个排序的输入序列合并为一个排序的输出序列的网络。我们使用BITONIC-SORTER [n]创建合并网络MERGER [n]。 合并网络基于以下假设： 给定两个排序的序列, 如果我们颠倒第二个序列的顺序, 然后连接两个序列...

2020-03-04半瓶木阅读(823)评论(0)赞(0)

比较网络由电线和比较器组成。比较器是具有两个输入x和y以及两个输出x’和y’的设备, 其中 x’=最小值（x, y）y’=最大值（x, y） 在“比较网络”中, 输入出现在左侧, 输出出现在右...

2020-03-04半瓶木阅读(1016)评论(0)赞(0)

二分图是其顶点可以分为两个独立的集合L和R的图, 这样每个边（u, v）要么连接从L到R的顶点, 要么连接从R到L的顶点。换句话说, 对于每个边（u, v）u∈L和v∈L。我们也可以说不存在连接相同集合的顶点的边。 匹配是一个二部图, 它是...