243:) 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.
287:
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
91:
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
206:
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
251:
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
275:, 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.
92:
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
39:
268:
that return good approximations to some #P-complete problems with high probability. This is one of the demonstrations of the power of probabilistic algorithms.
489:
272:
157:
88:
851:
458:
482:
69:
54:
108:
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.
886:
475:
674:
867:
856:
265:
248:
153:
128:
810:
191:
93:
805:
800:
183:
104:
problems. A polynomial-time algorithm for solving a #P-complete problem, if it existed, would solve the
203:
795:
305:
244:
187:
105:
361:
815:
454:
779:
669:
601:
591:
498:
426:
393:
353:
320:
179:
142:
135:
84:
57:. The problems in this complexity class are defined by having the following two properties:
50:
96:, a more specific type of reduction that preserves the exact number of solutions, are used.
65:, the class of problems that can be defined as counting the number of accepting paths of a
774:
764:
721:
711:
694:
684:
642:
637:
632:
616:
596:
574:
569:
564:
552:
547:
542:
537:
344:
228:
224:
216:
146:
66:
769:
657:
579:
532:
284:
280:
253:
240:
220:
164:
120:
How many different variable assignments will satisfy a given general boolean formula? (
880:
431:
414:
398:
381:
365:
339:
256:
which also defined the class #P and the #P-complete problems for the first time.
647:
557:
276:
101:
35:
17:
759:
584:
247:
is easy in contrast to counting the number of topological sortings. A single
754:
121:
415:"Random Generation of Combinatorial Structures from a Uniform Distribution"
749:
744:
689:
512:
202:
as well. As a non-example, consider the case of counting solutions to a
739:
357:
49:
problems (pronounced "sharp P complete" or "number P complete") form a
699:
212:
208:
199:
80:
62:
846:
841:
716:
467:
324:
836:
831:
652:
664:
522:
471:
679:
611:
606:
527:
517:
413:
Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986).
134:
How many different variable assignments will satisfy a given
127:
How many different variable assignments will satisfy a given
306:"The Complexity of Enumeration and Reliability Problems"
273:
fully polynomial-time randomized approximation scheme
83:-hard, meaning that every other problem in #P has a
824:
788:
732:
625:
505:
219:. This would be surprising, as it would imply that
288:that algorithm can be used to construct an FPRAS.
156:of a given matrix whose entries are 0 or 1? (See
198:These are all necessarily members of the class
239:Some #P-complete problems correspond to easy (
483:
100:#P-complete problems are at least as hard as
8:
382:"The Complexity of Computing the Permanent"
490:
476:
468:
116:Examples of #P-complete problems include:
430:
397:
235:Easy problems with hard counting versions
171:colors are there for a particular graph
296:
186:, or, equivalently, how many different
342:(1991). "Counting linear extensions".
30:The correct title of this article is
7:
211:, but cannot be #P-complete unless
304:Valiant, Leslie G. (August 1979).
89:polynomial-time counting reduction
25:
852:Probabilistically checkable proof
271:Many #P-complete problems have a
70:non-deterministic Turing machine
158:#P-completeness of 01-permanent
55:computational complexity theory
1:
432:10.1016/0304-3975(86)90174-x
419:Theoretical Computer Science
399:10.1016/0304-3975(79)90044-6
386:Theoretical Computer Science
449:Vazirani, Vijay V. (2003).
903:
868:List of complexity classes
380:Leslie G. Valiant (1979).
34:. The substitution of the
29:
865:
313:SIAM Journal on Computing
152:What is the value of the
857:Interactive proof system
451:Approximation Algorithms
392:(2). Elsevier: 189–201.
266:probabilistic algorithms
338:Brightwell, Graham R.;
94:parsimonious reductions
811:Arithmetical hierarchy
192:directed acyclic graph
190:are there for a given
182:are there for a given
145:are there for a given
40:technical restrictions
806:Grzegorczyk hierarchy
801:Exponential hierarchy
733:Considered infeasible
425:. Elsevier: 169–188.
245:Topologically sorting
188:topological orderings
184:partially ordered set
796:Polynomial hierarchy
626:Suspected infeasible
453:. Berlin: Springer.
825:Families of classes
506:Considered feasible
178:How many different
106:P versus NP problem
887:Complexity classes
499:Complexity classes
358:10.1007/BF00383444
61:The problem is in
874:
873:
816:Boolean hierarchy
789:Class hierarchies
180:linear extensions
143:perfect matchings
16:(Redirected from
894:
492:
485:
478:
469:
464:
437:
436:
434:
410:
404:
403:
401:
377:
371:
369:
335:
329:
328:
310:
301:
249:perfect matching
204:1-satisfiability
136:2-satisfiability
85:Turing reduction
51:complexity class
27:Complexity class
21:
18:Sharp P complete
902:
901:
897:
896:
895:
893:
892:
891:
877:
876:
875:
870:
861:
820:
784:
728:
722:PSPACE-complete
621:
501:
496:
461:
448:
445:
443:Further reading
440:
412:
411:
407:
379:
378:
374:
337:
336:
332:
325:10.1137/0208032
308:
303:
302:
298:
294:
262:
241:polynomial time
237:
165:graph colorings
147:bipartite graph
114:
79:The problem is
67:polynomial-time
43:
28:
23:
22:
15:
12:
11:
5:
900:
898:
890:
889:
879:
878:
872:
871:
866:
863:
862:
860:
859:
854:
849:
844:
839:
834:
828:
826:
822:
821:
819:
818:
813:
808:
803:
798:
792:
790:
786:
785:
783:
782:
777:
772:
767:
762:
757:
752:
747:
742:
736:
734:
730:
729:
727:
726:
725:
724:
714:
709:
708:
707:
697:
692:
687:
682:
677:
672:
667:
662:
661:
660:
658:co-NP-complete
655:
650:
645:
635:
629:
627:
623:
622:
620:
619:
614:
609:
604:
599:
594:
589:
588:
587:
577:
572:
567:
562:
561:
560:
550:
545:
540:
535:
530:
525:
520:
515:
509:
507:
503:
502:
497:
495:
494:
487:
480:
472:
466:
465:
459:
444:
441:
439:
438:
405:
372:
352:(3): 225–242.
340:Winkler, Peter
330:
319:(3): 410–421.
295:
293:
290:
261:
258:
254:Leslie Valiant
236:
233:
196:
195:
176:
161:
150:
139:
132:
125:
113:
110:
98:
97:
74:
73:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
899:
888:
885:
884:
882:
869:
864:
858:
855:
853:
850:
848:
845:
843:
840:
838:
835:
833:
830:
829:
827:
823:
817:
814:
812:
809:
807:
804:
802:
799:
797:
794:
793:
791:
787:
781:
778:
776:
773:
771:
768:
766:
763:
761:
758:
756:
753:
751:
748:
746:
743:
741:
738:
737:
735:
731:
723:
720:
719:
718:
715:
713:
710:
706:
703:
702:
701:
698:
696:
693:
691:
688:
686:
683:
681:
678:
676:
673:
671:
668:
666:
663:
659:
656:
654:
651:
649:
646:
644:
641:
640:
639:
636:
634:
631:
630:
628:
624:
618:
615:
613:
610:
608:
605:
603:
600:
598:
595:
593:
590:
586:
583:
582:
581:
578:
576:
573:
571:
568:
566:
563:
559:
556:
555:
554:
551:
549:
546:
544:
541:
539:
536:
534:
531:
529:
526:
524:
521:
519:
516:
514:
511:
510:
508:
504:
500:
493:
488:
486:
481:
479:
474:
473:
470:
462:
460:3-540-65367-8
456:
452:
447:
446:
442:
433:
428:
424:
420:
416:
409:
406:
400:
395:
391:
387:
383:
376:
373:
367:
363:
359:
355:
351:
347:
346:
341:
334:
331:
326:
322:
318:
314:
307:
300:
297:
291:
289:
286:
282:
278:
274:
269:
267:
260:Approximation
259:
257:
255:
250:
246:
242:
234:
232:
230:
226:
222:
218:
214:
210:
205:
201:
193:
189:
185:
181:
177:
174:
170:
166:
162:
159:
155:
151:
148:
144:
140:
137:
133:
130:
126:
123:
119:
118:
117:
111:
109:
107:
103:
95:
90:
86:
82:
78:
77:
76:
71:
68:
64:
60:
59:
58:
56:
52:
48:
41:
37:
33:
19:
704:
450:
422:
418:
408:
389:
385:
375:
349:
343:
333:
316:
312:
299:
270:
263:
238:
197:
172:
168:
115:
99:
75:
46:
44:
31:
705:#P-complete
643:NP-complete
558:NL-complete
102:NP-complete
47:#P-complete
32:#P-complete
760:ELEMENTARY
585:P-complete
292:References
264:There are
38:is due to
755:2-EXPTIME
366:119697949
163:How many
154:permanent
141:How many
881:Category
750:EXPSPACE
745:NEXPTIME
513:DLOGTIME
285:Vazirani
138:problem?
131:formula?
112:Examples
740:EXPTIME
648:NP-hard
281:Valiant
847:NSPACE
842:DSPACE
717:PSPACE
457:
364:
283:, and
277:Jerrum
167:using
837:NTIME
832:DTIME
653:co-NP
362:S2CID
345:Order
309:(PDF)
665:TFNP
455:ISBN
122:#SAT
45:The
780:ALL
680:QMA
670:FNP
612:APX
607:BQP
602:BPP
592:ZPP
523:ACC
427:doi
394:doi
354:doi
321:doi
129:DNF
87:or
53:in
883::
775:RE
765:PR
712:IP
700:#P
695:PP
690:⊕P
685:PH
675:AM
638:NP
633:UP
617:FP
597:RP
575:CC
570:SC
565:NC
553:NL
548:FL
543:RL
538:SL
528:TC
518:AC
423:43
421:.
417:.
388:.
384:.
360:.
348:.
315:.
311:.
279:,
231:.
229:PH
225:NP
217:FP
213:#P
209:#P
200:#P
160:.)
81:#P
63:#P
770:R
580:P
533:L
491:e
484:t
477:v
463:.
435:.
429::
402:.
396::
390:8
370:.
368:.
356::
350:8
327:.
323::
317:8
227:=
223:=
221:P
215:=
194:?
175:?
173:G
169:k
149:?
124:)
72:.
42:.
36:#
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.