[理工] 103中央离散必要但不充分 ponwar87123 PTT批踢踢实业坊

楼主: ponwar87123 (干我屁事喔北七) 2020-01-25 15:13:34

https://imgur.com/o2C9aKo
单纯想问题意
这题说要找关系为必要但不充分的叙述，
也就是说左到右成立但右到左不成立
或者是右到左成立但左到右不成立
对吧

作者: Ricestone (麦饭石) 2020-01-25 15:22:00

不是或者，是只有右到左成立且左到右不成立

作者: a80242002 (宽宽) 2020-01-25 16:02:00

错吧，根本没有关系吧不必要也不充分

作者: zuchang (chang) 2020-01-25 16:19:00

NP是可以多项式时间内验证就叫NP

作者: mistel (Mistel) 2020-01-25 18:53:00

C是对的吧若problem属于NP 则存在指数复杂度的算法z大说的应该是sufficient讲精确一点任何在NP里的problem一定存在O(2^p(n))的算法，其中p(n)是非决定性算法的步骤https://wiki.c2.com/?NpComplete可以参考

作者: MASAGA (和泉千晶我老婆) 2020-01-25 19:21:00

借题问个 NP-hard有exponential time algorithm 吗如果有的话 (C)就是必要但不充分了吧

作者: mistel (Mistel) 2020-01-25 21:47:00

MASA大说的我不是很懂 C选项不是讨论NP吗？

作者: MASAGA (和泉千晶我老婆) 2020-01-25 23:03:00

NP-hard不属于NP如果有一NP-hard但不是NPC的问题有exponential algorithm这样的话就不能靠exponential algorithm判断是否属于NP只是我不知道这前提是否是对的XD 也有可能我观念有错想问大家的想法

作者: zuchang (chang) 2020-01-25 23:16:00

我觉得还是不必要因为如果p=np 那就不用指数

作者: mistel (Mistel) 2020-01-25 23:27:00

若p则q 这跟有没有必要指数没什么关系*必要改成用不用https://i.imgur.com/Me0QGpo.jpg https://i.imgur.com/bP2in9K.jpg^^^立宇题库

作者: MASAGA (和泉千晶我老婆) 2020-01-26 08:26:00

我的意思跟详解差不多XD 只是我不知道要用tractable这词@z大即使P=NP 所有NP还是存在exponential algorithm吧

继续阅读