English Wikipedia @ Freddythechick

English Wikipedia @ Freddythechick:Articles for deletion/Permanent is sharp-P-complete

< English Wikipedia @ Freddythechick:Articles for deletion
The following discussion is an archived debate of the proposed deletion of the article below. Please do not modify it. Subsequent comments should be made on the appropriate discussion page (such as the article's talk page or in a deletion review). No further edits should be made to this page.

The result was Clusterfuck. The debate has been hopelessly confused by the fact that the article has changed to two distinct articles; one on the theorem "Permanent is sharp-P-complete" and one on the "Proof of Permanent is sharp-P-complete". It appears that the topic has been split, and that it is impossible to determine which article, or which version of which article, anyone below is commenting on. That at some point one article was set up as a redirect to the other, and the entire situation has been protected against editing makes this hopelessly muddled. There is no prejudice against improving articles during an AFD process, however the manner in which these changes have occured can hardly be called "improvement". The way this situation has worked out, I can't even say with certainty that we have a "no-consensus" situation here. Work out WHICH article we want to delete and WHICH we want to keep, even if we want to delete both or keep both. Once the situation has been sorted out, and we know exactly which article is which and what is going on, feel free to renominate either or both for another go at AFD. Jayron32.talk.contribs 06:54, 20 December 2008 (UTC)

Permanent is sharp-P-complete

Permanent is sharp-P-complete (edit | talk | history | protect | delete | links | watch | logs | views) (delete) – (View log)

Article not encyclopedic, not an article, is a probable copy-vio, and Wikipedia is not the place to (re)-publish research, and this proof is probably not notable.--Tznkai (talk) 19:06, 15 December 2008 (UTC)

  • Keep and improve The proof is certainly notable: its importance is comparable to that of Cook's theorem for NP-completeness, because Permanent is the canonical #P-complete problem, just as 3SAT is the canonical NP-complete problem. I do not believe this article is copy-vio, and is just one of several Category:Article proofs actually. I agree it could be improved, made more readable, more sources used, some sections trimmed etc. Shreevatsa (talk) 19:21, 15 December 2008 (UTC)
  • Keep Even though my eyes tend to glaze over when presented with proofs like that, the result clearly is important, and the proof is too complex to include in either Permanent or #P-complete, which are substantially less technical. 5 sources in article suggest notability, and I note that citeseer has additional citations of at least one of those. JulesH (talk) 19:58, 15 December 2008 (UTC)
  • delete With mathematical proofs we are treading on a very sharp boundary between original research and encyclopedic texts. This particular article is nothing beyond retelling a proof published in an original article, i.e., based solely on the primary source - AFAIK it is not admissible in wikipedia. With proof complex as that, the major issue is woth verifiability: I have no reason to believe that the wikipedian represented correctly the ideas of the proof, and this article may be actually a disservice; and just as well the original proof is available in libraries. In many cases a proof of some theorem is so notable as to be reprinted in several monographs, with commentaries and explanation. An encyclopedic article is possible in this case: it may consist of the outline of a proof, its associations and ramifications as presented by experts in reliable sources. This is not the case here. It is a nice, but still original essay, a non-reliable retelling of a tale. Of course, any wikipedia article is basically retelling of some tales by wikipedians, but the case of mathematics brings the issues of verifiablity no n-th degree. `'Míkka>t 21:48, 15 December 2008 (UTC)
Um, mathematics is more verifiable than any other discipline :) I also agree this proof as it stands (relying on one source, apparently) is not appropriate, but the article itself is very much admissible. Shreevatsa (talk) 06:38, 16 December 2008 (UTC)
I have no reason to believe that the wikipedian represented correctly the ideas of the proof. You can say that about any article on Wikipedia with references, not just the mathematics ones. Your point in making that comment is? The rest of your remark seems to be that you don't like how this article is written. That's never a valid argument to delete, as well you should know. The theorem is notable, and thus it should have an article. Merging or rewriting are all editorial decisions to be proposed and worked out elsewhere. --C S (talk) 20:29, 18 December 2008 (UTC)
  • Delete per mikkalai. Unnotable proof. Tavix (talk) 23:55, 15 December 2008 (UTC)
  • Delete. Whether or not this proof is notable is irrelevent. Reprinting a proof does not constitute an article at all and is merely a primary source. In order to have a wikipedia article we would need to have independent sources discussing the proof. None are presented here. Indrian (talk) 01:01, 16 December 2008 (UTC)
It's possible the article just retells one proof (I don't know; I didn't write it), but there are independent sources discussing essentially the same proof: see the ones in the references. The article will have to be improved to incorporate all of them. Shreevatsa (talk) 06:38, 16 December 2008 (UTC)
  • If the sources discuss the proof then they are about the proof and possibly about the problem. This would be encyclopedic information, a basic of an article with the title, say, Computation of the permananent of a matrix. `'Míkka>t 17:25, 16 December 2008 (UTC)
  • Delete WP:NOTREPOSITORY combined with WP:RAP and WP:INDISCRIMINATE and the above stated by Mikkalai is a good enough basis for deletion for me. Switching to Neutral, would like wording to be better though. ηoian ‡orever ηew ‡rontiers 06:56, 16 December 2008 (UTC)
  • Comment. If deleted, please transwiki to b:Famous theorems of mathematics. -- Jitse Niesen (talk) 15:14, 16 December 2008 (UTC)
  • Delete Firstly, WP:NOTTEXTBOOK. Secondly, WP:MOSMATH says "include proofs when they expose or illuminate the concept or idea; don't include them when they serve only to establish the correctness of result"; this proof is not unusual or illuminating. It consists of showing that a problem known to be #P-complete is equivalent to the calculating the permanent of a particular matrix, a very standard approach to such complexity proofs. Result could be mentioned in the permanent article, but we don't need to reproduce the blow-by-blow details. Gandalf61 (talk) 20:26, 16 December 2008 (UTC)
  • Comment Please. "Tznkai", could you at least attempt to make your case? You say it's probably a copyright violation. All it would take to back that up is to specify some copyrighted source—a web page or a book or something—that you think it's copied from. And you say "probably not notable". I wouldn't think that would be too hard to explain. But you don't attempt it. Michael Hardy (talk) 07:14, 17 December 2008 (UTC)
  • Keep. This result is fundamental to both permanents (and a lot of work on the borders between statistical mechanics and combinatorics) and the theory of #P-completeness (and the polynomial hierarchy more generally) in computational complexity. And as someone else pointed out it's too long to be merged into either of its parent articles. The following argument is kind of waxy, but still, if you're going to get rid of this, you might as well get rid of all of Category:Article proofs and reduce Wikipedia to more of a Schaum's outline of mathematical results, asserted to be true and with pointers to the literature, but with all explanations of why they're true excised. The article could use improvement (too much first person) and I don't care for the title (should be a noun phrase such as Sharp-P-completeness of the permanent rather than a sentence) but those aren't reasons for deletion. —David Eppstein (talk) 17:18, 17 December 2008 (UTC)
  • delete - with all due respect to the importance of the result itself, the article fails to demonstrate the notability of the details of the proof. Also, the requirements to the correctness/validity of proofs are beyond the scope of an encyclopedia, and all the more of wikipedia, which, as it is well-known, is not an instrument of peer review of someone's retelling of the proof. And indeed, the whole Category:Article proofs deserves to be scrutinized as well. The problem with encyclopedic articles which present proofs remind me the following joke retold about several genius porofessors: "During a lecture professor XXX explained some proof, repeating 'Now it is easily seen that...', 'YYY readily implies that ...'. After one of 'it is evident that ZZZ... " he abruptly stopped and started hastily scribbling long formulae in a corner of the blackboard. After ten minutes he wiped sweat from his forehead and continued, 'Yes, it is evident that ZZZ...' Twri (talk) 21:13, 17 December 2008 (UTC)
  • Keep – The result is as good as any in the field of computational complexity. Moreover, the proof is highly notable – I think the standard computational complexity textbook of Papadimitriou makes this case explicitly, which should work as an external reference for notability. (But I’d have to check.) Of course, the current form of this article may fail (indeed, does fail) to explain what’s so great about this proof. But that’s not an argument for deletion, only for improving it. And rename as per David Eppstein’s suggestion. Thore Husfeldt (talk) 21:20, 17 December 2008 (UTC)
    • I like better the siggestion of Mikka, Computation of the permananent of a matrix: it is both general ("Computation") and correctly specific ("permanent of a matrix"), and I am doing this right now. Twri (talk) 21:40, 17 December 2008 (UTC)
      • I don’t agree. The literature on computing permanents is vast, Valiant’s result is just one of many. Upper bounds, lower bounds in restricted models, hardness results in at least two frameworks I can think of, comparison with determinant and pfaffian,… I’m not saying that Algorithms for matrix permanent (or something like that) shouldn’t exist; in fact, that would be a great article. But the present article is much more specific. Thore Husfeldt (talk) 21:49, 17 December 2008 (UTC)
        • Sory, I was not clear or (was not reading the suggestion of Thore Husfeldt clearly): I was talking about a general article, which is clearly missing. Twri (talk) 21:56, 17 December 2008 (UTC)
  • Following up on my own comment, the best quote I could find in Papadimitriou’s book is “The most impressive and interesting #P-complete problems are those for which the corresponding search problem can be solved in polynomial time. The permanent problem for 0-1 matrices, [...] is the classical example here.” (Computational complexity, p. 443, emphasis his). It’s not quite the quote I had in mind, but the best I could find. Thore Husfeldt (talk) 09:55, 18 December 2008 (UTC)
  • Keep (and copy-edit for style and otherwise improve). The arguments for deletion are weak at best. "Copyvio"??? That's utterly arbitrary unless one points to a published article or book or web page that it may be copied from. Most of the other arguments could be addressed by improving the article rather than deleting it. And just saying "not notable" and signing your name is not an argument; you should explain your position. Michael Hardy (talk) 17:51, 18 December 2008 (UTC)
  • Keep I am not familiar with this (deletion) but I think that the article should be kept. Point-set topologist (talk) 18:25, 18 December 2008 (UTC)
  • Comment Apparently additional comments from me have been requested: I've stated its probable copy vio because of the style and the single source attribution. It looks like a copy write violation (likely to have copy/pasted material) and single source attribution runs into serious plagiarism and copyright violation situations. If I took a newspaper article lets say, copied it whole sale, and reworded it only slightly, that is still a copyright violation. I'm not an expert in mathematics, but I've never heard of this proof, I've never seen refresher to this proof, and I've gone ahead and looked briefly, but not in advanced mathematics journals - if an expert insists its notable, go for it. If this ends with a keep I would suggest a turning it into a stub and flagging for improvement, as the current version is unacceptable, even if the topic matter deserves an article as suggested above. Anyway, I have no burning desire to see this article deleted, I just ran across it on random article patrol.--Tznkai (talk) 18:36, 18 December 2008 (UTC)
    • Comment. I think it is very counterproductive to start advocating stubbification for anything that merely looks like it was professionally written. Sometimes articles here have that appearance because the people here who are writing them are in fact professionals, and we shouldn't be discouraging experts from contributing what they know. If you are suspicious that it's a copyvio, try searching Google for matches to some of the unusual phrases, and settle the question positively or negatively for yourself before casting aspersions so wildly. —David Eppstein (talk) 18:53, 18 December 2008 (UTC)
        • I agree with David Eppstein. Stubbification is not appropriate; what is needed here is expansion of the introductory section and some style clean-up. This is a notable theorem with a notable proof that deserves to be presented and has significant encyclopedic value. As a mathematician, I find WP articles about mathematical results that present at least a sketch of the proof to be much more useful and informative than short stubs where the result is only stated with a ref given. This is a published notable proof, so it is not a case of WP:OR. Nsk92 (talk) 20:37, 18 December 2008 (UTC)
      • But it does need some style improvements. Michael Hardy (talk) 19:29, 18 December 2008 (UTC)
    • Additional comments requested? That's one way to put it. I think a reasonable way to put it is that people have noticed that literally not a single thing you wrote makes sense. Your accusation of copyvio comes from the fact that it looks well-written and one main source was used. Silly. You said the theorem or proof is "probably not notable", and yet you also say "I'm not an expert in mathematics, but I've never heard of this proof". Oh, and I suppose you think it's reasonable for a non-expert to say something is not notable because s/he hasn't heard of it? Ludicrous. And I just love the cogent way your nomination was worded! The article is not only "not encyclopedic", it's also "not an article"! And woah, here's news to me, Wikipedia is not the place to republish research! Damn. Let me go back and delete all the articles I've written! --C S (talk) 20:29, 18 December 2008 (UTC)
Week keep the result does seem to be notable, whether the proof is notable is another matter. I generally thing the bar for proofs should be set quite high as there can be problems with OR and verifiability. I'm inclined towards keep here. One point is the article might be better titled Permanent is ♯P-complete note use of sharp ♯ symbol rather than hash # which overcomes technical problems.--Salix (talk): 18:55, 18 December 2008 (UTC)
  • Strong Keep I am really surprised to find this entry up for deletion. I work in pure mathematics, fairly far from technical complexity theory, but even I heard about this theorem. Computation of the permanent of a matrix is a basic example of a ♯P-complete problem and it does play a fundamental role in the subject. There are sufficient references in the article to establish notability of this result already, but there are quite a few more where ♯P-completeness of the permanent is discussed in substantial detail:[1][2][3][dead link]. The article could use expansion of the introductory part where the history of the result is explained in more detail but it certainly deserves to be kept. Nsk92 (talk) 20:17, 18 December 2008 (UTC)
    • I just looked up our library's copy of Papadimitriou's book Computational Complexity and the theorem about sharp-P completeness of the permanent is discussed there in substantial detail: Theorem 18.3 on page 443, with the preceding discussion on pages 439-443. Moreover, the proof that Papadimitriou presents appears to be essentially that given in this article, although I did not have time to digest the details. Let me just quote what Papadimitriou says about the significance of the result before giving the proof (italicization is Papadimitriou's):"The most impressive and interesting ♯P-complete problems are those for which the corresponding search problem can be solved in polynomial time. The PERMANENT problem for 0-1 matrices, which is equivalent to the problem of counting perfect matchings in a bipartite graph (or cycle covers in a directed graph, recall Figure 18.1) is the classic example here:" Really, this unfortunate nomination ought to be withdrawn. Nsk92 (talk) 21:01, 18 December 2008 (UTC)
      • Here are a few more sample secondary refs for doubters: [4] says:"In terms of computational complexity theory, Valiant[Val79] proved the seminal result that computing the permanent of integer matrices is complete for the counting complexity class ♯P, and is therefore NP-hard". Note that the theorem is referred to as a "seminal result". The book of Kozen[5] also discusses its significance. An article in "Encyclopedia of Microcomputers"[6] referes to this theorem as "the seminal result". Here is one more, calling this theorem a "celebrated result"[7]. And so on. Nsk92 (talk) 21:43, 18 December 2008 (UTC)
      • The theorem is "the seminal result", but this result is by Valiant in 1979, and this proof is yet to be proved to be "seminal". I am surprized that mathematicians (are you?) lack the basic logic. Mukadderat (talk) 01:22, 19 December 2008 (UTC)
  • keep: And whoever goes around bringing stuff like this up, stop wasting people's time. Do something constructive instead.72.229.20.108 (talk) 20:36, 18 December 2008 (UTC)
  • Comment All this discussion still has not fixed possible issues with WP:NOTTEXTBOOK. ηoian ‡orever ηew ‡rontiers 21:17, 18 December 2008 (UTC)
    • WP:NOTTEXTBOOK is not an issue here in the first place. We are talking about an advanced mathematical result, not a textbook kind of fact. The result is highly notable and plays a fundamental role in the subject. Its notability has been established by detailed coverage in multiple reliable sources. That is more that sufficient for a keep. Nsk92 (talk) 21:24, 18 December 2008 (UTC)
    You'll notice I used comment, not delete. I was merely referring to the wording of the article. ;) Also, IP 72.XXX.XX.XX, don't attack other editors. ηoian ‡orever ηew ‡rontiers 21:54, 18 December 2008 (UTC)
    Yes, I saw that, but at the time of my reply I also saw your original delete !vote above which I now see you have changed to neutral. I agree with you regarding uncivil comments by the IP, they are not helpful. Nsk92 (talk) 22:00, 18 December 2008 (UTC)
  • Keep per Shreevatsa and Thore Husfeldt. This is pretty far from my area of interest, but I still know of it as a major result. Further, this is good content -- there's not enough of that around! Even as a deletionist (in general) I see value in this article. CRGreathouse (t | c) 22:49, 18 December 2008 (UTC)
  • Delete Please allow me to respectfully notice that people confusing two distinct issues: the fact and its proof. The fact is extremely notable without doubt. However it belongs to Valiant (1979). Discussed here is a proof by different people, which may be smart, but it is secondary follow-up and I fail to see what kind of breakthrough it presents that makes it notable for its own article. Mukadderat (talk) 01:17, 19 December 2008 (UTC)
The article about the theorem stating that computing the permanent is sharp-P complete. You say yourself that the result is notable. There is no requirement for the proof presented in the article to be Valiant's initial proof. For notable mathematical results proofs are often significantly simplified and improved over time by other mathematicians, and it is a standard and accepted practice for WP math articles to give such simplified and modern proofs. As long as the result is clearly attributed to Valiant (which it is) and the proof given is based on a published source (as seems to be the case here), there is no problem. Nsk92 (talk) 01:27, 19 December 2008 (UTC)
The issue of notability is applied not to separate articles, but to any pieces of them. Otherwise what would prevent me from describing my dog in the article dog (of course this is an absurd exagerration, bit where is the boundary?). Also, I supplied my vote with the observation no one made until now. I also subscribe to other wories wxpressed, but I didn't want to be repetitive. But if you insist, then yest, I agree the presentation of a complex proof is on a dangerous verge to original research. In mathematical chain of thought every step cannot be misstepped. "Expert-unfriendly" Wikipedia gives no guarantee that the wikipedian did not make a blunder somewhere. Retelling an event or description of Madagascar consists of small independent, independently verifiable pieces. Whereas a mathematica proof is a monolith, and would never trust a wikipedian. Mukadderat (talk) 01:40, 19 December 2008 (UTC)
Wikipedia math articles routinely contain proofs and/or sketches of proofs. As is anything else, these proofs are subject to WP:V and to scruitiny of other Wikipedia users and if mistakes are discovered they should and are corrected. The math proofs given in math articles do need to rely on published reliable sources, and this one does. As a professional mathematician who does read Wkipedia math articles fairly frequently, I can tell you that there is significant encyclopedic value in both explaining the statement of a result and its significance, and in explaining how it was obtained. Mathematics is not static and changes over time; ideas progress, new tools and notions are introduced, language is simplified, etc. Proofs of important results get simplified, improved and rationalized too. It is entirely appropriate to present simpler and more modern proofs than the original ones, and this is routinely done in WP math articles, as well as in math books and math research articles. For example, the proof of Fundamental theorem of Galois theory would hardly be recognized by Évariste Galois, as most of the language and the notions have changed rather considerably since his time. Regarding your example with your dog and the article dog, the difference with the present case is in WP:UNDUE. Nsk92 (talk) 02:08, 19 December 2008 (UTC)
Whether or not you describe your dog in the article dog is irrelevant to whether the subject of "dog" is notable and the corresponding article should be deleted. --C S (talk) 01:57, 19 December 2008 (UTC)
In fact, I find it ironic that you are complaining that the proof is a "secondary" follow-up. It is in fact the golden standard of Wikipedia that articles should be based, to the extent possible, on secondary sources, not the primary ones. Nsk92 (talk) 01:29, 19 December 2008 (UTC)
In fact I find it ironic that you don't understand that secondary source and "secondary importance" are quite different issues yet you find it possible to insult me by hinting at my low intelligence. If an author of the text we vote about has the same level of logic, then woe to the readers. Mukadderat (talk) 01:40, 19 December 2008 (UTC)
Mukadderat, I usually have a fairly thick skin, but this kind of a personal attack by you is unacceptable. Please retract it. Nsk92 (talk) 02:14, 19 December 2008 (UTC)
Pray tell, where is Nsk92's "hinting of [your] low intelligence"? All I see is your not so thinly veiled insult that Nsk92 and others are "lacking basic logic" and your repeating of that kind of insult in your last response. The article is called, "Permanent is sharp-P-complete". There are plenty of reputable sources that say this is an important, seminal fact playing a fundamental role in the theory. Thus the article should not be deleted. That is the basic logic here. The fact that you insist on conflating this with other issues does not make those saying "keep" lacking of logic. --C S (talk) 01:57, 19 December 2008 (UTC)
The page in question is nothing but the proof of this fact. The fact itself and discussion of its importance may be easily put into Computation of the permanent of a matrix. (Wait, it is already there!) I am voting to delete the proof. Mukadderat (talk) 02:11, 19 December 2008 (UTC)
  • Delete, with a transwiki to Wikibooks if not a copyright violation. The proof is complex enough that it's almost certainly either a copyright violation or WP:SYN. Merge statement of theorem to permanent and #P-complete, if not already done (and it doesn't seem to have been done). Transwiki proof to Wikibooks if not a copyright violation, and delete. The proof, itself, is not notable, as a contrast to Proof that 22/7 exceeds π, where the proof has other significant characteristics. (The name of the article is terrible, as well, and if redirects are necessary for GFDL, it should be moved to Proof that Permanent is sharp-P-complete, and the existing article name deleted. — Arthur Rubin (talk) 02:00, 19 December 2008 (UTC)
  • This article need not be about the PROOF. It could be rewritten to be about the theorem rather than the proof with no change in its title. Michael Hardy (talk) 02:53, 19 December 2008 (UTC)
    • {{sofixit}} I lack the technical knowledge to do so, but apparently you do not.--Tznkai (talk) 04:14, 19 December 2008 (UTC)
  • Keep and rewrite from scratch. The result is notable, so the article should be kept. But the current content of the article is inappropriate, because the details of the proof are not notable. Compare, for example, Euclid's theorem (on the infinitude of prime numbers); Euclid's proof (not just his result) is famous. You all know what I'm talking about when I say "multiply all the primes and add one." I have not seen anyone make a case that the proof that computing permanents is #P-complete is similarly notable. The theorem is notable; the proof is not. A sketch of the proof is appropriate; the details are not. (That said, it would be nice to transwiki the present article to Wikibooks, as suggested above by Jitse Nielsen.) Ozob (talk) 06:13, 19 December 2008 (UTC)
As pointed above in David Eppstein's post, the proof is notable too, because, for example, a classic book on computational complexity by Papadimitriou which is the standard book in the subject, presents essentially the same argument. If this proof is simpler than the original one by Valiant, there is no problem with having this proof: it is informative, directly relevant to the article and encyclopedic. As I said above, with many, probably most, notable results in mathematics the initial proofs are too complicated and inefficient. If the result is interesting, other mathematicians come in and try to simplify and clarify the initial proof, and it is these simplified and clarified arguments that actually make it into books and encyclopedias. It makes perfect encyclopedic sense and in fact reflects the standard practice in Wikipedia articles on mathematical topics to present these new simplified proofs as opposed to the original complicated ones (which also often use language and machinery that becomes outdated). E.g. the proof of the Fundamental theorem of Galois theory contained in that WP article is certainly not the original proof of Évariste Galois, but rather a considerably adapted and simplified modern version. Similarly, proofs of other notable results given in the articles like Picard–Lindelöf theorem, Banach fixed point theorem, etc, are certainly not the original proofs but significant modern simplifications. This is a completely standard, reasonable and acceptable practice. Nsk92 (talk) 06:45, 19 December 2008 (UTC)
Comment I agree with Michael Hardy and Ozob. An article about the result, with a sketch of methods of proof would be encyclopedic; the current lengthy texbook-style line-by-line exposition of one particular proof is not encyclopedic. If the article were re-written to focus on the result, establishing its notability, discussing its history, sketching one or more proofs (at the same level of detail as the present Proof overview section), maybe mentioning some consequences, extensions or generalisations, then I would withdraw my Delete !vote. Fundamental theorem of Galois theory is a fairly good model here (although very undersourced) - note how short its Proof section is. But all that would require a major re-write of the current article. Gandalf61 (talk) 09:43, 19 December 2008 (UTC)
  • Delete, just a proof, not an article about the proof. Can be transwikied somewhere if desired. Note that the early page history contained stuff that was cut and pasted to True quantified Boolean formula, but I have spliced the page histories. Kusma (talk) 10:12, 19 December 2008 (UTC)
    Okay, now that there is a bit of an article, there is something worth keeping. I still think the proof should be removed (e.g., it could be transwikied out to Wikibooks, improving both Wikibooks and Wikipedia). Kusma (talk) 17:03, 19 December 2008 (UTC)
  • DO NOT CLOSE THIS DISCUSSION YET. I've just notified
that this discussion is in progress. We should see if they have something to contribute to this discussion. Michael Hardy (talk) 12:43, 19 December 2008 (UTC)
  • Keep! The article is encyclopedic (for Wiki). There are references in this article, and there are no official experts in Wiki to solve is it true. Let every reader solves it himself. However the article may be improved.--Tim32 (talk) 13:46, 19 December 2008 (UTC)
    Unfortunately it is not an article, but the proof of a theorem. If this can be improved without a complete rewrite, please do so. Kusma (talk) 14:41, 19 December 2008 (UTC)
    As I tried to explain above, a proof of the theorem also has significant encyclopedic value and properly belongs as a part of the article. I have just added some background information and discussion about the theorem's significance, with some references, to the lede. Nsk92 (talk) 15:48, 19 December 2008 (UTC)
    I disagree, but your lede is enough to be used as an article (nothing below the TOC is necessary, though). Kusma (talk) 17:03, 19 December 2008 (UTC)
  • Keep per Hardy and Eppstein points. Tparameter (talk) 16:55, 19 December 2008 (UTC)
  • Delete naive COPYVIO. The recent extension of the initial article was not warranted. The text moved into anothe article with meaningful and reasonalby general title, Computation of the permanent of a matrix. This proof is a blatant copyright violation. Think what will happen is you publish Harry Potter in very close detail. Mathematical proof is intellectual property; you cannot "retell" it in your own words without author's permission and pretend that it is OK. Laudak (talk) 17:47, 19 December 2008 (UTC)
    • Laudak, please stop it immediately! There was no consensus for your massing changes, moves and redirects. Wait until the AfD is concluded and obtain a consensus at the article's talk page before proceeding with such drastic changes. Nsk92 (talk) 18:02, 19 December 2008 (UTC)
      • You are attempting to game the vote. The vote was started about the proof. The expansion of the article shouild be in page Computation of the permanent of a matrix, where I moved the text. All votes to delete was about proof. Laudak (talk) 18:08, 19 December 2008 (UTC)
        • I did not game anything. The article was about the theorem and I have expanded it, as quite a few users suggested, by adding well-sourced information about the theorem. You, on the other hand, unilaterally removed this material and performed drastic changes to the article without consensus to do so and with AfD still open. This is outrageous. Nsk92 (talk) 18:18, 19 December 2008 (UTC)
          • I did not remove your addition from wikipedia. I moved it into appropriate place, with appropriate edit summaries. I don't need consensus to move text into a more appropriate place. This page was about a specific topic: proof. From the very beginning it said: This page gives a mathematical proof that.... And this proof was to be deleted as inappropriate. Laudak (talk) 18:30, 19 December 2008 (UTC)
    • NOT COPYVIO. What on earth? You cannot copyright mathematics; this is absurd. Also, I object to your renaming the article without discussion or consensus. Shreevatsa (talk) 18:04, 19 December 2008 (UTC)
      • Oh yest you can. Just try and copy someone's proof. Laudak (talk) 18:08, 19 December 2008 (UTC)
        • Laudak, your ignorance is astonishing. Ask anyone in mathematical publishing if it is possible to "copy" someone's proof without violating copyright. It happens all the time and is accepted practice, and perfectly legal. --C S (talk) 22:13, 19 December 2008 (UTC)
      • Could somebody please revert Laudak's outrageous edits? The AfD is still open, there was no consensus for either deleting the article or the proof and no copyvio case has been established. The discussion above shows clear consensus that the theorem is notable and I have expanded the article to add background material about the theorem as some of the delete !votes suggested. There is no justification for Laudak's outrageous unilateral actions! Nsk92 (talk) 18:11, 19 December 2008 (UTC)
        • Please stop insulting colleagues. AFD was about the proof. You are adding the text into a wrong place and thus gaming the system. Many people are against this proof.[[The page to expand is Computation of the permanent of a matrix. Laudak (talk) 18:17, 19 December 2008 (UTC)
          • Laudak: please stop yourself. It is very standard to improve articles in content, focus, and title during the course of an AfD, as a way to make them more appropriate for inclusion; see WP:HEY and WP:Article Rescue Squadron. Your reversions of Nsk92's improvements in order to force the AfD to consider only the as-nominated version of the article are counterproductive, WP:POINTy, and bordering on vandalism. —David Eppstein (talk) 18:24, 19 December 2008 (UTC)
            • David, respectfully, I did not delete Nsk92: I moved his addition into Computation of the permanent of a matrix with the appropriate edit summary. Many people vote for deletion of the proof. Do you want a separate vote again, when this one ends and I will want to delete the proof out of the page if it is expaneded and survive? The vote was started about proof and must be ended about proof. Otherwise we are voting for diffierent articles. This is confusion. Laudak (talk) 18:28, 19 December 2008 (UTC)
              • Please, give me a break. Just as many people voted for keep; the AfD was not closed and there was no consensus to do what you did. Nsk92 (talk) 18:33, 19 December 2008 (UTC)
              • This article is about hardness of the permanent. Whether the word proof is in the title or not, Valiant's hardness result is the main subject and the question is about the notability of that specific result as the subject of an encyclopedia article. Computation of the permanent is both a different topic (the emphasis being on upper bounds rather than lower bounds) and much broader. I see an ideal version of the article as focusing on the specific result but still including an outline of the proof (though likely not as in-detail as the nominated version). Your insistance that the only possible version of the article we can consider as the nominated one prevents any such refactoring attempt and unfairly forces any future article focusing more on the result than the proof (but still including the proof outline) to face a heavier obstacle of G4 speedy deletion. —David Eppstein (talk) 18:37, 19 December 2008 (UTC)

Article protected against revert war. Any admin has rights to unprotect without asking me first. `'Míkka>t 18:25, 19 December 2008 (UTC)

I don't object to protection in principle and I know that protecting the wrong version is a time-honored tradion, but please restore the pre-Laudak's version that includes my improvemennts and that most of this AfD is about. All of the discussion above relates to that pre-Laudak's version and the kind of radical transformations he attempted must wait until the AfD is completed. Nsk92 (talk) 18:31, 19 December 2008 (UTC)
I'm not going to unprotect (it was indeed an edit war, and you properly protected it in the wrong version) but doesn't this lead to a problem with the AfD? As I just pointed out to Laudak above, it is standard to attempt to improve articles in order to stave off their deletion, and Nsk92 has been working to try to do so with this article. Protected, it is impossible to make such improvements and this gives an unfair advantage to the deletionists in this debate. —David Eppstein (talk) 18:31, 19 December 2008 (UTC)
Not only that, but subsequent AfD !voters are looking at something radically different from the pre-Laudak version which does not show my improvements at all. Why don't we break with tradition and protect the right version for a change. Nsk92 (talk) 18:35, 19 December 2008 (UTC)
David, I understand that you may be annoyed by actions of Laudak, and therefore ignore his argument. His argument was that the deletion was started about the particular topic, namely the proof of some statement. There are many wikipedia articles which topics are specific proofs. And this is OK. This AfD discussion stared as deletion of the proof. During the discusion the article's topic started to change: it started to shift into article about the problem. But the article about the problem already exist: it is computation of the permanent, i.e., the "sharp-P-complete" page started turning into a fork, which is unnecessary. I guess Laudak is relatively new and does not know this wikilawyering term, and hence made his life harder and gained him more enemies :-). `'Míkka>t 18:42, 19 December 2008 (UTC)
"This AFD discussion stared[sic] as deletion of the proof..." Nope, that's your POV. The deletion discussion started with "Article not encyclopedic, not an article, is a probable copy-vio, and Wikipedia is not the place to (re)-publish research, and this proof is probably not notable". The issues here are "not encyclopedic" (this includes the article title and substantial content not related to the proof which existed back then), "not an article" (I have no idea what this means), "probably copy-vio" (let's put in the kitchen sink too!), "(re)-publish[ing] research" (in order to avoid NOR, we have to be republishing, so I have no idea what this means), and "proof is probably not notable", which is in your eyes, the only relevant issue as the discussion supposedly only started with this, right? Mikka, you don't own the discussion and you and the others certainly are not supposed to be able to hijack an AFD in this manner. I suppose the thought of just warning about 3RR and letting the AFD proceed never occurred to you. --C S (talk) 22:13, 19 December 2008 (UTC)
The improvements I made clearly show that the theorem of Valiant is notable, even famous, and more than deserves a separate article, rather than a meager mention in computation of the permanent. The AfD is and was about the theorem, which is a famous and notable mathematical result. Nsk92 (talk) 18:48, 19 December 2008 (UTC)
A meager mention would be in place in permanent. The page computation of the permanent safely holds what you wrote so far. When it grows over 32K, then you may split them into several pages. This is how wikipedia works: meager pages grow, mutate, split, merge, split again... Game of life. `'Míkka>t 19:11, 19 December 2008 (UTC)
The article computation of the permanent was created on Dec 17, well after this AfD started, and edited by the most ardent !delete voters here, including Mukadderat and Laudak. Talk about gaming the system! It is thecomputation of the permanent article which is a fork for the article discussed in this AfD. Nsk92 (talk) 19:55, 19 December 2008 (UTC)
  • Note For the subsequent AfD !voters: please look at the pre-protection version[8] reflecting improvements to the article, before !voting. Nsk92 (talk) 18:39, 19 December 2008 (UTC)
  • No vote. This is difficult. I might make an analogy with the pages containing source code implementations of algorithms, such as quicksort implementations, which were long ago deleted via AfD per WP:NOT (Wikipedia:Articles for deletion/Quicksort implementations). In my experience, detailed mathematical proofs are not well-maintained by the wiki process; well-meaning contributors tend to introduce small errors into the proof that make them invalid. I think it is acceptable to have an article about a theorem, with an informal proof sketch, that also describes the impact of the theorem; in this case, I think it'd probably be best to just take the proof summary and an example or two and merge it back into Sharp P complete, with a reference to the paper for a full exposition.
Oh, and regarding the silly edit warring - I move for an extension of the AfD by another few days in light of the protection. Dcoetzee 18:43, 19 December 2008 (UTC)
I would also suggest to do something to separate the votes about two conflated issues: the problem and the proof, in an analogy with your example about quicksort implementations. As I see in this discussion, some people who woted to keep the (expoanded) article still added that they want the proof gone. `'Míkka>t 18:48, 19 December 2008 (UTC)
And I would suggest that we restore the version that was being !voted on until an hour ago so that people know what they are actually !voting on. Regarding separating the theorem and the proof: while I believe that the proof belongs in the article about the theorem, in the formal sense the question of including or not including the proof is a content WP:WEIGHT issue for an article, not a deletion issue. If an article about the theorem is kept, the question of whether or not the proof should remain a part of the article is something that would need to be worked out in the talk page of the article. AfD is not the place for making these kinds of decisions. Nsk92 (talk) 18:55, 19 December 2008 (UTC)
The vote was going on long before your edits, and about the different issue. You were free to write a separate article about the problem, under correct title, which is computation of the permanent of a 0-1 matrix, or something. The article was about the proof and no particularly forcing reason to change the subject and to re-start yet another discussion in a talk page when we already have it. Laudak (talk) 19:02, 19 December 2008 (UTC)

I am sorry I got myself dragged into an edit war. I was offset by a revert of my good-faith edits with false edit summary: the reverter said that I deleted the proof, which I did not; exactly the opposite. Therefore I made the resoration, assuming that the reverter will undestand their mistake. However I was reverted again with edit summary which made me to conclude that the author wants to own the article: when only two are in disagreement and one side starts speaking about consensus, it usually means that in his view his consensus is better than mine. This kinda pissed me off. Anyway, this was first time with me here and of course it was silly. A good lesson. Thanks, good bye. I will not pursue the issue any more. Laudak (talk) 19:02, 19 December 2008 (UTC)

  • I see that Laudak has moved this page from Permanent is p-sharp complete to proof that permanent is p-sharp complete. I'd have kept the old title and changed it to an article about the theorem rather than the proof, possibly including a proof or a sketch of a proof, if I'd known enough about the role of this theorem to do that fairly quickly. Laudak's new title seems biased against that. Should we move it back? Michael Hardy (talk) 19:21, 19 December 2008 (UTC)
    • Yes, I would prefer both the initial title and the previous version to be restored, at least for the duration of this AfD. Since Laudak has officially bowed out from pursuing this issue further, could one of the admins here please restore this version [9] (which included a reasonably extensive discussion of the theorem and its significance, that I have added today, with multiple sources) and perhaps unprotect the article, so that the AfD can continue normally from the point where it was before all the moves and redirects occurred? Nsk92 (talk) 19:25, 19 December 2008 (UTC)
      • I was voting both against the proof and an article which contains solely the proof. I agree with Laudak's move, which restored the initial focus of the vote. I have no doubt that the result is a milestone and deserves the inclusion in wikipedia, but no one proved yet that proof in question is a comparable milestone. I find it ridiculous that someone changed the subjhect of the discussion and wants the original discussion to be restarted somewhere in a talk page when only a handful hardened POV-pushers will see it, and they may arrange whatever consensus they want. Mukadderat (talk) 19:38, 19 December 2008 (UTC)
        • P.S. Someone has removed my several tags I placed to indicate that the article in question is original research and of poor quality, too (and hence to be deleted) without fixing the problems or providing references. For starters, Someone "improved" the article with "By the definition of #P, #SAT is a #P-complete problem". Well, the article Sharp-P says nothing to this end. And there is no Sharp-SAT page to become wiser. I read more and it has more and more such dubious statements. I guess it was written by a college student as an assignment, and I am very surprised people want to keep it or "improve" a text which sucks by wikipedia standards despite pretty pictures. If someone thinks I am nitpicking, here is a problem: Both #P and proof for "permanent of 01- matrix" are introduced in the same 1979 paper. Since its title was "The complexity of computing the permanent", it is rather reasonable to assume that perm was the first ever #P-complete problem. Therefore its proof based on #SAT may look simpler but sweeps under the carpet the proof that #SAT is #P complete (and leaves the suspicion in circular logic; not that I believe that Ben-Dor made such a stupid mistake, but it is quite possible that someone publishes a "simpler" proof for #SAT which by some chain may be based on Perm and it finds its way into wikipedia). What I am saying, in math it is important to clearly ane explicitly keep track the causative chain. Mukadderat (talk) 19:58, 19 December 2008 (UTC)
          • Don't know who removed your tags (you'd have to look through the history log), but the other changes you are complaining about were made by Laudak. You may also want to look more carefully at the last version before Laudak's revisions:[10] It did contain quite a few references and a discussion, in the lede, of the significance of the theorem, that I added this morning. Nsk92 (talk) 20:07, 19 December 2008 (UTC)
            • The phrase in question is from "proof overview", and I checked it is in the pre-Laudak version. Laudak only moved the intro part elsewhere, by the way; he did not revert to some old version. Your addition is very good indeed (I rephrased it a bit), but it did not impove the proof itself in a slightest bit, and I want this proof gone and forgotten. Mukadderat (talk) 20:14, 19 December 2008 (UTC)
  • Delete "Below we give a mathematical proof that follows Ben-Dor and Halevi (1993)" Um, no we don't, that would be Wikibooks or some such. We discuss the theory but we don't do textbook proofs. Guy (Help!) 20:22, 19 December 2008 (UTC)
    • Too bad you're looking at the gamed version. --C S (talk) 22:04, 19 December 2008 (UTC)
  • Delete and transwiki per Guy. Septentrionalis PMAnderson 21:19, 19 December 2008 (UTC)
    • You are too. --C S (talk) 22:04, 19 December 2008 (UTC)
  • Close AFD as gamed by Mukadderat, Laudak, and Mikkalai. A fork has been created from the initial article "Permanent is sharp-P-complete" and the initial article moved to a new title and substantially revised. This is about as ludicrous as arguing that the article dog should be deleted because it contains too much information about Mukadderat's dog. Then when people argue "dog" is notable and should be kept, I moved dog to Mukadderat's dog and say, "I'm focusing the discussion on the relevant topic which is whether Mukadderat's dog is notable or not." --C S (talk) 22:03, 19 December 2008 (UTC)
  • Note to subsequent AfD !voters: Before !voting, please take a look at the pre-Laudak version of the article[11], that contained substantial additional information, including a discussion of the theorem's importance, and quite a few more references compared with the version of the article that was nominated and compared with the current Laudak's protected version. Also please note that the title of the article has been moved by Laudak too and that the original title was the statement of Valiant's theorem, Permanent is sharp-P-complete. Thanks, Nsk92 (talk) 22:23, 19 December 2008 (UTC)
  • Comment OK, now that this has been moved from Permanent is sharp-P-complete to Proof that permanent is sharp-P-complete, this could get deleted and then a new article could be created titled Permanent is sharp-P-complete, which would be about the theorem rather than about the proof. The objection expressed by some of the "delete" voters would not apply to that. Would someone then speedily delete it as "recreation of deleted content"? Michael Hardy (talk) 22:37, 19 December 2008 (UTC)
  • Summary of the attempted "fix" and why it is lacking: The article which had as title the theorem "Permanent is sharp-p-complete" has had all material about the theorem's impact and relevance moved to another article called computation of the permanent. The leftover material, on a standard proof of this theorem, was then moved to Proof of permanent is sharp-p-complete. Does the move make sense? As David Eppstein indicated above, computing the permanent is concerned with upper bounds, while saying a problem (like PERMANENT) is #P-hard is concerned with lower bounds. I would go even further. Saying a problem is #p-complete only says the general problem is hard. The average case could be much easier. And if one is truly concerned with the computing of the permanent, probabilistic methods could make the problem a lot easier. (Some stuff like this is already there, I notice, in "Computation..." and was moved there from the article Permanent) In other words, the practical problem of computing the permanent is really only somewhat related to this result, and it is a substantial, large topic in its own right. The move was entirely inappropriate in this regard. What would have been reasonable would have been to move only the stuff related to the detailed proof out of the article into another one called "Proof..." But then for people who are fixated upon deleting this particular article, that would hardly be satisfactory, would it? What would even be more reasonable would be just to raise the topic of whether the proof is too detailed on the talk page of the article.--C S (talk) 00:05, 20 December 2008 (UTC)
  • Carefully read nominator's reasons
  1. probable copy-vio - there is no evidence that this is copyvio, just an unfounded assertion,
  2. Wikipedia is not the place to (re)-publish research - so we can't republish anything ???
  3. proof is probably not notable - the nominator argues from ignorance as a reason for deletion. 86.167.196.116 (talk) 00:11, 20 December 2008 (UTC)
  • Sockpuppets: Based on their strange use of the English language, I suspect that several of the usernames in favour of deletion are operated by the same person. Will an admin please check their IP addresses. 86.167.196.116 (talk) 00:54, 20 December 2008 (UTC)
    • Comment. I see no evidence. The keep voters, on the other hand, seem to be mostly using similar phrasing. (No, seriously, I've seen most of both groups on math articles before.) Please be specific. — Arthur Rubin (talk) 01:18, 20 December 2008 (UTC)
      • I agree, the sockpuppetry claims seem far-fetched. As far as I can see, all the !delete voters are in fact established users. There were enough instances of actual wrongdoing here but sockpuppetry was not one of them. Nsk92 (talk) 01:50, 20 December 2008 (UTC)
The above discussion is preserved as an archive of the debate. Please do not modify it. Subsequent comments should be made on the appropriate discussion page (such as the article's talk page or in a deletion review). No further edits should be made to this page.
Retrieved from "https://enwiki.freddythechick.net/index.php?title=English_Wikipedia_@_Freddythechick:Articles_for_deletion/Permanent_is_sharp-P-complete&oldid=16598496"