751:. Seta Takahiro provided a reduction from 3SAT to this problem when restricted to planar directed max degree-3 graphs. The reduction provides a bijection between the solutions to an instance of 3SAT and the solutions to an instance of Hamiltonian Cycle in planar directed max degree-3 graphs. Hence the reduction is parsimonious and Hamiltonian Cycle in planar directed max degree-3 graphs is #P-complete. Consequently, the general version of Hamiltonian Cycle problem must be #P-complete as well.
762:
is an example of how parsimonious reduction could be used in showing hardness of logic puzzles. The decision version of this problem asks whether there is a solution to a given instance of the puzzle. The counting version asks for the number of distinct solutions to such a problem. The reduction from
734:
This is the counting version of Planar 3SAT. The hardness reduction from 3SAT to Planar 3SAT given by
Lichtenstein has the additional property that for every valid assignment of an instance of 3SAT, there is a unique valid assignment of the corresponding instance of Planar 3SAT, and vice versa. Hence
763:
Planar 3SAT given by
Demaine, Okamoto, Uehara and Uno also provides a bijection between the set of solutions to an instance of Planar 3SAT and the set of solutions to the corresponding instance of Shakashaka. Hence the reduction is parsimonious, and the counting version of Shakashaka is #P-complete.
725:
form. Any valid assignment of a boolean formula is a valid assignment of the corresponding 3-CNF formula, and vice versa. Hence, this reduction preserves the number of satisfying assignments, and is a parsimonious reduction. Then, #SAT and #3SAT are counting equivalents, and #3SAT is #P-complete as
525:
are used; these are parsimonious reductions whose transformation is a fixed-parameter tractable algorithm and that map bounded parameter values to bounded parameter values by a computable function.
602:
365:
336:
676:
699:
653:
630:
573:
553:
465:
445:
425:
405:
385:
307:
287:
267:
247:
224:
204:
165:
141:
117:
97:
77:
57:
502:
Specific types of parsimonious reductions may be defined by the computational complexity or other properties of the transformation algorithm. For instance, a
178:. Additionally, they are used in game complexity, as a way to design hard puzzles that have a unique solution, as many types of puzzles require.
1003:
529:
888:
848:
799:
998:
20:
528:
Polynomial-time parsimonious reductions are a special case of a more general class of reductions for counting problems, the
484:
171:
875:
520:
515:
722:
491:. Because parsimonious reductions preserve the property of having a unique solution, they are also used in
948:
32:
883:, Frontiers in Artificial Intelligence and Applications, vol. 185, IOS Press, pp. 633–654,
953:
170:
Parsimonious reductions are commonly used in computational complexity for proving the hardness of
476:
925:
895:
884:
844:
838:
795:
789:
744:
338:. If such a reduction exists, and if we have an oracle that counts the number of solutions to
917:
969:"JAIST Repository: Computational complexity and an integer programming model of Shakashaka"
815:
702:
511:
499:
where the uniqueness of the solution is an important part of the definition of the puzzle.
39:
between the respective sets of solutions of two problems. A general reduction from problem
578:
507:
492:
480:
341:
312:
24:
658:
816:"Complexity and Completeness of Finding Another Solution and Its Application to Puzzles"
681:
635:
123:
solution and vice versa. A parsimonious reduction guarantees that for every solution of
968:
820:
IEICE Transactions on
Fundamentals of Electronics, Communications and Computer Sciences
785:
748:
615:
612:
The class #P contains the counting versions of NP decision problems. Given an instance
558:
538:
450:
430:
410:
390:
370:
292:
272:
252:
232:
209:
189:
150:
126:
102:
82:
62:
42:
992:
555:
is parsimonious is to show that there is a bijection between the set of solutions to
871:
834:
945:
The
Complexities of Puzzles, Cross Sum, and their Another Solution Problems (ASP)
867:
863:
759:
929:
735:
the reduction is parsimonious, and consequently Planar #3SAT is #P-complete.
604:
which guarantees that the number of solutions to both problems is the same.
36:
387:, then we can design an algorithm that counts the number of solutions to
427:. Consequently, if counting the number of solutions to the instances of
843:, EATCS Texts in Theoretical Computer Science, Springer, p. 363,
488:
175:
496:
483:, parsimonious reductions are important for proving completeness for
921:
908:
Lichtenstein, David (May 1982). "Planar
Formulae and Their Uses".
718:
714:
35:) that preserves the number of solutions. Informally, it is a
747:
problem asks for the number of
Hamiltonian cycles in a given
608:
Examples of parsimonious reduction in proving #P-completeness
870:(2009), "Chapter 20. Model Counting", in Biere, Armin;
535:
One common technique used in proving that a reduction
684:
661:
638:
618:
581:
561:
541:
453:
433:
413:
393:
373:
344:
315:
295:
275:
255:
235:
212:
192:
153:
129:
105:
85:
65:
45:
289:
is a reduction such that the number of solutions to
506:is one in which the transformation algorithm takes
31:is a transformation from one problem to another (a
791:Computational Complexity: A Conceptual Perspective
693:
670:
647:
624:
596:
567:
547:
459:
447:is hard, then counting the number of solutions to
439:
419:
399:
379:
359:
330:
301:
281:
261:
241:
218:
198:
159:
135:
111:
91:
79:is a transformation that guarantees that whenever
71:
51:
705:below rely on the fact that #SAT is #P-complete.
510:. These are the types of reduction used to prove
794:, Cambridge University Press, pp. 203–204,
309:is equal to the number of solutions to problem
8:
678:asks for the number of solutions to problem
780:
778:
776:
495:, to show the hardness of puzzles such as
174:, for counting complexity classes such as
952:
683:
660:
637:
617:
580:
560:
540:
452:
432:
412:
392:
372:
343:
314:
294:
274:
254:
234:
211:
191:
152:
128:
104:
84:
64:
44:
16:Notion in computational complexity theory
874:; van Maaren, Hans; Walsh, Toby (eds.),
717:. One can show that any boolean formula
814:Yato, Takayuki; Seta, Takahiro (2003),
772:
504:polynomial-time parsimonious reduction
7:
530:polynomial-time counting reductions
662:
14:
713:This is the counting version of
407:, the corresponding instance of
840:Parameterized Complexity Theory
21:computational complexity theory
591:
585:
354:
348:
325:
319:
1:
575:and the set of solutions to
485:counting complexity classes
1020:
877:Handbook of Satisfiability
632:of an NP decision problem
479:are important for proving
206:be an instance of problem
1004:Combinatorial game theory
910:SIAM Journal on Computing
743:The counting version of
516:parameterized complexity
367:which is an instance of
943:Seta, Takahiro (2001).
523:parsimonious reductions
999:Reduction (complexity)
822:, E86-A (5): 1052–1060
695:
672:
649:
626:
598:
569:
549:
467:must be hard as well.
461:
441:
421:
401:
381:
361:
332:
303:
283:
263:
243:
228:Parsimonious reduction
220:
200:
161:
137:
113:
93:
73:
53:
29:parsimonious reduction
866:; Sabharwal, Ashish;
696:
673:
650:
627:
599:
570:
550:
462:
442:
422:
402:
382:
362:
333:
304:
284:
264:
244:
221:
201:
162:
138:
114:
94:
74:
54:
894:. See in particular
682:
659:
636:
616:
597:{\displaystyle R(x)}
579:
559:
539:
451:
431:
411:
391:
371:
360:{\displaystyle R(x)}
342:
331:{\displaystyle R(x)}
313:
293:
273:
253:
233:
210:
190:
151:
127:
103:
83:
63:
43:
671:{\displaystyle \#x}
477:many-one reductions
973:dspace.jaist.ac.jp
721:as a formula in 3-
694:{\displaystyle x.}
691:
668:
648:{\displaystyle X,}
645:
622:
594:
565:
545:
457:
437:
417:
397:
377:
357:
328:
299:
279:
259:
239:
216:
196:
157:
133:
109:
89:
69:
49:
739:Hamiltonian Cycle
625:{\displaystyle x}
568:{\displaystyle x}
548:{\displaystyle R}
460:{\displaystyle Y}
440:{\displaystyle X}
420:{\displaystyle X}
400:{\displaystyle x}
380:{\displaystyle Y}
302:{\displaystyle x}
282:{\displaystyle Y}
262:{\displaystyle X}
242:{\displaystyle R}
219:{\displaystyle X}
199:{\displaystyle x}
182:Formal definition
172:counting problems
160:{\displaystyle B}
145:a unique solution
136:{\displaystyle A}
112:{\displaystyle B}
92:{\displaystyle A}
72:{\displaystyle B}
52:{\displaystyle A}
1011:
983:
982:
980:
979:
965:
959:
958:
956:
940:
934:
933:
905:
899:
893:
882:
860:
854:
853:
830:
824:
823:
811:
805:
804:
782:
719:can be rewritten
701:The examples of
700:
698:
697:
692:
677:
675:
674:
669:
654:
652:
651:
646:
631:
629:
628:
623:
603:
601:
600:
595:
574:
572:
571:
566:
554:
552:
551:
546:
466:
464:
463:
458:
446:
444:
443:
438:
426:
424:
423:
418:
406:
404:
403:
398:
386:
384:
383:
378:
366:
364:
363:
358:
337:
335:
334:
329:
308:
306:
305:
300:
288:
286:
285:
280:
268:
266:
265:
260:
248:
246:
245:
240:
225:
223:
222:
217:
205:
203:
202:
197:
167:and vice versa.
166:
164:
163:
158:
142:
140:
139:
134:
118:
116:
115:
110:
98:
96:
95:
90:
78:
76:
75:
70:
58:
56:
55:
50:
1019:
1018:
1014:
1013:
1012:
1010:
1009:
1008:
989:
988:
987:
986:
977:
975:
967:
966:
962:
942:
941:
937:
922:10.1137/0211025
907:
906:
902:
891:
880:
864:Gomes, Carla P.
862:
861:
857:
851:
832:
831:
827:
813:
812:
808:
802:
786:Goldreich, Oded
784:
783:
774:
769:
757:
741:
732:
711:
703:#P-completeness
680:
679:
657:
656:
634:
633:
614:
613:
610:
577:
576:
557:
556:
537:
536:
512:#P-Completeness
508:polynomial time
493:game complexity
481:NP-completeness
473:
449:
448:
429:
428:
409:
408:
389:
388:
369:
368:
340:
339:
311:
310:
291:
290:
271:
270:
251:
250:
231:
230:
208:
207:
188:
187:
184:
149:
148:
143:, there exists
125:
124:
101:
100:
99:has a solution
81:
80:
61:
60:
41:
40:
25:game complexity
17:
12:
11:
5:
1017:
1015:
1007:
1006:
1001:
991:
990:
985:
984:
960:
954:10.1.1.81.7891
935:
916:(2): 329–343.
900:
889:
855:
849:
825:
806:
800:
771:
770:
768:
765:
756:
753:
749:directed graph
740:
737:
731:
728:
710:
707:
690:
687:
667:
664:
644:
641:
621:
609:
606:
593:
590:
587:
584:
564:
544:
472:
469:
456:
436:
416:
396:
376:
356:
353:
350:
347:
327:
324:
321:
318:
298:
278:
258:
238:
215:
195:
183:
180:
156:
132:
108:
88:
68:
48:
15:
13:
10:
9:
6:
4:
3:
2:
1016:
1005:
1002:
1000:
997:
996:
994:
974:
970:
964:
961:
955:
950:
946:
939:
936:
931:
927:
923:
919:
915:
911:
904:
901:
897:
892:
890:9781586039295
886:
879:
878:
873:
872:Heule, Marijn
869:
865:
859:
856:
852:
850:9783540299530
846:
842:
841:
836:
829:
826:
821:
817:
810:
807:
803:
801:9781139472746
797:
793:
792:
787:
781:
779:
777:
773:
766:
764:
761:
754:
752:
750:
746:
738:
736:
729:
727:
724:
720:
716:
708:
706:
704:
688:
685:
665:
642:
639:
619:
607:
605:
588:
582:
562:
542:
533:
531:
526:
524:
522:
517:
513:
509:
505:
500:
498:
494:
490:
486:
482:
478:
470:
468:
454:
434:
414:
394:
374:
351:
345:
322:
316:
296:
276:
256:
249:from problem
236:
229:
213:
193:
181:
179:
177:
173:
168:
154:
146:
130:
122:
106:
86:
66:
46:
38:
34:
30:
26:
22:
976:. Retrieved
972:
963:
944:
938:
913:
909:
903:
876:
868:Selman, Bart
858:
839:
828:
819:
809:
790:
758:
742:
733:
730:Planar #3SAT
712:
655:the problem
611:
534:
527:
519:
503:
501:
474:
471:Applications
227:
185:
169:
144:
121:at least one
120:
28:
18:
896:pp. 634–635
269:to problem
59:to problem
993:Categories
978:2019-05-15
833:Flum, J.;
767:References
760:Shakashaka
755:Shakashaka
949:CiteSeerX
930:0097-5397
835:Grohe, M.
663:#
119:also has
37:bijection
33:reduction
837:(2006),
788:(2008),
487:such as
475:Just as
951:
928:
887:
847:
798:
726:well.
497:sudoku
881:(PDF)
709:#3SAT
514:. In
926:ISSN
885:ISBN
845:ISBN
796:ISBN
745:this
715:3SAT
226:. A
186:Let
27:, a
23:and
918:doi
723:CNF
521:FPT
147:of
19:In
995::
971:.
947:.
924:.
914:11
912:.
818:,
775:^
532:.
518:,
489:#P
176:#P
981:.
957:.
932:.
920::
898:.
689:.
686:x
666:x
643:,
640:X
620:x
592:)
589:x
586:(
583:R
563:x
543:R
455:Y
435:X
415:X
395:x
375:Y
355:)
352:x
349:(
346:R
326:)
323:x
320:(
317:R
297:x
277:Y
257:X
237:R
214:X
194:x
155:B
131:A
107:B
87:A
67:B
47:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.