作者Aa841018 (andrew)
看板Grad-ProbAsk
标题[理工] 105清大（P&NP)!
时间Tue Jan 21 20:33:03 2020
https://i.imgur.com/oiFkCVm.jpg
https://i.imgur.com/G23Xg6H.jpg
想问（b)(c)
(b):这题详解是不是少了假设x=np?因为没有这假设，就算sat(npc) reduce to X，x也不
见得是npc说不定是np hard
(c):这和笔记好像有点矛盾，NPC不应该存在P的解法，否则NP=P
但NPC的某些input 又可以在非exponential time解开
时间复杂度排序：exponential>polynomial
（=n^k)
那如果不在exponential 解开，那肯定在polynomial范围内，这岂不是和笔记内容矛盾?
不知道哪里出错…
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.8.74.23 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1579609985.A.10F.html
1F：→ zuchang: B NPC也算是NP hard啊 01/21 20:35
2F：→ Aa841018: 对，但题目说npc应该是希望找出同时属於np,np hard的集 01/21 20:37
3F：→ Aa841018: 合，可是没有先令x属於np，有可能x是属於np hard但不属 01/21 20:37
4F：→ Aa841018: 於np 01/21 20:37
5F：→ zuchang: B 你想法没错 c我的解释是可能要阶乘甚至指数指数 01/21 20:45
6F：推 misaka0120: (c)会不会是说 某些特殊情况可以在p内解 像是bipartit 01/21 20:56
7F：→ misaka0120: e找ham path之类的 01/21 20:56
8F：→ Aa841018: 这我有点不确定，但若存在npc可在p解，似乎直接等价於p= 01/21 21:00
9F：→ Aa841018: np，因为所有np都可reduce到它 01/21 21:00
10F：→ DLHZ: decision不等於在p啊 01/21 21:10
11F：→ DLHZ: 一个叫optimization problem一个叫decision problem 01/21 21:14
12F：→ DLHZ: 好像回答的文不对题 前面就先别看 我误会了 简单来说要找Ham 01/21 21:19
13F：→ DLHZ: iltonian cycle是NPC 但如果今天前提是输入的图一定是cycle 01/21 21:19
14F：→ DLHZ: 当然是可解 他问题在於 for all kind这件事 如果我没理解错 01/21 21:19
15F：→ DLHZ: 那存在一种种类的输入可以简单的解出来的话这叙述就不成立 01/21 21:19
16F：→ DLHZ: 我认为for all kind of inputs拿掉就没问题 01/21 21:24
17F：推 gash55025502: 错在他已经假设了P不等於NP吧 但这是还没有被证明 01/21 22:14
18F：→ gash55025502: 的问题 01/21 22:14
19F：→ orz860708: 3.用SAT想 考虑clause为单独一个X1 判断他可否满足只 01/21 23:16
20F：→ orz860708: 需O(1) 因此input很小的时候不一定需要指数时间 01/21 23:16