关于NP问题的一个证明

若A可约化为B，求证：
（1）若B为P问题，则A为P问题
（2）若B为NP问题，则A为NP问题

写回答
好问题 0 提建议
追加酬金
关注问题
分享
邀请回答
编辑收藏删除结题
收藏举报

1条回答默认最新

关注

码龄粉丝数原力等级 --

被采纳

被点赞

采纳率
白萝卜。 2017-06-06 09:37
关注
计算机图论老师教过我们证明题就分两种：第一种：这也需要证？第二种：这也能证。你这属于前者。

解决无用
评论打赏
分享
举报

评论

按下Enter换行，Ctrl+Enter发表内容

报告相同问题？

关注问题

关于pytorch的一个小问题。 python 机器学习深度学习
2022-08-02 09:19

回答 3 已采纳你参数名称写错了，有用记得采纳 camp=plt.cm.gray 改成： cmap =plt.cm.gray
A=np.array输出问题 python
2022-07-13 00:07

回答 2 已采纳你生成了一个二维数值Aarray([[10, 11, 12], [13, 14, 15], [16, 17, 18]]) A[[2,1]]：取了A中的第三行和第三行array(
大数分解问题是NP问题吗？ python 数据结构
2023-04-01 12:15

回答 2 已采纳你说的是大数因式分解？大质数的判定是NP Hard问题。这个是现代密钥算法体系的基石。
P问题与NP问题的关系
2021-01-07 02:47

当一个问题是P问题时，我们可以在多项式时间内求出问题的解。若要验证一个解（记为t1）是否正确时，只需使用多项式时间求解出这个问题的解（记为t2），然后将t1和t2做比较即可验证答案是否正确。即，可以利用多项式...
关于python的2个小问题 python
2021-07-18 15:05

回答 1 已采纳 dd=ts.get_k_data('002466',start='2010-01-01',end='2021-07-18')['close']dd.sort_index(inplace=True)可以
为什么说旅行商问题是NP Hard的？
2015-01-02 12:04

回答 8 已采纳怎样证明一个问题C是NP完全问题呢？首先，要证明C是NP问题，也就是C的解的正确性容易验证；然后要证明有一个NP完全问题B，能够在多项式时间内归约到C。这就要求必须先存在至少一个NPC问题。Cook证
opencv中np的有关数组的问题 opencv python
2021-08-26 14:42

回答 1 已采纳构建一个 5125123的数组，每个值都是0相当于生成了一张黑色的 512*512大小的图片。
NP问题的证明
2017-12-28 17:42

crystal_zyp的博客 8.3证明NP完全问题（1) Problem： STINGY SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer k, find a satisfying assignment in which at most k ...
如何让一个np数组中随机几个数字+1 python 机器学习
2021-05-02 02:33

回答 2 已采纳 >>> import numpy as np >>> x = np.array([1,2,3,4,5,6]) >>> r = np.random
如果证明了大数分解问题存在多项式时间的算法，是否相当于证明了P=NP？ python
2023-04-01 07:26

回答 2 已采纳这个证明不了，别费心思了。
np.mat()生成的矩阵问题 python
2023-02-21 22:16

回答 1 已采纳该回答引用ChatGPT 在 Python 中，如果你想进行对应位置相乘，可以使用 Numpy 提供的 multiply 函数。例如： import numpy as np a = np.arr
如何证明一个问题是NP-hard（NP-complete）
2022-04-18 15:41

今天也要加油鸭！！！！！的博客 →使用一个叫做Reduction的技巧，即，如果能用A问题的求解器去求解另一个已知的NP-hard问题，则A问题是NP-hard的 Reduction是将两个算法建立联系的一个过程。我们说X reduce 到Y，意味着，假设现在有一个Y的黑盒求解...
python中np.genfromtxt的使用小问题 python
2021-09-13 10:26

回答 2 已采纳 delimiter 参数一旦文件被定义并打开阅读，genfromtxt将每个非空行拆分为一个字符串序列。刚刚跳过空行或注释行。delimiter关键字用于定义拆分应如何进行。通常，单个字符标记列之
NP-hard类问题证明
2021-03-15 21:35

Devour123的博客 NP-hard类问题：所有的非确定性多项式时间可解的判定问题构成NP类问题。证明1：问题A给定限制条件得到一个特例B问题 ...NP 问题的另一个定义是可以在多项式的时间里猜到一个解的问题；很显然，所有的 P 类问题都
证明一个问题是NP-Hard问题
2019-11-19 20:18

weixin_40736549的博客证明一个问题是NP-Hard问题证明问题A是NP-Hard问题可以分为两步： 1）对问题A给定一个限制条件，得到问题B； 2）证明问题B是NPC问题。
NP完全问题证明
2012-01-05 02:38

NP完全问题证明 CNF-SAT 3-SAT CLIQUE VERTEX-COVER 均分
np完全问题证明思路
2013-11-04 21:03

详细介绍了npc问题的证明思路，并拿顶点覆盖问题做了例子
没有解决我的问题, 去提问

悬赏问题

¥15 素材场景中光线烘焙后灯光失效
¥15 请教一下各位，为什么我这个没有实现模拟点击
¥15 执行 virtuoso 命令后，界面没有，cadence 启动不起来
¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
¥20 有关区间dp的问题求解
¥15 多电路系统共用电源的串扰问题
¥15 slam rangenet++配置
¥15 有没有研究水声通信方面的帮我改俩matlab代码
¥15 ubuntu子系统密码忘记
¥15 保护模式-系统加载-段寄存器

关于NP问题的一个证明

1条回答 默认 最新

悬赏问题

1条回答默认最新