fbpx
Wikipedia

♯P-complete

May 02, 2024

The correct title of this article is #P-complete. The substitution of the # is due to technical restrictions.

The #P-complete problems (pronounced "sharp P complete" or "number P complete") form a complexity class in computational complexity theory. The problems in this complexity class are defined by having the following two properties:

  • The problem is #P-hard, meaning that every other problem in #P has a Turing reduction or polynomial-time counting reduction to it. A counting reduction is a pair of polynomial-time transformations from inputs of the other problem to inputs of the given problem and from outputs of the given problem to outputs of the other problem, allowing the other problem to be solved using any subroutine for the given problem. A Turing reduction is an algorithm for the other problem that makes a polynomial number of calls to a subroutine for the given problem and, outside of those calls, uses polynomial time. In some cases parsimonious reductions, a more specific type of reduction that preserves the exact number of solutions, are used.

#P-complete problems are at least as hard as NP-complete problems.[1] A polynomial-time algorithm for solving a #P-complete problem, if it existed, would solve the P versus NP problem by implying that P and NP are equal. No such algorithm is known, nor is a proof known that such an algorithm does not exist.

Examples edit

Examples of #P-complete problems include:

These are all necessarily members of the class #P as well. As a non-example, consider the case of counting solutions to a 1-satisfiability problem: a series of variables that are each individually constrained, but have no relationships with each other. The solutions can be efficiently counted, by multiplying the number of options for each variable in isolation. Thus, this problem is in #P, but cannot be #P-complete unless #P=FP. This would be surprising, as it would imply that P=NP=PH.

Easy problems with hard counting versions edit

Some #P-complete problems correspond to easy (polynomial time) problems. Determining the satisfiability of a boolean formula in DNF is easy: such a formula is satisfiable if and only if it contains a satisfiable conjunction (one that does not contain a variable and its negation), whereas counting the number of satisfying assignments is #P-complete. Furthermore, deciding 2-satisfiability is easy compared to counting the number of satisfying assignments. Topologically sorting is easy in contrast to counting the number of topological sortings. A single perfect matching can be found in polynomial time, but counting all perfect matchings is #P-complete. The perfect matching counting problem was the first counting problem corresponding to an easy P problem shown to be #P-complete, in a 1979 paper by Leslie Valiant which also defined the class #P and the #P-complete problems for the first time.[3]

Approximation edit

There are probabilistic algorithms that return good approximations to some #P-complete problems with high probability. This is one of the demonstrations of the power of probabilistic algorithms.

Many #P-complete problems have a fully polynomial-time randomized approximation scheme, or "FPRAS," which, informally, will produce with high probability an approximation to an arbitrary degree of accuracy, in time that is polynomial with respect to both the size of the problem and the degree of accuracy required. Jerrum, Valiant, and Vazirani showed that every #P-complete problem either has an FPRAS, or is essentially impossible to approximate; if there is any polynomial-time algorithm which consistently produces an approximation of a #P-complete problem which is within a polynomial ratio in the size of the input of the exact answer, then that algorithm can be used to construct an FPRAS.[4]

References edit

  1. ^ Valiant, Leslie G. (August 1979). "The Complexity of Enumeration and Reliability Problems" (PDF). SIAM Journal on Computing. 8 (3): 410–421. doi:10.1137/0208032.
  2. ^ Brightwell, Graham R.; Winkler, Peter (1991). "Counting linear extensions". Order. 8 (3): 225–242. doi:10.1007/BF00383444. S2CID 119697949..
  3. ^ Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science. 8 (2). Elsevier: 189–201. doi:10.1016/0304-3975(79)90044-6.
  4. ^ Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986). "Random Generation of Combinatorial Structures from a Uniform Distribution". Theoretical Computer Science. 43. Elsevier: 169–188. doi:10.1016/0304-3975(86)90174-x.

Further reading edit

  • Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3-540-65367-8.

May 02, 2024
complete, correct, title, this, article, complete, substitution, technical, restrictions, complete, problems, pronounced, sharp, complete, number, complete, form, complexity, class, computational, complexity, theory, problems, this, complexity, class, defined,. The correct title of this article is P complete The substitution of the is due to technical restrictions The P complete problems pronounced sharp P complete or number P complete form a complexity class in computational complexity theory The problems in this complexity class are defined by having the following two properties The problem is in P the class of problems that can be defined as counting the number of accepting paths of a polynomial time non deterministic Turing machine The problem is P hard meaning that every other problem in P has a Turing reduction or polynomial time counting reduction to it A counting reduction is a pair of polynomial time transformations from inputs of the other problem to inputs of the given problem and from outputs of the given problem to outputs of the other problem allowing the other problem to be solved using any subroutine for the given problem A Turing reduction is an algorithm for the other problem that makes a polynomial number of calls to a subroutine for the given problem and outside of those calls uses polynomial time In some cases parsimonious reductions a more specific type of reduction that preserves the exact number of solutions are used P complete problems are at least as hard as NP complete problems 1 A polynomial time algorithm for solving a P complete problem if it existed would solve the P versus NP problem by implying that P and NP are equal No such algorithm is known nor is a proof known that such an algorithm does not exist Contents 1 Examples 2 Easy problems with hard counting versions 3 Approximation 4 References 5 Further readingExamples editExamples of P complete problems include How many different variable assignments will satisfy a given general boolean formula SAT How many different variable assignments will satisfy a given DNF formula How many different variable assignments will satisfy a given 2 satisfiability problem How many perfect matchings are there for a given bipartite graph What is the value of the permanent of a given matrix whose entries are 0 or 1 See P completeness of 01 permanent How many graph colorings using k colors are there for a particular graph G How many different linear extensions are there for a given partially ordered set or equivalently how many different topological orderings are there for a given directed acyclic graph 2 These are all necessarily members of the class P as well As a non example consider the case of counting solutions to a 1 satisfiability problem a series of variables that are each individually constrained but have no relationships with each other The solutions can be efficiently counted by multiplying the number of options for each variable in isolation Thus this problem is in P but cannot be P complete unless P FP This would be surprising as it would imply that P NP PH Easy problems with hard counting versions editSome P complete problems correspond to easy polynomial time problems Determining the satisfiability of a boolean formula in DNF is easy such a formula is satisfiable if and only if it contains a satisfiable conjunction one that does not contain a variable and its negation whereas counting the number of satisfying assignments is P complete Furthermore deciding 2 satisfiability is easy compared to counting the number of satisfying assignments Topologically sorting is easy in contrast to counting the number of topological sortings A single perfect matching can be found in polynomial time but counting all perfect matchings is P complete The perfect matching counting problem was the first counting problem corresponding to an easy P problem shown to be P complete in a 1979 paper by Leslie Valiant which also defined the class P and the P complete problems for the first time 3 Approximation editThere are probabilistic algorithms that return good approximations to some P complete problems with high probability This is one of the demonstrations of the power of probabilistic algorithms Many P complete problems have a fully polynomial time randomized approximation scheme or FPRAS which informally will produce with high probability an approximation to an arbitrary degree of accuracy in time that is polynomial with respect to both the size of the problem and the degree of accuracy required Jerrum Valiant and Vazirani showed that every P complete problem either has an FPRAS or is essentially impossible to approximate if there is any polynomial time algorithm which consistently produces an approximation of a P complete problem which is within a polynomial ratio in the size of the input of the exact answer then that algorithm can be used to construct an FPRAS 4 References edit Valiant Leslie G August 1979 The Complexity of Enumeration and Reliability Problems PDF SIAM Journal on Computing 8 3 410 421 doi 10 1137 0208032 Brightwell Graham R Winkler Peter 1991 Counting linear extensions Order 8 3 225 242 doi 10 1007 BF00383444 S2CID 119697949 Leslie G Valiant 1979 The Complexity of Computing the Permanent Theoretical Computer Science 8 2 Elsevier 189 201 doi 10 1016 0304 3975 79 90044 6 Mark R Jerrum Leslie G Valiant Vijay V Vazirani 1986 Random Generation of Combinatorial Structures from a Uniform Distribution Theoretical Computer Science 43 Elsevier 169 188 doi 10 1016 0304 3975 86 90174 x Further reading editVazirani Vijay V 2003 Approximation Algorithms Berlin Springer ISBN 3 540 65367 8 Retrieved from https en wikipedia org w index php title P complete amp oldid 1181169460, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.