Talk:♯P-completeness of 01-permanent

Illustrations

There need to be some illustrations in the article of the graph constructions used in the proof. In particular, "Figure 1" and "Figure 2" are mentioned in the article, but there are no figures. Deepmath (talk) 17:51, 12 March 2008 (UTC)

Now that you mention it, that's a bit worrisome and suggests the text might be copied from the stated source. It may just be referring to figures in the source though (which still isn't very useful). Someone with this book should check it out. Dcoetzee 02:31, 13 March 2008 (UTC)

I don't have the book you are talking about, but the article seems to follow http://citeseer.ist.psu.edu/ben-dor95zeroone.html pretty closely. It's also odd that there was a deletion log associated with this talk page. Deepmath (talk) 06:04, 13 March 2008 (UTC)

I guess this is an old discussion, but the deletion log associated with Talk:Permanent is sharp-P-complete is uninteresting. User:SatyrBot automatically added a WP:Logic banner to this article and a lot of other vaguely-relevant articles, creating a talk page since there wasn't one already. After some discussion on the project talk page, it was persuaded to remove these banners, causing the talk page to be deleted again. —David Eppstein (talk) 07:12, 20 December 2008 (UTC)

Proof

There aren serious problems with proofs in wikipedia.

Wikipedia is ancyclopedia, not place for mathematical publications. Encyclopedia presents general overview of facts, e.g. math. Duplication of a proof is original research however you look at it. If it lcosely follows the original paper then it is copy of original research it its direct sense: you are copying the original "original research". If you are retelling the proof in your words, it is still an original research, since it is wikipedian's interpretation of the proof, and there is no way to verify that wikipedian's interpretation is correct. The proof may be explained in wikipedia only when it becomes available from secondary sources: eg., textbooks, or general monographs, i.e, when there is sufficient evidence that the particular proof in question undergone an extensive peer review and was recognized as notable.

Another problem with the text of the proof is that it is written in non-encyclopedic, frivolous style, not accepted in wikipedia. `'Míkka>t 15:20, 13 November 2008 (UTC)

I can understand the objection to this proof on WP:COPYVIO grounds, but I disagree with the claim that proofs have no place on Wikipedia. See Category:Articles containing proofs and Category:Article proofs. This discussion has been made before. Shreevatsa (talk) 15:25, 13 November 2008 (UTC)

I have reverted[1] Laudak's removal of the proof from the article and I most strongly object to any such removal. The proof of the theorem properly belongs in the article about the theorem, not somewhere else. The proof is well-sourced, based on a published article in a reliable source, directly relevant and encyclopedic. Having proofs of important results, when reasonable spacewise, is a standard convention in Wikipedia math article and there is no reason not to follow it here. Nsk92 (talk) 17:51, 19 December 2008 (UTC)

Further, there was no consensus for either renaming or redirecting the previous title. Nsk92 (talk) 17:58, 19 December 2008 (UTC)

Why is the proof of such a fundamental result cited from a paper that appeared in a second rated symposium?

Propose to change

If this were unprotected I would just go ahead and do this, and maybe it doesn't need protection now that the AfD is over (for now), but: I would like this article moved back to a phrase that describes the significant result itself rather than its proof (my proposal: Sharp-P-completeness of the permanent, since I think noun phrases work better than sentences as titles), and I would like the contents reworked to emphasize the result rather than its proof. This does not mean removing the proof altogether, but it probably means reducing it to a mere proof outline. My opinion: this result is significant enough to stand on its own, this proposed change is better than leaving an article about the proof itself (which I agree is not especially notable), and it's also a better idea than trying to merge this subject into an article on upper bounds for 0-1 matrix permanent algorithms or on #P-completeness. But it would be good to get something resembling a consensus before doing anything, so I welcome discussion. —David Eppstein (talk) 07:06, 20 December 2008 (UTC)

I agree with the above suggestion. I would like to see something like the original title of the article restored and also agree that the article, both in its pre-AfD form and in the pre-holy-of-all-messes form[2] was lacking balance and needed a greater emphasis on the discussion of the significance of the theorem, its applications, generalizations, etc. Regarding the proof itself, while I think it is a good idea to actually keep the proof also as a part of the article, I would also find it acceptable if the proof is reduced to the outline of sorts, provided it is not too short and sufficiently informative. Nsk92 (talk) 10:28, 20 December 2008 (UTC)

I agree, as a first step. I don't think the details of a proof (especially if in error, as in Cook's Theorem, where I recently removed a "disjunction" was was incorrect) necessarily add to understanding of the results. The methods can be notable and of interest, but the details of how they're applied to the proof of the specific result almost certainly cannot be. The result is certainly significant, but I'm not absolutely sure what remains shouldn't be merged to #P-complete. We'll just have to see what's left. — Arthur Rubin (talk) 16:58, 20 December 2008 (UTC)

Since the theorem is clearly significant, and even famous, it certainly deserves its own article, regardless of the existence of broader articles like #P-complete. There is also significant potential for expansion of an article about the theorem itself, which would discuss its further applications and generalizations. Regarding the proof, a fairly standard convention used in math articles is that outlines of proofs of important results may be presented and, if not excessive in length, sometimes complete proofs as well. E.g. this is the case for articles like Banach fixed point theorem. Procedurally, including a proof outline is not any different from a plot outline for a book or a movie and is often more encyclopedic than the latter. Nsk92 (talk) 17:10, 20 December 2008 (UTC)

E.g., in terms of generalizations, by looking at a few of the reviews in MathSciNet that refer to Valiant's theorem, here is an example of a generalization: Hartmann, W. On the complexity of immanants. Linear and Multilinear Algebra 18 (1985), no. 2, 127--140. From what I understood by reading the review, immanants of matrices are generalizations of both the permanent and the determinant, and are defined with respect to particular characters on the symmetric group S_n (with permanent and determinant being special cases). The paper of Hartmann discusses complexity of computing immanants and, according to the review, generalizes Valiant's proof. This is exactly the sort of thing that could be included in an article about Valiant's theorem, given time. Nsk92 (talk) 17:29, 20 December 2008 (UTC)

I suspect (but haven't yet done the research to verify) that this result is notable not only for showing that polynomial existence problems could turn into hard counting problems, but also as a simple combinatorial base problem from which many other #P-hardness results derive. If so, I think that's more important than the details of the proof. —David Eppstein (talk) 19:06, 20 December 2008 (UTC)

I agree; #P-completeness of the permanent seems the most appropriate title for the article. Shreevatsa (talk)

Bird-eye view

Now that some dust settled, let me remind you that there are three to four "nested" articles which talk about the issue:

• Permanent contains section "Permanent computation" with
  Main article: Computation of the permanent of a matrix
• Computation of the permanent of a matrix contains section "Permanent of a 0-1-matrix is #P-complete"
• Permanent is sharp-P-complete is a redirect to proof of #P-completeness, although it may well be an article in its own, Sharp-P-completeness of the permanent computation problem or smth. like that. - and which is what most "keepers" had in mind when vioting to keep.
• Proof that permanent is sharp-P-complete (which is actually Proof that permanent is sharp-P-complete, by Ben Dor and Halevi), which is what "deleters" and even several "keepers" wanted to keep.

Since I was acused of "engineering" something (I have no idea what) during the AfD, let me try to engineer a bit here as well, namely what is to keep. `'Míkka>t 22:06, 20 December 2008 (UTC)

Poll

Proposal 1: Basing on the amount of text I suggest to keep the following structure:

1. Permanent
2. Computation of the permanent of a matrix
3. Sharp-P-completeness of the permanent computation problem (or a better title; or keep old one)

I am also inclined to keep #2 and #3 merged for the time being, since there is not much text in both, but I think there is a strong feeling to single out "perm #p-hardness" into a separate page.

Support:

1. `'Míkka>t 22:13, 20 December 2008 (UTC)
2. I think there is plenty of algorithmic material to discuss in the "Computation of the..." article. I don't see the point in the "computation problem" part of your suggested title — it seems like pure redundancy to me (the only thing that can be #P-complete is a computational problem) but I also think it is important enough to stand on its own as an article separate from the permanent, #P-completeness, and permanent algorithm articles. Note that my support here is not for keeping the upper and lower bounds articles merged — the proposal as I believe you have written it is for three separate articles. —David Eppstein (talk) 23:52, 20 December 2008 (UTC)
3. Support, but keep the old title in case #3, per user:C S in #Change the title: names may be figured out independently; no rush. A good approach would be to analyze how the theorem is most commonly referred to, then retitle. Mukadderat (talk) 16:29, 23 December 2008 (UTC)
4. Support, with #2 and #3 (this one) kept separate. #2 is about methods for computation -- upper bounds -- while #3 is about hardness of computation -- lower bounds, specifically #P-completeness. Shreevatsa (talk) 16:49, 23 December 2008 (UTC)
5. Here’s my view, then: Permanent is the main article about permanents, like Minc’s book Permanents (1978) or the chapter on Permanents in van Lint and Wilson A course in combinatorics. Focus on discrete maths, with a section on computation. Computing the permanent is about computing it. It includes: naïve algorithm • Ryser’s formula • Connection to perfect matchings and cycle covers • Connection to the determinant (and account of historical mystification about why they are computationally so different) • Approximating the permanent • Valiant’s counting complexity theory, including #P-completeness • Valiant’s algebraic complexity theory, including the class VNP • Unconditional lower bounds in restricted models: Jerrum–Snir in monotone circuits, Shpilka and Wigderson in bounded depth, Raz in multilinear formulas. I would love to see this article (I’ve left pointers on the relevant talk page). #P-completeness of the permanent remains as a very specialised article explaining Valiant’s proof. There are several neat constructions available today, for example some pretty slick XOR-gadgets. I am not quite sure which mechanisms Wikipedia should employ to choose among different candidates for proof, so this may actually be difficult to edit collaboratively. Thore Husfeldt (talk) 17:08, 23 December 2008 (UTC)
   • The whole fuss started because is is not Valiant's proof. Actually, it would be a good idea to have summaries of all reasonably different proofs. `'Míkka>t 00:31, 24 December 2008 (UTC)
6. Support three pages with whatever titles are good in math and English. Twri (talk) 22:56, 24 December 2008 (UTC)

Oppose:

1. Strong Oppose. The article Computation of the permanent of a matrix was started during the AfD as a fork for this one and regardless of the amount of text there (much of which was lifted from this article after I had added it), it is a poisonous fruit of AfD gaming and, in my strong opinion, it must be merged/redirected to this one after all is said and done. Moreover, the theorem of Valiant, as a famous and notable mathematical result, deserves its own separate article, specifically about the theorem, its significance, generalizations and possibly outline of the proof and/or a proof. Nsk92 (talk) 23:29, 20 December 2008 (UTC)

Neutral:

1. Neutral. I don't think that's a good choice of articles. There should not be a proof article unless the proof, itself, is notable, and there probably shouldn't be a proof section in any of the articles. — Arthur Rubin (talk) 00:10, 21 December 2008 (UTC)
   • Comment. Please note the lack of the word "proof" in the titles of the three suggested articles. An article on the result that the permanent is #P-complete need not be a detailed presentation of the proof of that result. —David Eppstein (talk) 00:11, 21 December 2008 (UTC)
     • Comment. I'm sorry I wasn't clear. My comment wasn't directly on point with the proposal. I don't think I misinterpreted the proposal, I merely didn't comment on it. — Arthur Rubin (talk) 00:34, 21 December 2008 (UTC)

Proposal 2: whatever happens with the articles, the detailed Ben Dor proof is to be deleted, replaced by an informal description based on any summaries of the proof published elsewhere. Deailed retelling the proof by a wikipedian is not an option.

Support:

1. `'Míkka>t 22:13, 20 December 2008 (UTC)
2. Per Mikka. If there is external commentary on the Ben Dor proof, then that might be appropriate. — Arthur Rubin (talk) 00:10, 21 December 2008 (UTC)

   Sorry, but I find the "Deailed retelling the proof by a wikipedian is not an option" statement quite absurd. Procedurally, there is no difference between retelling a proof of a theorem and retelling a plot of a book or a movie (a common WP practice), and the former is certainly a great deal more encyclopedic than the latter. In fact we have loads of technical science articles on Wikipedia that can, in the proper sense, be only adequately verified by people with sufficient background knowledge. This has never been a problem and such technical articles are considered no less verifiable than articles about cartoons and soap operas. Many Wikipedia math articles have sketches of proofs or actual proofs in them and it is particularly useful to have them for famous results like this one. It is quite a common and accepted practice. Banach fixed point theorem is a good example but there are, of course, lots more. Further, the insistence on a proof having independent notability is absurd as well. Almost all Wikipedia articles include discussion of and references to subtopics that are not necessarily notable themselves. The real questions to consider here are weight, balance and reliability/verifiability. If a proof is too long and detailed compared with the rest of the article, this may represent a balance problem that can be fixed in various ways (e.g. by expanding the background discussion about the theorem, its applications and significance and/or reducing the level of detail and length of the proof). In terms of weight, a proof is certainly directly relevant to the article and if it is much shorter and simpler than the original proof, it is perfectly fine to include such a simpler proof or its outline. In fact this is what always happens in mathematics. Initial proofs of important results are subsequently simplified, clarified and rationalized and it is these simpler versions that actually make it into books and encyclopedias. Nsk92 (talk) 01:30, 21 December 2008 (UTC)

3. Please, no complete proofs here. Wikipedia is not a textbook (but Wikibooks is). Kusma (talk) 18:46, 21 December 2008 (UTC)
4. Proof summary may be OK, but the complete proof is not: there is no evidence of notability of the details: they don't seem to introduce any new ideas or tricks; at least no evidence provided. In other words, the proof is Mukadderat's dog (the closer joked so in the afd page, not me) within the article dog. Mukadderat (talk) 16:29, 23 December 2008 (UTC)
5. Support per all above. Also, if the retelling is very close to the original text, this is a copyvio. If it is detailed but far from the original text, then it is OR. Proof summary is OK, just as "Plot summary" in articles about books, as someone mentioned. Twri (talk) 22:56, 24 December 2008 (UTC)

Oppose:

1. Oppose. I feel that proofs of important mathematical results, when not exessively long, have significant encyclopedic value and may be included in the appropriate articles especially if such proofs are already written. Non-experts will skip them but for experts (understood broadly, I mean people with substantial mathematical knowledge) they can represent significant encyclopedic value. If we want Wikipedia to be read and edited by more mathematicians (and I think that we certainly do) including occasional proofs, especially when they are already written, is a good idea. It makes the entire project more attractive to such expert audiences. The real question to me if this particular proof is too long and sufficiently clearly written; this question has not been discussed yet. Nsk92 (talk) 23:29, 20 December 2008 (UTC)

Neutral:

1. I do feel that some proofs, presented at an appropriate level, have encyclopedic value and are capable of teaching something useful to the interested reader, but that others are just tedious to read and don't do anything but convince you that the theorem is true (which could be achieved more succintly by pointing to the peer-reviewed literature). See e.g. this recent blog post by Luca Trevisan on the same general subject. I'm not yet sure which side of the line this proof falls on, so I don't want to commit to keeping it or removing most of it. —David Eppstein (talk) 23:52, 20 December 2008 (UTC)
2. I think a proof (or at least sufficient detail for a mature reader to see that there is a proof here) ought to be kept in the article, but there is no reason to "follow" the Ben-Dor and Halevi article. Like any proof on Wikipedia, it can and should be improved to improve readability and understandability. (I think the Arora-Barak book has a shorter proof, for example, so it is certainly possible to make it shorter.) Shreevatsa (talk) 16:49, 23 December 2008 (UTC)

Opinions/votes, please. `'Míkka>t 22:06, 20 December 2008 (UTC)

Proposal 3: Keep the articles Permanent and Sharp-P-complete separate as they are now, and move this article to something like its original title, Sharp-P-completeness of the permanent (suggested by David Eppstein above) or maybe even Valiant's theorem, to have it as a separate article about the famous theorem. Have Computation of the permanent of a matrix merged/redirected either to the present article or to Permanent.

Moved to original title, to match the content. `'Míkka>t 01:52, 21 December 2008 (UTC)

OK, thank you! Nsk92 (talk) 01:54, 21 December 2008 (UTC)

Support:

1. Support. I explained the rationale in my oppose to proposal 1. A famous and notable mathematical result like Valiant's theorem deserves its own separate article, where its history, significance, generalizations and applications are discussed and possibly an outline of a proof or a proof is included. Nsk92 (talk) 23:39, 20 December 2008 (UTC)
2. I prefer proposal 1 (I think the algorithms also deserve an article) but this would be an acceptable alternative. —David Eppstein (talk) 23:52, 20 December 2008 (UTC)
3. While I prefer proposal 1 (mine :-), there is no harm to have 2 articles instead of 3. The page about algorithms may be spit off whenever the content grows sufficiently. So I agree it would be a resaonable trade-off. I oppose the nae "aliant's theorem, because brief google search readily shows there are other pretenents on his name. Besides, it is always good to have a descriptive title, unless the namesaked theorem name is uberfamous. `'Míkka>t 01:57, 21 December 2008 (UTC)

Oppose:

1. "Computing the permanent" : 82,000 google hits, "computation of the permanent" : 20,000 hits. Also, the article is big already and still may be expanded. no reason for merging. Mukadderat (talk) 16:29, 23 December 2008 (UTC)

I have restored the last pre-Laudak version of the present article as a more sound and sane starting point for continuing this discussion. The title "Proof of" is still misleading and is the result of AfD gaming by Laudak, but I am not going to move the title for the time being as all these redirects are already a mess. Nsk92 (talk) 01:09, 21 December 2008 (UTC)

Please assume good faith. Also, as far as I remember, Laudak kinda apologized, although with teeth clenched, and withdrew himseld from the conflict. Beating a dead horse is hardly productive. `'Míkka>t 02:05, 21 December 2008 (UTC)

OK, I see that the title has been moved back to the original and also the AfD tag that I accidentally restored had been removed. Thanks for that! I wonder if people would consider it objectionable if I added some stuff to the non-proof introductory section of the article concerning the theorem itself (such as discussion of its generalizations, applications and related results). Nsk92 (talk) 01:59, 21 December 2008 (UTC)

It was unprotected after the AfD closed, so I think we're free to make improvements without needing to get prior consensus. I think it would still be a good idea to discuss big changes such as the reorg proposed in some of these poll items but that doesn't sound like what you're talking about. —David Eppstein (talk) 02:02, 21 December 2008 (UTC)

Adding a well-referenced content is independent of any poll. Whatever restructuring happens after the poll, your addition will survive somewhere. `'Míkka>t 02:05, 21 December 2008 (UTC)

OK, thanks. I will not be touching the controversial proof section at all. Nsk92 (talk) 02:07, 21 December 2008 (UTC)

Please stop this nonsense: This is a very useful article, and this discussion is ridiculous. Please do not delete it. Please do not modify it. Just read it and appreciate it.Likebox (talk) 02:53, 21 December 2008 (UTC)

That something is useful is not a reason to have it in Wikipedia. For example, the New York city phonebook is very useful, but we do not have a copy of it in Wikipedia. The question is: what is the best way to structure encyclopedia articles about the sharp-P-completeness of the permanent problem, and how much content should these have. Kusma (talk) 18:46, 21 December 2008 (UTC)

Yeah, sure. Nicht finregpoken, zo relaxen und enjoy the blinkenlights. `'Míkka>t 20:42, 21 December 2008 (UTC)

As someone in the afd rightly mentioned, some people are insufficiently familiar with English language, so it is difficult to guess whether Likebox is ironic (the part "just readt it" suggests so) or it is his true suggestion. Please restate it clearly, if you want it discussed seriously in a wider community, which may also include which lack the sense of humor or language, but still decent contributors to wikipedia. Mukadderat (talk) 16:29, 23 December 2008 (UTC)

Change the title

I'd like to propose the article's title be changed to Valiant's theorem. This could be understood when the tilte is read from outside this article, say in a list of search results or a link from the RfD page. As it stands now, "Permanent is sharp-P-complete" sounds as an alien title and doesn't make any sense to anybody who doesn't know that Permanent and #P-complete are mathematical terms.Diego (talk) 11:49, 22 December 2008 (UTC)

In principle I am mildly simpathetic to this suggestion. However, Mikka pointed out above that Valiant has several well-known theorems, this being just one of them, so, as he put it, there may be other "pretenders to the name". We actually do already have an article Valiant-Vazirani theorem. The current title is fairly short and descriptive, which is rarely possible with the statement of a theorem (usually they are too long). Perhaps this is something that could be solved using redirects and disambig notices which would take care of likely search terms. Nsk92 (talk) 13:29, 22 December 2008 (UTC)

Maybe something like Valiant's theorem on #P-completeness of the permanent or Valiant's theorem (Permanent is #P-complete) or Permanent is #P-complete (Valiant's theorem), with a few redirects for search purposes? Nsk92 (talk) 14:27, 22 December 2008 (UTC)

Dunno. Wikipedia shouldn’t be a normative source of names for theorems. While I immediately know which theorem is meant when somebody says “Valiant–Vazirani”, my reaction to “Valiant’s theorem” would probably be “Which one?” (but the odds are on the permanent result). That’s an argument in favour of the current title. On the other hand, the results might just as well be seen as a claim about counting the number of perfect matchings (rather than computing the permanent), so there are reasons for wanting to avoid mentioning the permanent in the article title. A quick Google scholar search turns up, for example: “Valiant’s theorem states that counting perfect matchings in bipartite graphs is #P-complete.” Via the Ising model (and because of the obvious link to the P-easy decision problem of finding a perfect matching), this permanent-free way of viewing the result may be at least as important and notable. If we call it Valiant’s theorem we would avoid taking sides. (But Valiant’s original paper is explicitly about the permanent in the title, so I think we should favour the permanent.) Thore Husfeldt (talk) 15:53, 22 December 2008 (UTC)

How about The Complexity of Computing the Permanent (per Leslie G. Valiant. "The Complexity of Computing the Permanent". Theoretical Computer Science.) or Valiant's theorem and The Complexity of Computing the Permanent? (as per Christos H. Papadimitriou. Computational Complexity.) Diego (talk) 16:18, 22 December 2008 (UTC)

We’re going in circles now. The complexity of computing the permanent is a huge topic, and belongs to the fledgling article Computation of the permanent of a matrix. Valiant himself has at least two major conceptual contributions to it, one is the topic of the current article, another is the class VPN. Arguably, his recent work on holographic algorithms belongs there as well. I’ve left some pointers at Talk:Computation of the permanent of a matrix. To me it seems to be a good idea to get that page, and Permanent into much better shape, including a section containing three meaty paragraphs about the topic of this article, before we expand those three paragraphs into so much material that it needs its own article. Thore Husfeldt (talk) 16:38, 22 December 2008 (UTC)

Ok, you're clearly more knowledgeable about the subject, and I don't know anything about this theorem. I'm only trying to protect the layman of a title like "Permanent is sharp-P-complete", which will freak out everybody but some specialists when it inevitably leaks to public areas such as article lists. Remember that "titles must be for a general audience over specialists" (see the relevant bits in the manual of style). Diego (talk) 17:30, 22 December 2008 (UTC)

You will never outsmart a layman :-) Looking at "Valiant's theorem", he will just as well say "Duh, WTH is Valiant?" . IMO a descriptive title, if it is brief, always beats name calling. `'Míkka>t 02:09, 23 December 2008 (UTC)

There aren't many times a theorem is so succinct and clearly stated that it can actually be the name of a paper or an article. When it does happen, I see nothing wrong with availing ourselves of it. While the thought that there will be a mass of laymen just puzzling over this title is amusing, the reality is many article titles on Wikipedia (not having anything to do with mathematics or computer science) appear arcane to a great deal many people. I expect most people will just ignore it; I hardly think this is an issue. Valiant's theorem would seem an ok solution, but just like Gromov's theorem, it's hardly unambiguous (at least now it's serving as a disambiguation page, despite the fact that I have yet to meet a single mathematician who refers to one of the listed results as "Gromov's theorem" without qualification).

By the way, the poll above doesn't list the obvious choice. Just keep things as they are. The stuff on the theorem here, at this name (the current name isn't an option in any of the poll choices). The stuff on computation at the computation article. Summaries of these articles at the permanent article. People that want to debate how much detail is too much detail for the proof can duke it out here. --C S (talk) 06:15, 23 December 2008 (UTC)

In fact "Proposal 1" is to keep things "as they are". The reason I suggested the redlinked name is that in wikipedia the article titles are nominal phrases, unless it is a title of something else. `'Míkka>t 16:05, 23 December 2008 (UTC)

A google search in web, books & scholar for "Valiant theorem" and "Valiant's theorem" shows that (a) there are several Valiant's theorems (b) the share of hits for the permanent case is not dominating (c) the total number of hits is itself hardly overwhelming. Therefore IMHO use this as title of append to the title is not solidly justified. What is more, I was thinking to create a disambig page for the phrase, but found no evidence that the phrase is used out of context to uniquely mean something in specalized but reasonably broad circles. Twri (talk) 23:10, 24 December 2008 (UTC)

Another reason to change the name is that permanent is not in #P! It's GapP-complete. Aram.harrow (talk) 18:53, 30 September 2013 (UTC)

This is a very good reason to change the name. I don't like the "Valiant's theorem" proposals above, and I also find convincing the arguments that the current title is not just erroneous but also too technical. How about something like Hardness of the permanent? —David Eppstein (talk) 20:57, 30 September 2013 (UTC)

An even better solution would be to merge this article into Computing the permanent (and possibly rename it to Complexity of the permanent). In the meantime I also prefer Hardness of the permanent over "Valiant's theorem" (and both over the current title). ylloh (talk) 10:34, 2 October 2013 (UTC)

Zero-One permanent

I don't know if anyone actually read the proof in this article :), but much of its effort seems to be in proving not just that computing permanents is #P-complete in general, but that specifically computing permanents of matrices with 0-1 entries is #P-complete as well. The title/discussion should probably take this into account. Shreevatsa (talk) 19:44, 23 December 2008 (UTC)

There is nothing unusual when a computational complexity proof actually holds for a subproblem, so there is no reason to change the article title. By the way, this point brings me an exercise question: it is trivial to see that permanent of a 0,3-matrix is also #P-complete: just multiply all entries by 3. But what about the permament of, say, +1/-1-matrix? Answer: Yes, but is it published anywhere? `'Míkka>t 00:38, 24 December 2008 (UTC)

Somewhat coincidentally, I was looking at just that :-) In the Arora-Barak book chapter they say "We start by reducing to the case that all edges have weights in {±1}": their construction is to start from an arbitrary permanent, and replace an edge (u,v) of weight k with k paths of the form u-w-v for different w. So I guess that counts as published. Shreevatsa (talk) 01:03, 24 December 2008 (UTC)

But this still leaves non-edges in, so it’s not the permanent of a {−1,1}-matrix, but only {−1,0,1}-matrix. I’d be actually interested to know if there is a reduction of general integer permanent to {−1,1}-permanent preserving the value of the permanent (or rather, changing it in a predictable, polynomial-time computable way, such as multiplying it by 2ⁿ; exact preservation is impossible as a permanent of a {−1,1}-matrix is always even). Of course, one can reduce integer permanent to {−1,1}-permanent by replacing the 0s with a large Q, and then reducing the positive entries to 1s as before. But this preserves the permanent only up to a multiple of Q that is hard to compute.—Emil J. 09:13, 30 June 2023 (UTC)

The usual definition of #P-completeness allows Turing reductions. So do the reduction with two different large Q's and use the result to compute the multiplier. —David Eppstein (talk) 18:21, 30 June 2023 (UTC)

I’m not talking about #P-completeness, but about a stronger notion of reduction. In particular, what I asked for above would imply (in fact, it is equivalent) that the language {(A,s) : Perm(A) = s} for {−1,1}-matrices is C₌-complete, which the usual Valiant’s reduction does not give. (For context, I was lead to this question by [3], which poses a similar problem for {0,1}-matrices).

I don’t understand what you mean with two different Q’s: the multiplier depends on Q as well, of course. And anyway, I would need to compute the multiplier in polynomial time, whereas you reduce it to the computation of two permanents, which is no better than just computing it directly from the definition.—Emil J. 10:36, 10 July 2023 (UTC)

Careful now! It’s early, and I haven’t had my coffee yet, but I don’t think +1/-1 permanent is #P-complete. For a boring reason: it’s not in #P. (It’s in GapP, which is the closure of #P under subtraction.) It’s #P-hard, though. Thore Husfeldt (talk) 07:33, 24 December 2008 (UTC)

At least for ±1, the reduction in this article to a nonnegative matrix works. (Actually, it seems to me that it will work for any arbitrary integer matrix: µ≤(input size), so Q has a polynomial number of bits as well.) Shreevatsa (talk) 15:55, 24 December 2008 (UTC)

Oops. As above, there is a polynomial-time reduction from arbitrary permanent to 01-permanent, but although the latter is in #P, the former is not, because it is a Turing reduction and requires subtraction in order to compute it. (Right?) Shreevatsa (talk) 01:50, 25 December 2008 (UTC)

Well, the reduction is used to show hardness (in this case, #P-hardness). Membership in #P isn’t proved by reduction, but by modelling the computation as the number of accepting paths of a Turing machine. An easy way to see that Permanent is not in #P is to observe that the permanent of the 1x1-matrix, (-1), is negative, and thus not equal to the number of accepting paths of anything. (Among other things, membership in #P requires the output to be a nonnegative integer.) By the way, these ruminations may be a strong argument in favour of changing the title to #P-hardness of the permanent (since the permanent isn’t actually #P-complete.) Thore Husfeldt (talk) 14:31, 25 December 2008 (UTC)

Right, I understand. We have Turing reductions $\#SAT\leq _{T}Perm\leq _{T}\pm 1Perm\leq _{T}01$-Perm, but although the first and last are in #P, the intermediate ones are not. (Because #P is not closed under subtraction, let alone Turing reductions.) Shreevatsa (talk) 23:49, 25 December 2008 (UTC)

Hardness, not completeness

Above, I already mentioned that the permanent (without any qualifications) is not #P-complete. It doesn’t even belong to #P. So I think the article title is a problem. Now, we even had the article categorised as “other complete problems”, but the permanent isn’t complete for anything – well, actually it is, but in a completely different framework (Valiant’s algebraic class VNP). I propose this article be renamed to either #P-completeness of 01-permanent or (my preference) #P-hardness of the permanent, mutatis mutandis. Thore Husfeldt (talk) 08:41, 27 December 2008 (UTC)

I agree there is a problem. "#P-hardness of the permanent" sounds better, but "#P-hardness of 01-permanent" (or "#P-completeness of 01-permanent") is a more accurate description of the article's contents. (And of Valiant's theorem.) Shreevatsa (talk) 15:56, 27 December 2008 (UTC)

So why hasn't anyone gone ahead and changed the title as suggested? The current title is indeed confusing and misleading. Took (talk) 12:34, 11 December 2014 (UTC)

Copy edit

I've completed a copy edit on the page. Mostly, this consisted of an attempt to remove the conversational tone used throughout the page (in violation of the Manual of Style (mathematics). I'd encourage contributors to this page to read MOS:MATH before editing. The page could still use revision by mathematically-inclined folks to ensure compliance with MOS:MATH. Speaking as a non-mathematician, I found the page to read as if it had been copied from an advanced mathematics text; it would be improved if the "Significance" section were rewritten so that it might be retitled "Why non-mathematicians should care about this article." After all, Wikipedia is not a textbook. Macwhiz (talk) 19:03, 26 August 2010 (UTC)

Thanks for your improvements. I just rewrote the significance section in an attempt to clarify the significance to non-expert readers; I hope it too will be seen as an improvement. —David Eppstein (talk) 20:05, 26 August 2010 (UTC)

Yes, that helps quite a bit. I still think the rest of the article treads very close to the line of being a textbook rather than an encyclopedia article, but I'm a language sort of guy; I'll leave the question to the math folks. Macwhiz (talk) 02:34, 27 August 2010 (UTC)

I've been MIA a few years, but I can confirm the article originated as an assignment in a 500-level complexity theory course. I'm pleased to see the community rightly determined the result to be worthy of inclusion, and has cleaned the article up quite a bit from our original presentation. ForgeGod (talk) 19:08, 17 May 2014 (UTC)

I've reworked the lead section to make it compliant with Wikipedia:Manual_of_Style/Mathematics#Article_introduction and WP:MOSINTRO. For a general reader, it's more important to stablish that this is a result in mathematics and "describe, define, and give context to the subject of the article, to establish why it is interesting or useful, and to summarize the most important points", in that order, rather than starting with a summary of the theorem itself. Diego (talk) 11:30, 12 December 2014 (UTC)