Deolalikar P vs NP paper - Revision history

Aaronszy at 23:42, 30 September 2011

2011-09-30T23:42:29Z

← Older revision		Revision as of 16:42, 30 September 2011
Line 32:		Line 32:
	* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated-mjr.pdf draft 2 + ε], Aug 9 2010. '''File removed,''' Aug 11 2010.		* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_updated-mjr.pdf draft 2 + ε], Aug 9 2010. '''File removed,''' Aug 11 2010.
	* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf Third draft], Aug 11 2010. '''File removed,''' Aug 17 2010.		* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf Third draft], Aug 11 2010. '''File removed,''' Aug 17 2010.
	* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_synopsis.pdf Synopsis of proof], Aug 13 2010.		* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_synopsis.pdf Synopsis of proof], Aug 13 2010. '''File removed'''
	* [http://www.hpl.hp.com/techreports/2010/HPL-2010-95.html HP Technical report], Aug 20, 2010. '''File removed,''' Aug 23 2010?		* [http://www.hpl.hp.com/techreports/2010/HPL-2010-95.html HP Technical report], Aug 20, 2010. '''File removed,''' Aug 23 2010?

AaronSterling: /* Further reading */ TCS Q&A site now in beta

2010-09-17T13:09:20Z

Further reading: TCS Q&A site now in beta

← Older revision		Revision as of 06:09, 17 September 2010
Line 345:		Line 345:
	* Here is a [http://wiki.henryfarrell.net/wiki/index.php/Computer_Science list of blogs in computer science] (including several blogs who have been actively posting on this topic).		* Here is a [http://wiki.henryfarrell.net/wiki/index.php/Computer_Science list of blogs in computer science] (including several blogs who have been actively posting on this topic).

	* [http://area51.stackexchange.com/proposals/8766/theoretical-computer-science Theoretical Computer Science] Q&A site launching ~~soon from stackexchange~~.		* [http://area51.stackexchange.com/proposals/8766/theoretical-computer-science Theoretical Computer Science] Q&A stackexchange site site launching currently in beta.

Teorth at 16:59, 23 August 2010

2010-08-23T16:59:59Z

← Older revision		Revision as of 09:59, 23 August 2010
Line 21:		Line 21:
	* [http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof Fatal Flaws in Deolalikar’s Proof?] August 12, 2010 (Inactive)		* [http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof Fatal Flaws in Deolalikar’s Proof?] August 12, 2010 (Inactive)
	* [http://rjlipton.wordpress.com/2010/08/15/the-p%e2%89%a0np-proof-is-one-week-old/ The P≠NP "Proof" Is One Week Old] August 15, 2010 (Inactive)		* [http://rjlipton.wordpress.com/2010/08/15/the-p%e2%89%a0np-proof-is-one-week-old/ The P≠NP "Proof" Is One Week Old] August 15, 2010 (Inactive)
	* [http://rjlipton.wordpress.com/2010/08/18/proofs-proofs-who-needs-proofs Proofs, Proofs, Who Needs Proofs?] August 18, 2010 (~~'''Active'''~~)		* [http://rjlipton.wordpress.com/2010/08/18/proofs-proofs-who-needs-proofs Proofs, Proofs, Who Needs Proofs?] August 18, 2010 (Inactive)
	* [http://rjlipton.wordpress.com/2010/08/19/projections-can-be-tricky Projections can be tricky] August 19, 2010 ('''Active''')		* [http://rjlipton.wordpress.com/2010/08/19/projections-can-be-tricky Projections can be tricky] August 19, 2010 ('''Active''')

Line 33:		Line 33:
	* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf Third draft], Aug 11 2010. '''File removed,''' Aug 17 2010.		* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf Third draft], Aug 11 2010. '''File removed,''' Aug 17 2010.
	* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_synopsis.pdf Synopsis of proof], Aug 13 2010.		* [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_synopsis.pdf Synopsis of proof], Aug 13 2010.
			* [http://www.hpl.hp.com/techreports/2010/HPL-2010-95.html HP Technical report], Aug 20, 2010. '''File removed,''' Aug 23 2010?

	Here is the list of [[Update\|updates]] between the different versions.		Here is the list of [[Update\|updates]] between the different versions.
Line 299:		Line 300:
	* August 15: Further difficulties in the proof are summarized in another [http://rjlipton.wordpress.com/2010/08/15/the-p%e2%89%a0np-proof-is-one-week-old/ post of Dick Lipton and Ken Regan].		* August 15: Further difficulties in the proof are summarized in another [http://rjlipton.wordpress.com/2010/08/15/the-p%e2%89%a0np-proof-is-one-week-old/ post of Dick Lipton and Ken Regan].
	* August 17: All drafts of the paper are now removed from Deolalikar's [http://www.hpl.hp.com/personal/Vinay_Deolalikar/ home page], leaving only the synopsis and the comment "The preliminary version was meant to solicit feedback from a few researchers as is customarily done. It illustrated the interplay of principles from various areas, which was the major effort in constructing the proof. I have fixed all the issues that were raised about the preliminary version in a revised manuscript (126 pages); clarified some concepts; and obtained simpler proofs of several claims. This revised manuscript has been sent to a small number of researchers. I will send the manuscript to journal review this week. Once I hear back from the journal as part of due process, I will put up the final version on this website."		* August 17: All drafts of the paper are now removed from Deolalikar's [http://www.hpl.hp.com/personal/Vinay_Deolalikar/ home page], leaving only the synopsis and the comment "The preliminary version was meant to solicit feedback from a few researchers as is customarily done. It illustrated the interplay of principles from various areas, which was the major effort in constructing the proof. I have fixed all the issues that were raised about the preliminary version in a revised manuscript (126 pages); clarified some concepts; and obtained simpler proofs of several claims. This revised manuscript has been sent to a small number of researchers. I will send the manuscript to journal review this week. Once I hear back from the journal as part of due process, I will put up the final version on this website."
			* August 20: The paper temporarily resurfaces as a [http://www.hpl.hp.com/techreports/2010/HPL-2010-95.html HP Technical report].
			* August 23: The HP Technical report is no longer available.

	== Bibliography ==		== Bibliography ==

Teorth: /* Discussion threads */

2010-08-19T18:51:10Z

Discussion threads

← Older revision		Revision as of 11:51, 19 August 2010
Line 22:		Line 22:
	* [http://rjlipton.wordpress.com/2010/08/15/the-p%e2%89%a0np-proof-is-one-week-old/ The P≠NP "Proof" Is One Week Old] August 15, 2010 (Inactive)		* [http://rjlipton.wordpress.com/2010/08/15/the-p%e2%89%a0np-proof-is-one-week-old/ The P≠NP "Proof" Is One Week Old] August 15, 2010 (Inactive)
	* [http://rjlipton.wordpress.com/2010/08/18/proofs-proofs-who-needs-proofs Proofs, Proofs, Who Needs Proofs?] August 18, 2010 ('''Active''')		* [http://rjlipton.wordpress.com/2010/08/18/proofs-proofs-who-needs-proofs Proofs, Proofs, Who Needs Proofs?] August 18, 2010 ('''Active''')
			* [http://rjlipton.wordpress.com/2010/08/19/projections-can-be-tricky Projections can be tricky] August 19, 2010 ('''Active''')

	== The paper ==		== The paper ==

Geomblog: /* Specific issues */

2010-08-19T07:42:08Z

Specific issues

← Older revision		Revision as of 00:42, 19 August 2010
Line 89:		Line 89:
	== Specific issues ==		== Specific issues ==

	* '''P=NP only gives polylog parameterizability property of a lift of the k-SAT solution space, rather than that solution space itself''' If P=NP, then the procedure in Section 8.3 of the third draft does not create a [[polylog parameterizability\|polylog parameterizable]] distribution on the solution space of a hard phase k-SAT problem itself, but rather on a <I>lift</I> of that solution space in which many additional variables are added, so that one is now working in <math>\{0,1\}^N</math> for some <math>N=n^{O(1)}</math> rather than in <math>\{0,1\}^n</math>. Of course, one can forget all but the original n variables and return to a distribution on the solution space by projecting, but it is not clear that the polylog parameterizable property is preserved by this (there is no reason why the directed acyclic graph on the N literals has any meaningful projection onto the original n literals). In particular, the projected distribution is not in a recursively factorizable form, and the cluster geometry of the lifted solution space could be quite different from that of the original k-SAT problem (e.g. the set of frozen variables could change, as could the definition of a cluster, and number of flips required to get from one cluster to the next). This issue does not seem to be discussed at all in the paper.		* '''P=NP only gives polylog parameterizability property of a lift of the k-SAT solution space, rather than that solution space itself'''

			If P=NP, then the procedure in Section 8.3 of the third draft does not create a [[polylog parameterizability\|polylog parameterizable]] distribution on the solution space of a hard phase k-SAT problem itself, but rather on a <I>lift</I> of that solution space in which many additional variables are added, so that one is now working in <math>\{0,1\}^N</math> for some <math>N=n^{O(1)}</math> rather than in <math>\{0,1\}^n</math>. Of course, one can forget all but the original n variables and return to a distribution on the solution space by projecting, but it is not clear that the polylog parameterizable property is preserved by this (there is no reason why the directed acyclic graph on the N literals has any meaningful projection onto the original n literals). In particular, the projected distribution is not in a recursively factorizable form, and the cluster geometry of the lifted solution space could be quite different from that of the original k-SAT problem (e.g. the set of frozen variables could change, as could the definition of a cluster, and number of flips required to get from one cluster to the next). This issue does not seem to be discussed at all in the paper.

	To phrase it another way, consider the following excerpt from the paper describing part of the strategy (Page 92, third draft):		To phrase it another way, consider the following excerpt from the paper describing part of the strategy (Page 92, third draft):

Teorth at 18:56, 18 August 2010

2010-08-18T18:56:31Z

← Older revision		Revision as of 11:56, 18 August 2010
Line 20:		Line 20:
	* [http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%e2%89%a0np-proof/ Deolalikar Responds To Issues About His P≠NP Proof] August 11, 2010 (Inactive)		* [http://rjlipton.wordpress.com/2010/08/11/deolalikar-responds-to-issues-about-his-p%e2%89%a0np-proof/ Deolalikar Responds To Issues About His P≠NP Proof] August 11, 2010 (Inactive)
	* [http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof Fatal Flaws in Deolalikar’s Proof?] August 12, 2010 (Inactive)		* [http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof Fatal Flaws in Deolalikar’s Proof?] August 12, 2010 (Inactive)
	* [http://rjlipton.wordpress.com/2010/08/15/the-p%e2%89%a0np-proof-is-one-week-old/ The P≠NP "Proof" Is One Week Old] August 15, 2010 ('''Active''')		* [http://rjlipton.wordpress.com/2010/08/15/the-p%e2%89%a0np-proof-is-one-week-old/ The P≠NP "Proof" Is One Week Old] August 15, 2010 (Inactive)
			* [http://rjlipton.wordpress.com/2010/08/18/proofs-proofs-who-needs-proofs Proofs, Proofs, Who Needs Proofs?] August 18, 2010 ('''Active''')

	== The paper ==		== The paper ==

MarkDilley: /* Online reactions */ trying to make the page shorter / more manageable by transcluding the online reactions - please revert if this SuggestedEdit is not wanted

2010-08-18T06:51:07Z

Online reactions: trying to make the page shorter / more manageable by transcluding the online reactions - please revert if this SuggestedEdit is not wanted

Show changes

MarkDilley: add RightTOC formatting

2010-08-18T06:41:59Z

add RightTOC formatting

← Older revision		Revision as of 23:41, 17 August 2010
Line 1:		Line 1:
			{{RightTOC}}
	This is a clearinghouse wiki page for aggregating the following types of items:		This is a clearinghouse wiki page for aggregating the following types of items:

Teorth: /* 17th August */

2010-08-18T04:38:26Z

17th August

← Older revision		Revision as of 21:38, 17 August 2010
Line 364:		Line 364:
	* [http://web.mit.edu/newsoffice/2010/3q-pnp.html 3 questions: P vs. NP], Larry Hardesty, MIT News Office, August 17 2010.		* [http://web.mit.edu/newsoffice/2010/3q-pnp.html 3 questions: P vs. NP], Larry Hardesty, MIT News Office, August 17 2010.
	* [http://www.livemint.com/2010/08/17220858/PNP-problem-the-claim-the-h.html P=NP problem: the claim, the hype and the mini-furore], Seeema Singh, livemint, August 17 2010.		* [http://www.livemint.com/2010/08/17220858/PNP-problem-the-claim-the-h.html P=NP problem: the claim, the hype and the mini-furore], Seeema Singh, livemint, August 17 2010.
			* [http://blogs.forbes.com/leegomes/2010/08/17/now-its-the-slow-roasting-of-an-hp-mathematician Now, It’s The Slow Roasting Of An HP Mathematician], Lee Gomes, Digital Tools, Forbes blogs, August 17 2010.

	=== Real-time searches ===		=== Real-time searches ===

Teorth: /* 16th August */

2010-08-18T03:09:35Z

16th August

← Older revision		Revision as of 20:09, 17 August 2010
Line 358:		Line 358:
	====16th August====		====16th August====

	* [http://www.nytimes.com/2010/08/17/science/17proof.html Step 1: Post Elusive Proof. Step 2: Watch Fireworks.], John Markoff, New York Times, August 16 2010 online, August 17 in print		* [http://www.nytimes.com/2010/08/17/science/17proof.html Step 1: Post Elusive Proof. Step 2: Watch Fireworks.], John Markoff, New York Times, August 16 2010 online (August 17 in print).

			====17th August====

			* [http://web.mit.edu/newsoffice/2010/3q-pnp.html 3 questions: P vs. NP], Larry Hardesty, MIT News Office, August 17 2010.
			* [http://www.livemint.com/2010/08/17220858/PNP-problem-the-claim-the-h.html P=NP problem: the claim, the hype and the mini-furore], Seeema Singh, livemint, August 17 2010.

	=== Real-time searches ===		=== Real-time searches ===