精华内容
下载资源
问答
  • NP问题的证明

    千次阅读 2017-12-28 17:42:32
    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 ...

    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 variables are true, if such an assignment exists. Prove that STINGY SAT is NP-complete.
    (2) Solution:
    类似于SAT问题,显然对于给定的一组变量赋值,我们可以在多项式时间内证明是否为STINGY SAT问题的解,所以STINGY SAT问题是NP问题;
    SAT问题是给定一个CNF,给出一组变量值使得所有字句为真,或者证明不存在满足的解。令k = n时,可以将SAT问题归约成STINGY SAT问题,由于SAT问题是NP完全问题,所以STINGY SAT问题也是NP完全问题。

    8.10证明NP完全问题
    (a)子图同构:令G是一个环,且环上的顶点数等于H上的顶点数。如果G是H的同构子图,则H中存在Rudrata回路,Rudrata回路问题是子图同构问题的一个特例,所以子图同构问题也是一个NP完全问题;
    (b)最长路径:假设G=(V, E),g=|V|-1,则G中存在Rudrata路径,Rudrata路径问题是最长路径问题的一个特例,所以最长路径问题也是一个NP完全问题;
    (c)最大SAT:与8.3的问题相似,令g等于CNF中字句的个数时,则SAT问题可归约成最大SAT问题,所以最大SAT问题也是一个NP完全问题;
    (d)稠密子图:令b=a(a-1)/2,则此时图G中的a个顶点两两相连,最大团问题是此问题的一个特例,所以稠密子图问题是一个NP完全问题;
    (e)稀疏子图:令b=0,则此时图G中的a个顶点两两互不相连,最大独立集是此问题的一个特例,所以稀疏子图问题是一个NP完全问题;
    (f)集覆盖:集合覆盖是指从B={b1, b2, b3, …, bn}中找出一组集合使得其并集等于集合A,而顶点覆盖是指从V中找出一组顶点V’使得G中的每条边至少有1个顶点在V’中,最小顶点覆盖可以看成是集合覆盖的一个特例,所以集合覆盖也是一个NP完全问题;
    (g)可靠网络:TSP问题是此问题的一个特例,所以可靠网络问题是一个NP完全问题。

    8.14证明NP完全问题
    (1)Problem:
    Prove that the following problem is NP-complete: given an undirected graph G = (V, E) and an integer k, return a clique of size k as weill as an independent set of size k, provided both exist.
    (2)Solution:
    独立集问题和团集问题是等价的,假设要求图G中存在大小为k的团集,可以向原图G中增加k个互相独立的顶点,则这k个顶点构成了新图G大小为k的独立集,同时也不影响原图的团,团集问题可归约成此问题,因此该问题是NP完全问题。

    8.15证明NP完全问题
    (1)Problem:
    Show that the following problem is NP-complete.
    MAXIMUM COMMON SUBGRAPH
    Input: Two graphs G1=(V1,E1) and G2=(V2,E2);a budget b.
    Output: Two set of nodes V1’⊆V1 and V2’⊆V2 whose deletion leaves at least b nodes in each graph, and makes the two graphs identical.
    (2)Solution:
    假设G1=(V, E), G2=(V, Ø),当存在至少b个顶点的最大公共子图时,即存在至少b个顶点的独立集。
    a. 如果有图大小为b的最大公共子图,且这b个顶点不属于独立集,则至少有2个顶点有边相连,G1和G2的子图中这两个顶点就是相连的,而因为假设条件中G2是不存在边的,出现矛盾,因此这b个顶点属于独立集;
    b. 如果有b个顶点属于独立集,我们取这b个顶点构成G1和G2的子图,所以G1中这b个顶点之间不存在边,G2又是没有边的图,所以这两个子图就是相同的,也就是存在大小为b的公共子图。
    因此,独立集问题是这个问题的一个特例,这个问题就是NP完全问题。

    展开全文
  • NP类问题证明

    千次阅读 2018-10-13 11:06:08
    NP类问题:所有的非确定性多项式时间可解的判定问题构成NP类问题。 根据这个概念,要证明一个问题是NP类的,第一证明此问题是不确定的;第二证明此问题可多项式时间求解 这是我的理解,你可以参考一下  ...

    NP类问题:所有的非确定性多项式时间可解的判定问题构成NP类问题。

    根据这个概念,要证明一个问题是NP类的,第一证明此问题是不确定的;第二证明此问题可在多项式时间求解

    这是我的理解,你可以参考一下
     

    展开全文
  • 算法_NP_证明

    2019-09-27 13:30:46
    外,可以每个子句添加一些哑变量(辅助变量,没有实际用处),这样就可以将每个子句包含的 literal的数目增加到四个。因此,该3SAT实例可以转化为一个EXACT 4SAT问题。因此,可以证明该问 题是NP完全的。 ...

    8.3

    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 variables are true, if such an assignment

    exists. Prove that STINGY SAT is NP-complete.

    证明:

    由于可以在多项式时间内验证STINGY SAT的解,所以该问题属于NP问题。而将k设为所有变量的总数

    时,就可以将SAT规约到STINGY SAT,因此该问题为NP完全问题。

     


    8.8

    In the EXACT 4SAT problem, the input is a set of clauses, each of which is a disjunction of exactly

    four literals, and such that each variable occurs at most once in each clause. The goal is to find a

    satisfying assignment, if one exists. Prove that EXACT 4SAT is NP-complete.

    证明:

    由于可以在多项式时间内验证EXACT 4SAT的解,因此该问题属于NP问题。为证明其NP完全性,考虑

    通过将3SAT规约到EXACT 4SAT。对于任意一个3SAT实例,如果其中某个子句中包含同一个literal多次,

    那么可以把这个多次出现的literal缩减为一次;如果同时包含某个literal的肯定和否定,则可以去掉它。另

    外,可以在每个子句中添加一些哑变量(辅助变量,没有实际用处),这样就可以将每个子句中包含的

    literal的数目增加到四个。因此,该3SAT实例可以转化为一个EXACT 4SAT问题。因此,可以证明该问

    题是NP完全的。

     

    转载于:https://www.cnblogs.com/pxy7896/p/7117207.html

    展开全文
  • 2020年7月出版的《计算机科学》(中国计算机学会会刊)发表了国防科技大学教授、湘潭大学计算机学院特聘教授姜新文题为《哈密顿图判定问题的多项式时间算法...,这标志着数学和计算机科学领域最为重要的难题之一"NP=P...

    2020年7月出版的《计算机科学》(中国计算机学会会刊)发表了国防科技大学教授、湘潭大学计算机学院特聘教授姜新文题为《哈密顿图判定问题的多项式时间算法》的论文,这标志着在数学和计算机科学领域中最为重要的难题之一"NP=P?"得到科学证明,论文刊出几天后下载量近千次,引发有关学术群体热议。

    68370daef67c1e13899ba8726eb94421.png

    "NP=P?"也称"NP≠P还是NP=P",实质是P对NP关系问题,被称为世界级数学难题之一。

    2000年5月,美国克雷数学研究所(CMI)在巴黎举行的千年数学大会上宣布对攻克世界7个数学难题的悬赏。P对NP关系问题被列为新千年7大难题之首。2005年《科学》杂志将"NP=P?"问题作为数学科学的代表,列为25个学科难题之一。2018年《科学》杂志再次列出125个亟待解决的科学难题,其中第19个问题就包含"NP=P?"问题。

    迄今为止,新千年7大数学难题中除了俄罗斯数学家佩雷尔曼2002年证明了有关拓扑学的"庞加莱猜想"之外,其他难题均悬而未决。

    据介绍,20世纪,现代计算机问世,NP与P的关系问题就成为计算机科学和数学交叉领域的基础科学问题。通常,算法求解一个问题需要耗费时间,这被称为算法的时间复杂度。求解同一个问题的不同算法耗费的时间可能不同,只有采用多项式时间算法才能最有效解决问题。

    NP≠P,其核心是否定不同选择方法,认为有些问题不存在多项式算法。

    而姜新文证明了"NP=P",表明多项式算法实际上是存在的。

    姜新文从1986年开始讲授《算法设计与分析》课程,结合此前学习图论时关于哈密顿图判定问题的思考,开始研究P对NP关系问题。9年之后,姜新文于1995年发表了研究成果《简单无向图H性质判定》,开始思考运用整体观思路来处理一个有限系统的计算问题。

    他首先建立了一套基于数学归纳法的证明框架,然后坚持探索满足这套证明框架的算法设计。从1995年开始之后的15年中,经历了2000次以上设计、修改与调整,到2010年底得到预期效果。姜新文35年的潜心探索,终于获得成功!

    "NP=P"得到证明具有重要的科学意义与应用价值。因为这将为计算机科学领域带来截然不同的理论极限和发展前景。在现代经济社会中,大量科研、生产、国防与社会服务过程都需要采用正确的快速计算方法。可以期待,在"NP=P时代",地球科学、生命科学、宇宙科学、环境科学、生物科技、材料工程、管理科学、数学科学、物理科学等多个学科的研究都将得到更深入的推进。

    此外,由于现代密码学是建立在NP≠P的假定之上,而现在NP=P得到证明,对密码学的发展是一次巨大的科学挑战。

    相关论文信息:doi: 10.11896/jsjkx.191200176

    展开全文
  • NP完全问题习题证明

    千次阅读 2017-06-23 11:43:50
    NP-完全问题 一、概述 1.1 P问题 如果一个问题可以找到一个能多项式的时间里解决它的算法,那么这个问题就属于P问题,P(olynominal) ...NP 问题不是非 P 类问题,NP问题的另一个定义是,可以多项式的时间里猜出
  • NP 问题已有的知识的(黑箱) 零知识证明都是非常数轮的, 因此, 标准的复杂性假设下, NP 问题是否存在常数轮的(黑箱) 知识的零知识证明是一个有意义的问题. 本文对该问题进行了研究, 一定的假设下给出了HC 问题的...
  • P问题、NP问题、NPC问题的概念及实例证明

    万次阅读 多人点赞 2016-05-21 16:29:25
    三、如何对问题证明 四、NP-Complete间的规约例子 首先解释一下什么是NP问题,什么是NP hard问题,什么是NP完全问题。 * P Problem:这个应该最易理解,就是一个问题可以Polynominal的时间的得到解决,当然,是...
  • 课后习题8.10:利用推广的方法证明NP-完全性。对以下每个问题请通过证明它是本章某个NP-完全问题的推广说明它是NP-完全 的。 (a)子图同构:给定两个作为输入的无向图G和H,判断G是否为H的一个子图(即删除H的...
  • NP 是 Non-deterministic Polynomial 的缩写,NP 问题通俗来说是其解的正确性能够被很容易检查的问题,这里"很容易检查"指的是存在一个多项式检查算法。 例如,著名的推销员旅行问题(Travel Saleman Problem or ...
  • 第六个知识点:我们怎么把NP问题解释成一组可以多项式内证明的命题 原文地址:http://bristolcrypto.blogspot.com/2014/11/52-things-number-6-how-can-we-interpret.html 这是密码学52件事的第六篇,我们继续解释...
  • 交互式证明系统的诞生与发展 本文章从传统的数学证明系统入手...数学学习,我们证明一个推论或者断言T的主要形式如下: 证明目标:T 证明过程:断言T的证明是可以有一个机器生成的(可能不是很高效—全搜索方法...
  • 算法复杂度与NP问题

    千次阅读 2019-05-02 19:14:51
    美剧《基本演绎法》S2E2,两位研究 NP 问题的数学家被谋杀了,凶手是同行,因为被害者即将证明“P=NP 问题”。假设人类证明了P=NP 是真的,那么就会有一个算法,能够很快算出某个帐号的密码。《基本演绎法》里面所...
  • 2000年5月,美国克雷数学研究所(CMI)巴黎举行的千年数学大会上宣布对攻克世界7个数学难题的悬赏。P对NP关系问题被列为新千年7大难题之首。2005年《科学》杂志将"NP=P?”问题作为数学科学的代表,列为25个学科难题...
  • 算法NP问题

    千次阅读 2017-05-24 21:42:02
    一个周六的晚上,你参加了一个盛大的晚会。由于感到局促不安,你想知道这一大厅是否有你已经认识的人。你的主人向你提议说,你一定认识那位正在甜点盘附近角落的女士罗丝。不费一秒钟,你就能向那里扫视,并且...
  • NP问题

    2017-08-25 11:27:04
    I’m the Alpha and the Omega,the First and the Last,the Beginning and the End.你是一, 也是万! 是刹那, 也是永恒!...创世纪二零XX年, 历史揭开了新的篇章, 计算宇宙的第一个人诞生了, 这是一个新的纪元
  • P问题、NP问题、NPC问题以及NP-hard问题理解与区分
  • P vs NP vs NPC vs NP-hard

    2016-02-24 19:53:13
     你会经常看到网上出现“这怎么做,这不是NP问题吗”、“这个只有搜了,这已经被证明NP问题了”之类的话。你要知道,大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题...
  • NP-hard NP问题

    千次阅读 2013-10-30 11:13:57
    NP 是 Non-deterministic Polynomial 的缩写,NP 问题通俗来说是其解的正确性能够被很容易检查的问题,这里"很容易检查"指的是存在一个多项式检查算法。 例如,著名的推销员旅行问题(Travel Saleman Problem or ...
  • P vs NP

    2018-01-30 14:21:00
    Complexity Class Computational problem Decision Problems Model of computation Time-complexity classes Space-complexity ...P, NP, co-NP, NPC, NP-hard P NP co-NP NPC NP-hard Euler图 Reference ...
  • 从哈密尔顿路径谈NP问题

    万次阅读 2015-11-06 21:01:35
    1859年,爱尔兰数学家哈密尔顿(Hamilton)提出下列周游...试问能否做一次旅行,从顶点到顶点,沿着边行走,经过每个城市恰好一次之后再回到出发点。这就是著名的哈密尔顿问题。哈密尔顿问题是一个著名的NP问题。
  • 2020年7月出版的《计算机科学》(中国计算机学会会刊)发表了国防科技大学教授、湘潭大学计算机学院特聘教授姜新文题为《哈密顿图判定问题的多项式时间算法》的论文,这标志着数学和计算机科学领域最为重要的...
  • NP难问题

    2020-04-28 23:03:53
    NP难问题求解综述 彭茗菁 2008221104210521 [摘要]: 上世纪70年代开始,诞生了一种许多...它是Clay研究所的七个百万美元大奖问题之一,2006国际数学家大会上,它是某个1小时讲座的主题。 [关键词]: NP...
  • 02. Zero-KNOWLEDGE for NP【对于NP的零知识证明】 ... 01.Introduction to Zero knowledge --Alon Rosen ...也可以我之前的这篇博客,去寻找一些关于其它知识点的博客,下面的博客链接是我整个内容的目录博客,如果有
  • NP完全问题

    2013-08-06 10:57:08
    不能排除NP完全问题可以多项式时间内解决。研究NP完全问题的人非常之多,但是没有人发现任何一个问题的多项式时间解决方案。 如果确定一个问题是NP完全问题,那么工程师应该花时间开发一种近似算法或解决某种易...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,219
精华内容 3,687
关键字:

在系统np中证明