About: ♯P-completeness of 01-permanent

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: ♯P-completeness of 01-permanent Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon

http://dbpedia.demo.openlinksw.com/c/6mpx38vT6N

The #P-completeness of 01-permanent, sometimes known as Valiant's theorem, is a mathematical proof about the permanent of matrices, considered a seminal result in computational complexity theory. In a 1979 scholarly paper, Leslie Valiant proved that the computational problem of computing the permanent of a matrix is #P-hard, even if the matrix is restricted to have entries that are all 0 or 1. In this restricted case, computing the permanent is even #P-complete, because it corresponds to the #P problem of counting the number of permutation matrices one can get by changing ones into zeroes.

Attributes	Values
rdfs:label	♯P-completeness of 01-permanent (en)
rdfs:comment	The #P-completeness of 01-permanent, sometimes known as Valiant's theorem, is a mathematical proof about the permanent of matrices, considered a seminal result in computational complexity theory. In a 1979 scholarly paper, Leslie Valiant proved that the computational problem of computing the permanent of a matrix is #P-hard, even if the matrix is restricted to have entries that are all 0 or 1. In this restricted case, computing the permanent is even #P-complete, because it corresponds to the #P problem of counting the number of permutation matrices one can get by changing ones into zeroes. (en)
foaf:depiction
dcterms:subject	Article proofs Combinatorics Computational problems
Wikipage page ID	20768719 (xsd:integer)
Wikipage revision ID	1062322208 (xsd:integer)
Link from a Wikipage to another Wikipage	Scott Aaronson Cook's theorem Binary numeral system Perfect matching Article proofs Matrix (mathematics) Modular arithmetic NC (complexity) Conjunctive normal form Leslie Valiant Biadjacency matrix Complexity class Computational complexity theory Computational problem Function problem Hopcroft–Karp algorithm Ketan Mulmuley Parallel algorithm Permanent (mathematics) Scholarly paper Sharp-P Polynomial-time reduction Adjacency matrix Combinatorics Mathematical proof Immanant of a matrix Toda's theorem Computational problems Bipartite graph 3SAT Boolean satisfiability problem Polynomial hierarchy Sharp-SAT Sharp-P-complete Polynomial-time counting reduction Turing reduction Computation of the permanent of a matrix
sameAs	♯P-completeness of 01-permanent ♯P-completeness of 01-permanent
dbp:wikiPageUsesTemplate	dbt:Anchor dbt:Correct_title dbt:Cquote dbt:Harvtxt dbt:Reflist dbt:Short_description dbt:MOS
thumbnail	wiki-commons:Special:FilePath/Permanent-Nonneg2Powers.png?width=300
reason	hash (en)
title	#P-completeness of 01-permanent (en)
has abstract	The #P-completeness of 01-permanent, sometimes known as Valiant's theorem, is a mathematical proof about the permanent of matrices, considered a seminal result in computational complexity theory. In a 1979 scholarly paper, Leslie Valiant proved that the computational problem of computing the permanent of a matrix is #P-hard, even if the matrix is restricted to have entries that are all 0 or 1. In this restricted case, computing the permanent is even #P-complete, because it corresponds to the #P problem of counting the number of permutation matrices one can get by changing ones into zeroes. Valiant's 1979 paper also introduced #P as a complexity class. Valiant's definition of completeness, and his proof of completeness of 01-permanent, both used polynomial-time Turing reductions. In this kind of reduction, a single hard instance of some other problem in #P is reduced to computing the permanent of a sequence of multiple graphs, each of which could potentially depend on the results of previous permanent computations. A later simplification by showed that it is possible to use a weaker notion of reduction, a polynomial-time counting reduction, that translates the other problem into a single instance of the permanent problem. (en)
prov:wasDerivedFrom	wikipedia-en:♯P-completeness_of_01-permanent?oldid=1062322208&ns=0
page length (characters) of wiki page	25100 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:♯P-completeness_of_01-permanent
is Link from a Wikipage to another Wikipage of	Permanent is sharp-P-complete ♯P-complete Sharp-P-completeness of 01-permanent Proof that permanent is sharp-P-complete Valiant's theorem Computing permanent is sharp-P-complete
is Wikipage redirect of	Permanent is sharp-P-complete Sharp-P-completeness of 01-permanent Proof that permanent is sharp-P-complete Valiant's theorem Computing permanent is sharp-P-complete
is foaf:primaryTopic of	wikipedia-en:♯P-completeness_of_01-permanent

Faceted Search & Find service v1.17_git147 as of Sep 06 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3332 as of Dec 5 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 71 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software