Find link

language:

Find link is a tool written by Edward Betts.

searching for Computing the permanent 13 found (22 total)

♯P-completeness of 01-permanent (4,216 words) [view diff] exact match in snippet view article find links to article

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

♯P (944 words) [view diff] case mismatch in snippet view article find links to article

ISBN 978-0-521-42426-4. Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science. 8 (2). Elsevier: 189–201. doi:10

♯P-complete (849 words) [view diff] case mismatch in snippet view article find links to article

S2CID 119697949.. Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science. 8 (2). Elsevier: 189–201. doi:10

Perfect matching (949 words) [view diff] exact match in snippet view article find links to article

matchings, even in bipartite graphs, is #P-complete. This is because computing the permanent of an arbitrary 0–1 matrix (another #P-complete problem) is the

Random self-reducibility (911 words) [view diff] exact match in snippet view article find links to article

residuosity problem, the RSA inversion problem, and the problem of computing the permanent of a matrix are each random self-reducible problems. Theorem: Given

Matching (graph theory) (2,938 words) [view diff] exact match in snippet view article

to count perfect matchings, even in bipartite graphs, because computing the permanent of an arbitrary 0–1 matrix (another #P-complete problem) is the

Quantum algorithm (4,560 words) [view diff] exact match in snippet view article find links to article

Solving this problem with a classical computer algorithm requires computing the permanent of the unitary transform matrix, which may take a prohibitively

Conductance (graph theory) (1,407 words) [view diff] exact match in snippet view article

turn gives rise to the polynomial-time approximation scheme for computing the permanent. For undirected d-regular graphs G {\displaystyle G} without edge

Vertex cycle cover (411 words) [view diff] exact match in snippet view article find links to article

adjacency matrix. This fact is used in a simplified proof showing that computing the permanent is #P-complete. The problems of finding a vertex disjoint and edge

Polynomial-time counting reduction (753 words) [view diff] exact match in snippet view article find links to article

ISBN 0-89871-479-6, MR 1827376 Valiant, L. G. (1979), "The complexity of computing the permanent", Theoretical Computer Science, 8 (2): 189–201, doi:10.1016/0304-3975(79)90044-6

Sharp-SAT (1,495 words) [view diff] exact match in snippet view article find links to article

commutative semirings. Valiant, L.G. (1979). "The complexity of computing the permanent". Theoretical Computer Science. 8 (2): 189–201. doi:10.1016/0304-3975(79)90044-6

Hafnian (2,263 words) [view diff] exact match in snippet view article find links to article

Computing the hafnian of a (0,1)-matrix is #P-complete, because computing the permanent of a (0,1)-matrix is #P-complete. The hafnian of a 2 n × 2 n {\displaystyle

Rook polynomial (3,630 words) [view diff] exact match in snippet view article find links to article

number of ways to place n rooks on the board is equivalent to computing the permanent of a 0–1 matrix. A precursor to the rook polynomial is the classic