mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2010-08-18, 19:31   #45
davar55
 
davar55's Avatar
 
May 2004
New York City

102138 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Not that I agree with the sentiment, but I think the theory is that if P = NP, proving theorem is easy, so who needs a mathematician? Just hook up the polynomial-time SAT solver computer.
Mathematicians count.
davar55 is offline   Reply With Quote
Old 2010-08-18, 20:01   #46
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

1138610 Posts
Default

Quote:
Originally Posted by davar55 View Post
Mathematicians count.
Perhaps. I always thought that mathematicians worked it out with a pencil and paper.

Astronomers, on the other hand, tend to do it at night whereas cosmologists do it with a Big Bang and politicians do it to everyone.


Paul
xilman is offline   Reply With Quote
Old 2010-08-18, 20:56   #47
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2×3×13×83 Posts
Default

Quote:
Originally Posted by xilman View Post
Perhaps. I always thought that mathematicians worked it out with a pencil and paper.

Paul
And logs..... but only when constipated.

David
davieddy is offline   Reply With Quote
Old 2010-08-19, 12:18   #48
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22·5·373 Posts
Default

Quote:
Originally Posted by xilman View Post
Perhaps. I always thought that mathematicians worked it out with a pencil and paper.

Astronomers, on the other hand, tend to do it at night whereas cosmologists do it with a Big Bang and politicians do it to everyone.


Paul
Nah. Mathematicians do it both continuously and discretely.
R.D. Silverman is offline   Reply With Quote
Old 2010-09-19, 08:30   #49
only_human
 
only_human's Avatar
 
"Gang aft agley"
Sep 2002

375410 Posts
Default

This is a follow-up posted on an IBM research site: http://www.almaden.ibm.com/cs/disciplines/pm/#PvNPtalk
Quote:
What's all this about P not equaling NP?

Recently there was considerable interest in a proposed proof that P is not equal to NP. In response to that interest, some members of the theory group gave a talk to describe, for a general scientific audience, some aspects of this work and the community's analysis of it.
(The video starts a little bit into the talk; the speakers are Ken Clarkson, Ron Fagin, and Ryan Williams, in that order; the "D." referred to is Vinay Deolalikar, the author of the proposed proof.)
Video of the talk (including all but the first few slides)
The slides
I've made text format changes to the following slides here but intend no factual changes:
Quote:
Strategy of Deolalikarโ€™s Proof

If k-SAT were in P, then the solution spaces for all k-SAT formulas would have a โ€œsimple structureโ€.
For some k-SAT formulas, the solution spaces for these formulas do not have a simple structure.
Therefore, k-SAT is not in P, and so P โ‰  NP.

Deolalikar proposes to choose certain random
k-SAT formulas, and use known properties of their solution spaces
The last two slides paraphrase the problems by analogy and offer concluding remarks:
Quote:
Can we salvage something from it?
  • Terence Tao's car analogy (paraphrased):
โ€ฆthe paper is like a lengthy blueprint for a revolutionary new car, that somehow combines a high-tech engine with advanced fuel injection to get 200 miles to the gallon.

The LFP objections are like a discovery of serious wiring faults in the engineโ€ฆ but the inventor claims this can be fixed using a weak engine

The solution space objections are like a discovery that, according to blueprints, the car would run just as well if gasoline was replaced with ordinary tap waterโ€ฆ D.โ€™s response to this has been roughly โ€œThat objection is invalid โ€“ everyone knows cars canโ€™t run on water.โ€

The theorem (on the previous slide )
[edit: this is the gist]
[Theorem (Proved by "vloodin" and Terence Tao)
Under the notion of โ€œsimple" given in the paper, k-SAT does have simple solution spaces!]
is like a discovery that the fuel is in fact being sent to a completely different component of the car than the engineโ€ฆ"
  • Can any parts of this car be salvaged?
Quote:
Concluding remarks
  • Deolalikarโ€™s proof seems to be not only wrong, but unfixable.
  • Hardness and solution space complexity seem to be orthogonal.
- New research question: can random k-SAT be used to prove complexity results?
  • There is a new world of community refereeing.
- Good: every part of the proof had corresponding experts
- Bad: those experts spent a great deal of time
- The community is still learning how to work effectively in this new world,
only_human is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
News gd_barnes No Prime Left Behind 255 2022-06-01 00:03
News gd_barnes Conjectures 'R Us 304 2022-04-19 23:07
Other news Cruelty Riesel Prime Search 41 2010-03-08 18:46
The news giveth, the news taketh away... NBtarheel_33 Hardware 17 2009-05-04 15:52
News KEP Riesel Base 3 Attack 4 2008-12-17 11:54

All times are UTC. The time now is 23:09.


Tue Jul 5 23:09:38 UTC 2022 up 82 days, 21:10, 0 users, load averages: 1.75, 1.34, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”