A Structured View on Weighted Counting with Relations to Counting, Quantum Computation and Applications Cassio P. de Campos ∗1, Georgios Stamoulis †2, and Dennis Weyland ‡3 7 1Queen’s University Belfast, Northern Ireland, United Kingdom 1 2Department of Data Science & Knowledge Engineering, Maastricht University, 0 2 The Netherlands n 3Department of Economics and Management, University of Brescia, Italy a J 3 2 Abstract ] C Weighted counting problems are a natural generalization of counting problems where a C weightisassociatedwitheverycomputationalpathofnon-deterministicTuringmachinesand . the goal is to compute the sum of the weights of all paths (instead of just computing the s c number of accepting paths). Many useful closure properties and plenty of applications make [ weighted counting problems interesting. The general definition of these problems captures even undecidable problems, but it turns out that obtaining an exponentially small additive 1 approximation is just as hard as solving conventional counting problems. In many cases v such an approximation is sufficient and working with weighted counting problems tends to 6 8 be very convenient. We present a structured view on weighted counting by defining classes 3 that depend on the range of the function that assigns weights to paths and by showing the 6 relationships between these different classes. These classes constitute generalizations of the 0 usual counting problems. Weighted counting allows us to easily cast a number of famous . results of computational complexity in its terms, especially regarding counting and quantum 1 0 computation. Moreover, these classes are flexible enough and capture the complexity of 7 variousproblemsinfieldssuchasprobabilisticgraphicalmodelsandstochasticcombinatorial 1 optimization. Usingtheweightedcountingterminologyandourresults,weareabletogreatly : simplify and answer some open questions in those fields. v i X 1 Introduction r a Counting problems play an important role in computer science and can be informally defined as finding the number of solutions (that is, computational paths of polynomial length that end in an accepting state) of a givencombinatorialdecision problem. Weighted counting problems are a naturalgeneralizationofcountingproblems: aweightisassociatedwitheverycomputationalpath and the goalis to compute the sum of the weights of all computationalpaths. Weighted counting has numerous applications in a wide variety of fields, such as quantum computation, stochastic combinatorialoptimization,probabilisticgraphicalmodels,tonamebutafew. Inmanysituations itis morenaturalandmoreconvenienttouse weightedcountingproblems insteadofconventional counting problems. For instance, certain proofs can be simplified and stated in a more intuitive manner by using weighted counting. It also offers additional closure properties which do not hold ∗E-mail: [email protected] †E-mail: [email protected] ‡Email: [email protected] 1 for the conventionalcounting classes. Because of that and because the computational complexity of weighted counting is closely related to that of conventional counting, the former might be preferred to the latter when studying some computational complexity questions. In this work we give compact definitions for different classes of weighted counting problems, whichdiffer onlyin the rangeof their weights. Inparticular,we study the complexity ofweighted countingproblemsusingnatural,integer,rationalandrealnumbersasweightstogetherwithsome more restricted cases where weights take values on finite sets such as {0,1} and {−1,1}. If one allows only positive integers as weights, it is easy to show that problems remain in #P, the class of(non-weighted)counting problems[57]. If negativevaluesare allowed,evenif they areintegers, thenitisnotpossibleanymoretoguaranteethattheresultisanon-negativevalue. Therefore,these problems are not in #P by definition. In order to study these cases, we adopt the terminology of #P-equivalence to indicate that a problem is #P-hard under 1-Turing reductions and can be affinely reduced to a problem in #P. This concept of affine reductions is closely related to weightedreductions[12], butitis notapproximatepreserving[26]. Inshort,itallowspolynomial- time preprocessing of the input and an affine transformation of the output from the function. Essentially,thedifferencebetween#P-equivalence andpreviouslyused1-Turing#P-completeness isthe affine transformationforthe membershipin#P. Hence,problemswhicharenotactuallyin #P because of technical details can still be #P-equivalent. Using this terminology, we show that problems using weights from the set {−1,1}, and from arbitrary integers, are closely related to #P problems, and also that the decision variants of these weighted counting problems remain in PP (the class of problems related to the decision of whether the majority of the polynomial-time computational paths are accepting paths) [34]. While some of these results are considered to be known by the community, we are not aware of an explicit and precise treatment of all relevant cases. The weighted counting problems just described are asking for computing results whose size is always bounded by a polynomial in the input size. In this case, the corresponding decision variants remain in PP. However, this is not necessarily the case for weighted counting problems whenoneallowsweightsto be takenfromrealorevenrationalnumbers. Inspite ofthat, weshow that computing arbitrarily good additive approximations for these problems is a #P-equivalent problem. Regarding the corresponding decision problems, it is shown that the superclass of PP whichallowsrationalweights(wewilllaterdenoteitasPP )candecidethe haltingproblem,and Q hence strictly contains PP. We also address the relations between complexity classes of weighted counting problems and those of quantum computation. We show that weighted counting can be used to represent the acceptance probability of a quantum Turing machine in a very natural way. Based on this ob- servation, it is possible to derive complexity results regarding quantum computation using very simplified proofs. For instance, we are able to show that BQP⊆AWPP [33] using a very simple andshortargumentation(BQP is the class ofdecision problemsthat canbe solvedby a quantum Turing machine with bounded error probability [9] and AWPP is a quite restricted gap defin- able counting class and the best known classical upper bound for BQP [30]). Finally, we give a short and intuitive proof of the recently published result that quantum Turing machines with bounded error can be simulated in a time- and space-efficient way using randomized algorithms with unbounded error that have access to random access memory [59]. Weconcludethepaperwithadiscussionoftheimplicationsofourresultsforproblemsinother fieldssuchasinferencesinprobabilisticgraphicalmodelsandstochasticcombinatorialoptimization problems. Using these results and terminology, it is possible to simplify complexity proofs for those problems and to close some open questions, namely, upper bounds for the computational complexityofvariouscomputationaltasksrelatedtoprobabilisticgraphicalmodels andtwo-stage stochastic combinatorialoptimization problems. 2 2 Counting Classes, Generalizations and Historical Devel- opments The starting point of our work is the definition of conventional counting problems and the cor- responding class of decision problems. This definition is altered to allow for the summation of weights instead of counting accepting paths. Restrictions on the weights lead to several different classes of problems. We discuss basic properties of these classes and relate them to conventional counting problems. Additionally, we show that the closure properties for conventional counting problemscanbeextendedtoweightedcountingproblems. Althoughthesepropertiesmakeitcon- venient to work with weighted counting problems, the general definition leads to problems which might have an exponentially long output or even capture undecidable problems. We then show that from a complexity point of view approximating weighted counting problems up to an expo- nentiallysmalladditiveerrorisbasicallyequivalenttosolvingconventionalcountingproblems. In many cases such an approximation is sufficient and therefore weighted counting is a convenient andpowerfultool. Webeginwithanintroductiontorelatedconcepts. Since countingclassesplay a central role in our paper, we devote part of this section to discuss them. 2.1 Counting Problems and Generalizations ProblemsinthecomplexityclassNParerelatedtothequestionofwhether,foragiveninput,there exists at least one valid certificate of polynomial size (with respect to the input size) and which canalsobe checkedinpolynomialtime (withrespecttothe input size). This complexityclasshas been generalized in 1979 [57, 58] in the following way: instead of deciding if there exists at least one valid certificate for a giveninput, we want to compute, for a giveninput, the number of valid certificates. Suchproblemsarecalledcountingproblemsandaresubsumedinthecomplexityclass #P. More formally, we can define counting problems as follows. Definition 1 (Counting Problem). We are given a polynomial p and a polynomial-time predicate T (meaning a polynomial-time Turing machine whose output is either 0 or 1). The counting problem associated with p and T is to compute for x∈{0,1}⋆ the function f(x)= T(x,u). u∈{0X,1}p(|x|) We alsoneed definitions of relatedcomplexity classes(such as BPP,PP,BQP)while studying the relationships of weighted counting and other classes. Their definitions are given below. Definition 2 (BPP). A language L⊆{0,1}⋆ is in the complexity class BPP if and only if there exists a polynomial p and a polynomial-time predicate M (meaning a polynomial-time Turing machine whose output is either 0 or 1) such that for every x ∈ L, the fraction of strings y of length p(|x|) which satisfy M(x,y) = 1 is greater than or equal to 2/3; for every x ∈/ L, the fraction of strings y of length p(|x|) which satisfy M(x,y)=1 is less than or equal to 1/3.1 Definition 3 (BQP). A language L⊆{0,1}⋆ is in the complexity class BQP if and only if there exists a polynomial-time uniform family of quantum circuits {Q :n∈N}, such that: n 1. For all n∈N , Q takes n qubits as input and outputs 1 bit. n 2. For all x∈L, Pr(Q (x)=1)≥ 2. x 3 | | 3. For all x∈/ L, Pr(Q (x)=0)≥ 2. x 3 | | 1The stringy can be seen as the output of the random coin flips that the probabilistic Turing machine would havemade. 3 Thisclassisdefinedforaquantumcomputeranditsnaturalcorrespondingclassforanordinary computer (or a Turing machine plus a source of randomness) is BPP. Just like P and BPP, BQP is low for itself, which means BQPBQP = BQP. In fact, BQP is low for PP, meaning that a PP machine (see the following definition) achieves no benefit from being able to solve BQP problems instantly, anindicationof the possible difference in powerbetween these relatedclasses. The relation between BQP and NP is not known. Adding post-selection to BQP results in the complexity class PostBQP which is equal to PP [1]. Theclosestdecisioncomplexityclassto#P isPP, standingforProbabilisticPolynomialtime. Definition4 (PP). AlanguageL⊆{0,1}⋆ isinthecomplexityclass PPifandonlyifthereexists a polynomial p and a polynomial-time predicate M (meaning a polynomial-time Turing machine whose output is either 0 or 1) such that: 1. For all x ∈ L, the fraction of strings y of length p(|x|) which satisfy M(x,y) = 1 is strictly greater than 1/2. 2. For all x∈/ L, the fraction of strings y of length p(|x|) which satisfy M(x,y)=1 is less than or equal to 1/2. As usual, the string y should be interpreted as a string of bits corresponding to random choices. The terms “less than or equal” can be changed to “less than” and the threshold 1/2 can be replaced by any fixed rational number in ]0,1[, without changing the class. PP is a very powerfulclass: itcontainsBPP,BQPandNP.Inthe followingwegiveanewandextremelyshort intuitive proof that PP contains BQP (and also the related class AWPP, see Section 4) based entirely on the concept of weighted counting. Moreover,as we will discuss shortly, a polynomial- time Turing machine with access to a PP oracle can solve the entire polynomial hierarchy. On the other hand, PP is contained in PSPACE (polynomial-space bounded Turing Machines; for instance, polynomial space can solve the majority satisfiability problem simply by going through eachpossible assignment). Another concept fromcomplexity theory that we need is the notionof Functional Problems. Definition 5 (FP). Abinary relation P(x,y) is in the complexity class FP if and onlyif for every x∈{0,1}⋆ there is a deterministic polynomial-time (in |x|) algorithm that finds some y ∈{0,1}⋆ such that P(x,y) holds (or tells that such y does not exist). The difference between FP and P is that problems in P have one-bit yes/no answers, while problemsinFPcanhaveanyoutputthatcanbe computedinpolynomialtime. JustasPandFP are closely related, NP is closely related to FNP. In a straightforward way, the class of relations FP#P containsall relationsthat canbe computed in polynomialtime with accessto a #P oracle. We use the terminology FP#P[m] to limit the overall number of calls to the oracle to m. We note that FP#P is a very powerful class, as it was shown in [56]: every function in #PH is Turing-1reducibleinpolynomialtimetosomefunctionin#P,thus#PH⊆FP#P[1] (where#PH is the class of functions that count the number of accepting paths of polynomial time-bounded nondeterministic oracle Turing machines with oracle sets from the polynomial hierarchy PH). 2.2 Related Work and Historical Developments Since its introduction, the class #P has been very successful in characterizing the difficulty of counting problems: for this, central is the role of #P-completeness [57, 58] introduced to capture the computationalcomplexity ofthe permanent. Surprisingly,not only all NP-complete problems have their counting version #P-complete (this is true under parsimonious reductions) but also many“easy”problemssuchasperfect matchingare#P-completeintheircountingversions. These problemswith easy decisionversion(called“hardto count-easyto decide” in[23])cannotbe #P- completeunderparsimonious reductions,butare#P-completeunderCookreductions. See[46]for somecloselyrelatedclassessuchasTotPand#PE(standingfor#P-easy)andtheircorresponding 4 structuralpropertiesandcharacterizationsandalso[38,52]forworkonsomeothercloselyrelated subclasses of #P that contain functions with easy decision variants. Intheclassical“textbook”proofthatcomputingthepermanentofamatrixM ∈Zn n is#P- × complete [8], first it shown a reduction to the computation of the permanent of another matrix M′ ∈ Zn×0n and then to the computation of the permanent of a matrix M′′ with 0/1 entries. In other≥words, a counting problem over arbitrary integers is reduced to a classic 0/1 counting problem. This however requires pre and postprocessing, so it has been argued that #P might not be the correct class when we are interested in counting. Indeed #P has some disadvantages: the class #P is not closed under many operations. Namely, #P is not (or is not known to be) closed under subtractions or binomial coefficients. A direct implication of the first case is that computing the permanent of a matrix with arbitrary integer entries is not #P by definition. This was a main motivation behind the work of Fenner, Fortnow and Kurtz [30] that introduced and defined the complexity class GapP (intuitively, a class of functions that introduces “gaps” between the number of accepting and rejecting computations of NP machines) as an alternative to #P (see also [31] for a more systematic study of gap definability). The authors claim that this class constitutes a natural alternative for #P. Indeed, many computations (such as the permanentoverarbitraryintegers)whichareoutside#PfallnowinsideGapP.Moreover,GapPis showntobeclosedundernon-trivialoperationssuchassubtractions,binomialcoefficients,etc(see also [6]). Arguably, the success of GapP comes from the work of Beigel, Reingold and Spielman to show that PP is closedunder the operationof intersection[7] and also due to the fact that the definition of GapP helps to simplify very important complexity theoretic results: Toda’s famous theorem that the entire polynomial hierarchy is contained in PPP [54] can be cast in terms of GapP [55]. The very important result that BQP ⊆ PP by Adleman, DeMarrais and Huang [3] can also be simplified and improved with GapP: in [33], among others, it has been shown, using GapP definable functions, that PPBQP = PP. Moreover, it has been shown that BQP⊆ AWPP, which is the best current upper bound for BQP. Regarding the simulation of a BQP machine by a randomized, unbounded error machine, the most efficient simulation was given in a very recent article by van Malkebeek and Watson [59]. In spite of that, it seems that the class GapP cannot capture the complexity of weighted counting, where every computational path has a weight and we are interested in computing the sum of weights of all computational paths, which is precisely the focus of this work. Inanotherline ofresearch,the complexityofcountingconstraint satisfaction problems (CSPs) has been investigated. We recall that a CSP can be formulated as follows: Let D be an arbitrary finitesetcalledthedomainset. LetR={R ,R ,...,R }beanarbitraryfinitesetofrelationson 1 2 k D. Each R has an arity n ∈ N. As input we have variables x ,...,x over D, and a collection i i 1 n of constraints R∈R, each applied to a subset of variables. The decision query is whether there is an assignment that satisfies all the constraints and the corresponding counting version asks to compute the number of satisfying assignments. First, identify each R ∈ R with a binary valued function φ(R). Then a counting CSP is to evaluate the following so-called partition function on an input instance I: P(I)= f(x ,...,x ), i1 ir xXi∈DfY∈I wheref hasarityr andisappliedtovariablesx ,...,x . Iff is0/1valued,thenthis countsthe i1 ir number of solutions. If φ can take arbitrary values, then we have a weighted CSP problem (see for example [12] and [24]). Feder and Vardi [28] conjectured that a CSP over constraints R is either in P or NP-hard, and very recent work may have settled this question [48]. In a very recent breakthrough, Cai and Chen [15, 16] proved a dichotomy theorem for the counting versions of CSPs over complex weights: Given any finite D and any finite set of constraint functions F, where fi : Dni → C, the problem of computing the partitionfunction P(I) is either in P or #P-hard. On the negative side, the criteria are not knownto be computable, but still the dichotomy exists. Another similar dichotomy conjecture, but yet to be proved, exists for #CSP, namely that any #CSP problem is 5 either in FP or #P-complete. See [13] for some partial results regarding this conjecture and see also [24, 17, 12, 14, 63, 64] for other results in the are of counting versions of CSPs. Another related result comes from Bla¨ser and Curticapean [11] in which the #W[1]-hardness of the weighted counting of all k-matchings in a bipartite graph was given. There, the weight of a matching is simply the product of the weights of the edges that constitute this matching. Inyetanotherline ofresearchandmorerelevanttoourstudy,aweightedcountingclass#P Q′ has been defined by Goldberg and Jerrum[35]. This is the class of functions f :{0,1} →Q that ∗ canbewrittenasthedivisionofa#PfunctionoveranFPfunction. Thisclasswasusedtoclassify the complexityof approximatingthe value ofTutte polynomialsofa graphthat take asargument arbitraryrationalnumbers. Recallthatthe Tutte polynomialofa givengraphGis atwo-variable polynomial T (x,y). Usually, the arguments x, y are integers (not necessarily positive), but the G authors were interested in the most generalcase where x,y are arbitrary rationalnumbers. Tutte polynomials can encode interesting graph theoretic properties. For instance, T (1,1) counts the G number of spanning trees in G, T (2,1) counts the number of forests in G, and so on. Tutte G polynomialsarealsoverycloselyconnectedto chromaticpolynomials,flowpolynomials,etc. This class #P is a strict subclass of the class #P(pt) defined later on. We shall mention that the Q′ Q complexity of exactly evaluating Tutte polynomials is #P-hard [39] except for some threshold cases. The authors were interested in some dichotomy results and they significantly widened the cases where there exist a fully polynomial time randomized approximation scheme (FPRAS) for T (x,y), and showedthat some other particular cases do not attain FPRAS (modulo RP 6= NP). G Finally, it is important to mention the result of Yamakami [62] that is probably the closest to the settings in this paper. There, the author studied a class of quantum functions, namely #QP , which are defined as the set of functions computing the acceptance probability of some K polynomial-time quantum Turing machine, the amplitudes of which are drawn from a set K. We follow a similar notation here. He also defined the corresponding gap definable function GapQP = #QP −#QP . He named these functions as quantum probability and quantum K K K probability gap functions, respectively. Among other very interesting results, Yamakami proved the following nice characterizationof PP in terms of some generalized quantum classes: Theorem 1 (Theorem 7.1 in [62]). Let A ⊆ {0,1} and let A be the set of complex algebraic ∗ numbers. Then, the following statements are all equivalent: 1. A∈PP, 2. ∃f,g ∈#QP such that ∀x∈{0,1} , x∈A⇔f(x)>g(x), A ∗ 3. ∃f,g ∈GapQP such that ∀x∈{0,1} , x∈A⇔f(x)>g(x). A ∗ TheusefulnessofthisresultisevenmoreevidentwhenYamakami,inthesamepaper,considers thequantumanalogofPP,namelyPQP forsomeamplitude setK (wheretheusualpolynomial- K time Turing machine of the standard definition of PP is replaced by a certain quantum Turing machine). Using the above theorem, Yamakami proved that PQP = PP. Later in this paper, A we will show that PP over arbitrary (approximable) rational numbers contains even undecidable problems and thus cannotbe equalto PP.However,we do not know if the statement is true if we consider a more restricted definition. 2.3 Weighted Counting Problems Asastraightforwardgeneralizationofconventionalcountingproblems,weightedcountingproblems can be formally defined in the following way. Definition 6 (Weighted Counting Problem). We are given a polynomial p and a function w : {0,1}⋆×{0,1}⋆ → R that can be approximated by a polynomial-time (in the size of the first two arguments and the third argument) computable function v : {0,1}⋆×{0,1}⋆×N → Z, such that 6 |w(x,u)−v(x,u,b)/2b|≤2 b forallx∈{0,1}⋆,u∈{0,1}⋆,b∈N. Theweightedcountingproblem − associated with p and w is to compute for x∈{0,1}⋆ the function f(x)= w(x,u). u∈{0X,1}p(|x|) Here,xistheinputtotheweightedcountingproblemandwrepresentsthe2p(x)manyweights | | for a given input x. With the restriction to w, imposed by the approximation property, we limit therangeofwtoefficientlycomputablenumbersasdefinedin[44]. Asimilarnotioninthecontext ofquantumcomputationisusedin[3,59]. Foragivenrationalthresholdvaluewecanthendefine the corresponding decision problem in the following way. Definition 7 (WeightedCountingProblem,DecisionVariant). We are given a weighted counting problem defined by a polynomial p and a function w:{0,1}⋆×{0,1}⋆ →R as well as a threshold value t∈Q. The corresponding decision problem is to decide for x∈{0,1}⋆ whether f(x)≥t or not. Withoutlossofgenerality,wecouldhaveusedanintegerthresholdvalueintheabovedefinition, since the denominator of the threshold value can always be multiplied into the weight function. Nevertheless, the definition given above might be more convenient for applications of weighted counting, while assuming an integer threshold value could be used to simplify proofs. Asmentionedearlier,weightedcountingproblemsmayhavedifferentcharacteristicsdepending on the set from which weights are taken. For any given set S ⊆ R, we define the class #P to S consist of all functions f : {0,1}⋆ → R corresponding to weighted counting problems where the range of w is restricted to S. The class of the corresponding decision problems is then denoted by PP . By using this notation, we can define the classes #P , #P , #P , #P , S 0,1 1,1 1,0,1 N #P , #P and #P , as wellas the correspondingclassesof dec{isio}npro{b−lem}s PP {− , PP} , Z Q R 0,1 1,1 { } {− } PP ,PP ,PP ,PP andPP . Theseclassescontaininterestingproblems,sinceforinstance 1,0,1 N Z Q R {− } the permanentofmatriceswithentriesthatarenotnaturalnumbersalreadyfallsinsuchdifferent classes depending on the range of the entries. Some inclusions among these classes are trivial, since S ⊆S ⇒(#P ⊆#P )∧(PP ⊆PP ). 1 2 S1 S2 S1 S2 Itiseasytoseethat#P isequalto#P[57],theclassof(non-weighted)countingproblems. 0,1 The same equality holds fo{r th}e corresponding classes of decision problems PP and PP. Ad- 0,1 { } ditionally, #P is equal to GapP [30], the closure of #P under subtraction, while #P 1,0,1 1,1 equals GapP u{n−der n}ormal Turing machines (the computational tree is completely binary){,−and} therefore PP and PP are equal to PP, since #P andGapP constitute the same class 1,1 1,0,1 {− } {− } of decision problems. The classes #P and PP are extremely powerful since the output of #P can be infinitely R R R long. For instance,PP containsthe halting problem. The followingresultconfirmsthatnotonly R #P and PP but also #P and PP are extremely powerful classes, since they also contain the R R Q Q halting problem. Let ha,birepresentthe concatenationofthe bitstring representationsof a andb. Theorem 2. #P contains unsolvable problems and PP can decide the halting problem. Q Q Proof. Define a weight function w that, on input x = hM,yi, is as follows: w(x,0) = 0 if the Turingmachine representedby M does notterminate oninput y,while w(x,0)= 1 ifthe Turing 2t machine represented by M terminates after t steps on input y. We also define w(x,u) = 0 for every u 6= 0. As required by Definition 6, this weight function w can be approximated by a polynomial-time computationthat oninput (x,0,b) simulates M oninput y and if the simulation does not terminate after b+p(|x|) steps, then it outputs 0, while if the simulation terminates at step t ≤ b+p(|x|), then it outputs 1. The additive error of this approximation is at most 2 b, 2t − since there are less than or equal to 2p(x) paths with an approximate value, each of which with | | an error of at most 2 b p(x). Therefore, we have constructed a problem in #P such that M − − | | Q terminates oninput y if andonlyif f(x)>0 andthus if wewere ableto decide the corresponding counting problem, then we would be able to decide the halting problem. 7 Corollary 1. PP is strictly contained in PP . Q Theorem 2 suggests that our definition gives too much power to PP and #P and they Q Q are possibly equal to PP and #P , respectively. Since we are interested in understanding the R R complexityofpracticalproblems,aswewilldiscussinSection5,wedecidetoworkwitharestricted version of PP and #P from now on. Q Q Definition 8. #P(pt) is the subset of #P for which the weighted counting problems have their Q Q function w (as in Definition 6) computable in polynomial time (in the size of its input). PP(pt) is Q the associated decision version. Inthefollowingwefurtherinvestigatetherelationsamongtheotherclassesofweightedcount- ing problems and their corresponding decision versions. Before proceeding, we must define the terminology of #P-equivalence that will be used throughout the paper. This definition was nec- essary because #P is not closed with respect to polynomial-time computations. This leads to several inconveniences. We make use of an adapted version of weighted reduction [12], as sug- gested in [20], but we allow for affine postprocessing of the output from the desired function. For other definitions of metric reductions, see for example [27]. Definition 9. A function f : {0,1}⋆ → R affinely reduces to g : {0,1}⋆ → R if there are polynomial-time computable functions h ,h ,h such that ∀x∈{0,1}⋆ :f(x)=h (x)·g(h (x))+ 1 2 3 1 2 h (x). 3 Definition 10. A problem A is #P-hard under 1-Turing metric reductions if #P ⊆ FPA[1]. Problem A is said #P-complete if A is #P-hard and A∈#P. Note that we use a restrictedversionof hardnesswhen comparedto the definition in Valiant’s seminal work [58]. There, an unlimited number of oracle calls are allowed, that is, problem y is #P-hard if #P ⊆ FPy. This definition with unlimited calls allows PP-complete problems such as majority satisfiability to be #P-complete. This is somewhat undesired, since the classes PP and #P are not known to have similar power. For instance, PP = PPP[log] [7, 32], while the correspondingquestionfor #P is open, to the best ofour knowledge. In particular,it is unknown whether FP#P[1] is strictly contained in FP#P[2] [36, 49]. As discussed earlier, #PH ⊆ FP#P[1], suggestingthatlimitedcallsto#ParemorepowerfulthanlimitedcallstoPP,whileunlimitedcalls give us no distinction between them and FPPP =FP#P. We note that this distinction may have practical implications. For instance, the recently very active topic of probabilistic logics has seen someimportantproblemsfallingintoclassessuchasPPNP,...,PPPH [18,19]. Allthoseclassesare confinedbetweenthe limitedandunlimited PPcalls: PP=PPP[log] ⊆PPNP ⊆PPPH ⊆PPP [54]. Definition 11. A problem A is #P-equivalent if it is #P-hard under 1-Turing metric reductions and can be affinely reduced to a problem in #P. The concept of #P-equivalence for problems relaxes the concept of #P-completeness under 1-Turing reductions by introducing the affine reduction instead of actual membership. Arguably, such concept gives a more useful relation between problems that are said to be #P-equivalent whencomparedto #P-completeness. Any #P-complete under 1-Turingreductionproblemis also #P-equivalent(theinversedoesnotnecessarilyhold;forinstance,permanentofintegermatricesis #P-equivalentbut is not#P-complete, since it does notbelong to #P). Actually, the derivations we have in this paper would work even if we restricted ourselves to affine reductions for showing hardness, but 1-Turing reductions might be a reasonable compromise. Definition 12. A class C is #P-equivalent if any problem in C can be reduced to a problem in #P via an affine reduction and vice-versa, that is, any problem in #P can be reduced to a problem in C via an affine reduction. The notion of equivalence is commutative, and could be applied to any other functional com- plexity class. It gives a means to represent the strong relationship between some classes, as we 8 willseelateron. Itisworthnotingthatthedecisionvariantsofproblemsin#P-equivalentclasses are in PP. We first show equality of the classes #P and #P , as well as equality of the classes 0,1 N #P and #P . This implies equality o{f t}he corresponding classes of decision problems, 1,0,1 Z nam{e−ly of}PP and PP , and of PP , PP and PP . These results are widely un- 0,1 N 1,1 1,0,1 Z derstood as “k{no}wn” by the community{,−but}to th{−e best}of our knowledge they have never been explicitly stated. Since the rangeof the functions in #P is not limited to non-negativeinte- 1,1 gers,asitisthecaseforthefunctionsin#P ,theset{w−ocl}assescannotbeequal. Nevertheless, 0,1 it is possible to show that all these classes a{re #}P-equivalent. We later focus on weighted counting problems in #P(pt), #P and #P as well as on their Q Q R correspondingdecisionvariants. #P and#P captureundecidableproblems,aswehaveproven. Q R Itisimmediatetoshowthat#P ⊆#P(pt)andPP ⊆PP(pt). Additionally,thesizeoftheoutput Z Q Z Q ofweightedcountingproblemsbelongingto#P(pt) isnotnecessarilypolynomiallyboundedbythe Q input size. Therefore, the inclusion of #P in #P(pt) is strict, and it is generally not possible to Z Q give polynomial reductions from problems in #P(pt) to any of the more restricted classes. As we Q will see inSection 2.5, itis stillpossible to solveproblemsin #P using a #P-equivalentproblem R suchthat we lose only a small additive approximationerror. This result then implies that PP(pt), Q PP and PP are actually PP as long as we focus on problems whose output size is polynomially Q R bounded in the input size. We make use ofthe followingproperty to showequalitybetween #P and#P . Giventhe 0,1 N weight function w and its approximation v (Definition 6), we can assur{e th}at the integer part of the weights can always be encoded using polynomially many bits. We then add this polynomial to the given polynomial p and construct a new weight function using only weights of 0 and 1, such that the overallsum does not change. We formalize these ideas in the proof of the following theorem. Theorem 3. #P =#P . 0,1 N { } Proof. Since problems in #P are by definition in #P , we only have to show the other 0,1 N inclusion. Foraweightedcount{ing}problemin#P definedbyapolynomialpandaweightfunction N w :{0,1}⋆×{0,1}⋆→N, we constructthe followingweightedcounting problemin#P . Take 0,1 thepolynomialp =p+q,whereq isapolynomialboundingthenumberofbitsrequired{to}encode ′ the integer part of the weights of our original problem. Define w :{0,1}⋆×{0,1}⋆→{0,1} by ′ 1 if #u <w(x,u ) 2 1 w (x,u)= ′ (0 else, where u are the first p(|x|) bits of u and #u is the number encoded by the last q(|x|) bits 1 2 of u. Since the two functions defined by the original weighted counting problem and the newly constructed weighted counting problem are identical, we conclude the proof. Theorem 4. #P =#P . 1,0,1 Z {− } Proof. It follows from the same arguments as in the proof of the previous theorem, this time applied to positive and negative weights. Observe that #P corresponds to GapP functions on normal Turing Machines (the com- 1,1 putational tree is com{−plet}ely binary) whereas #P =#P corresponds to GapP functions. 1,0,1 Z SinceGapPstrictlycontainsnormalGapPfunction{s−,wei}mmediatelyhave#P ⊂#P . 1,1 1,0,1 The classes #P = #P = #P , #P and #P = #P can{−not}be equa{l−, sinc}e 0,1 N 1,1 1,0,1 Z their ranges of output are{di}fferent. Never{t−hele}ss, there a{r−e affi}ne reductions from problems of each of these classes to the other classes. Theorem 5. #P and #P (which equals to #P ) are #P-equivalent. 1,1 1,0,1 Z {− } {− } 9 Proof. Since #P ⊂ #P , it is enough to show reductions from #P to #P and 1,1 1,0,1 1,1 from #P {t−o #}P. Any{−probl}em in #P (which equals #P) can be affinely r{e−duc}ed to 1,0,1 0,1 #P {−by mu}ltiplying allits weightsby 2 an{dt}hen subtracting 1. After solving the problemin 1,1 #P{− },theresultisretrievedbackusingtheinversetransformation,thatis,dividingtheoutput 1,1 {− } by 2 and summing 2p(x) 1. Any problem in #P can be affinely reduced to #P (which | | − 1,0,1 N equals #P). For that we can simply add a value{−of 1}to every weight of the given #P 1,0,1 problem, obtaining a problem in #P with weightsin {0,1,2}. We can then retrievethe re{−sulto}f N the original problem in #P by solving this new problem and then subtracting 2p(x) from 1,0,1 | | the resulting value. {− } This relation of equivalence clarifies that, at least from a computational viewpoint, problems that are #P-equivalent are not harder to solve than those in #P, as a single evaluation of a #P function plus an affine transformation gives us the desired result. This fact might not be so surprising, but it seems that the literature still has not taken it for granted. For instance, Chapter 17.3 of [4] suggests to the reader an approach to solve permanent of integer matrices using unlimited calls to a #P oracle (more precisely, a #SAT one). It also suggests two calls to solvematrices with entriesin {−1,0,1}. With the weightedcountingframework,it becomes clear that a single call is enough, even if entries would be drawn from rational numbers (as we will see later on – the key is that the output of permanent is always polynomially bounded in the input size), and that the problem is in FP#P[1], perhaps also in some lower class (any #P-equivalent problem is trivially in FP#P[1]). Intheremainderofthissection,weshowaproofthatforweightedcountingproblemsin#P(pt) Q the size of the output, even encoded as a fraction, is not necessarily bounded by a polynomial (pt) in the input size. This proves that #P cannot be #P-equivalent. We focus on the following Q simple problem. According to Definition 6, take the polynomial p to be the identity function and take the weight function w :{0,1}⋆×{0,1}⋆ →Q such that 1/(#u+1), if #u+1∈P and #u<x w(x,u)= (0, otherwise. Here#u isthe numberrepresentedbythe bitstringu andPis the setofprime numbers. Note that this function fulfills the approximationproperties of Definition 6. For a given input x∈N of size ⌈logx⌉, the task is to compute the value f(x)= 1/p= q/ p. p P p P q P p P pX∈x pX∈x q Yx∈,q=p  pY∈x ≤  ≤ ≤ 6  ≤   Note that this fraction cannot be simplified. The only numbers that divide the denominator are prime numbers of value at most x. Each of these prime numbers divides all parts of the sum except one and therefore it does not divide the whole sum. To show that the result cannot be represented efficiently with respect to the input size, we showthat itis notpossible to representthe denominatorefficiently with respectto the input size. For this purpose we presenta lower bound for the product of all prime numbers between x/e and x forsufficiently largex. Using this lowerbound wecanthen boundthe wholeproductappearing in the denominator of the output from below. Lemma 1. The number of prime numbers between x/e and x is bounded away from below by x/(3lnx) for sufficiently large x. Proof. Let π(x) denote the prime-counting function. Due to [50], we have for x≥17 that x x/e π(x)> and π(x/e)<1.25506 . lnx ln(x/e) 10