看板ACMCLUB
标 题Re: [转录][闲聊] NP versus P
发信站批踢踢兔 (Mon Aug 9 16:56:17 2010)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
http://www.scribd.com/doc/35539144/pnp12pt
上面的hold up 的话真要说老师是先知啊
※ 引述《pangfeng (P老师)》之铭言：
: ※ [本文转录自 hil 看板]
: 作者: hil (随机客) 看板: hil
: 标题: [闲聊] NP versus P
: 时间: Wed Jul 4 22:55:27 2007
: 自从 Computational Complexity Weblog 易手之後，
: 「随机客」觉得有趣的东西变少了，所以上去浏览的频率也逐渐降低，
: 难得发现一篇比较好玩的：
: Down to 100% sure that P does not equal NP
: http://weblog.fortnow.com/2007/06/down-to-100-sure-that-pne-np.html
: In 1985 I was 120% sure that P\ne NP. Why? Scott gave a nice list of
: reasons here.
: In 1988 I was down to 110% sure that P\ne NP. Why? Because the Graph
: Minor Theorem showed that many problems had faster algorithms than
: previously thought. Example:
: For all g, Determining if a graph G is it of genus g. can be
: solved in O(n^3) time (constant depends on g).
: Note that the Graph Minor Theorem involves some very deep math. It took
: Robertson and Seymour many years to get the result. The papers are called
: Graph Minors I, Graph Minors II, etc. and in there someplace (perhaps around
: Graph minors XVII) is the graph minor theorem. I do not think that P=NP will
: be shown by using the Graph Minor Theorem; however, the fact that some very
: deep math lead to some problems having low complexity means that it could
: happen again, perhaps to SAT. Hence my confidence in P\ne NP went from 120%
: to 110%.
: In 2007 I was down to 100% sure that P\ne NP. Why? Because Valiant used some
: strange techniques to solve the following problem in polynomial time.
: Given a monotone boolean planar formula in 3-CNF form determine if
: the number of satisfying assignments is a multiple of 7. (NOTE- the
: problem for multiple-of-2 is Parity-P complete and hence NP-hard).
: Again, a surprising algorithmic technique leads to problems being easier
: than we thought. To be fair, this is not a problem people looked at much
: (if at all). But the technique employed are truly new and my concern is
: that other truly new approaches may prove powerful enough to get SAT in P.
: Neither NL closed under complementation nor Factoring in QP has made me
: lower by percent belief that P\ne NP. But they were surprising results and
: I can see someone else lowering theirs because of them.
: So I'm down to 100% sure that P\ne NP. It will take a truly remarkable
: result for me to go lower than that. Like a polynomial time algorithm for
: SAT.
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 112.105.111.39