text: 4 Kim et al. Table 1. Analysed QSOs QSO zeam zHi,Civ S/Nb Inst. ref.c Notes Q0055–269 3.656 2.663–3.054, 3.077–3.390 [29, 62] UVES 1, 2, 3 PKS2126–158 3.280 2.413–2.608, 2.669–3.055, 3.075–3.208 [100, 125] UVES 1, 2, 3 HS1425+6039 3.180 2.667–3.110 [83, 71] HIRES 4 DLA at z = 2.827, sub-DLA at z = 2.770 Q0636+6801 3.175 2.863–3.105 [50, 67] HIRES 4 Q0420–388 3.115 2.670–2.615, 2.670–3.045 [125, 111] UVES 1, 2, 3 sub-DLA at z = 3.087 HE0940–1050 3.082 2.498–2.716, 2.776–3.014 [83, 111] UVES 1, 2, 3 HE2347–4342 2.873 2.080–2.710, 2.770–2.809 [100, 100] UVES 1, 2, 3 HE0151–4326 2.781d 2.072–2.710 [100, 125] UVES 1 mini-BAL Q0002–422 2.768 2.016–2.705 [87, 137] UVES 1, 2, 3 PKS0329–255 2.704 2.091–2.643 [38, 63] UVES 1, 2, 3 Q0453–423 2.657 1.978–2.595 [67, 100] UVES 1, 2, 3 sub-DLA at z = 2.305 HE1347–2457 2.612d 1.987–2.552 [63, 67] UVES 1, 2, 3 Q0329–385 2.435 2.001–2.378 [45, 83/45] UVES 1, 2, 3 HE2217–2818 2.413 1.979–2.355 [67, 100] UVES 1, 2, 3 mini-BAL Q0109–3518 2.405 1.976–2.348 [67, 91/140] UVES 1, 2, 3 HE1122–1648 2.404 1.975–2.346 [111, 200/71] UVES 1, 2, 3 HE0001–2340 2.264 1.993–2.211 [67, 80] UVES 1 sub-DLA at z = 2.187 J2233–606e 2.251 1.588–2.197 [33, 45] UVES 1, 2, 3, 5 mini-BAL PKS0237–23 2.222 1.975–2.167 [99, 136] UVES 1, 2, 3 sub-DLA at z = 1.673 PKS1448–232 2.219 1.986–2.168 [57, 122/70] UVES 1, 2, 3 Q0122–380 2.191d 1.977–2.140 [48, 77] UVES 1, 2, 3 Q1101–264 2.141 1.800–2.090f [67, 77] UVES 1, 2, 3 sub-DLA at z = 1.839 HE1341–1020 2.138d 1.972–2.086 [50, 63] UVES 1 mini-BAL a The redshift is measured from the observed Lyα emission line of the QSOs. b The ﬁrst and the second numbers separated by a comma in the brackets are the S/N per pixel estimated from the central parts of the Hi and Civ regions, respectively. Due to an instrument setup which determines the wavelength ranges to be overlapped, some QSOs have a much higher S/N for part of the Civ region. In this case, two numbers are listed separated by “/”. c 1: Kim et al. (2004); 2: Kim et al. (2007); 3. Kim et al. (2013); 4: Boksenberg & Sargent (2015); 5: Savaglio et al. (1999) d The redshift estimated from the Lyα emission proﬁle is uncertain as there are many absorption lines in the peak of the Lyα emission line or as the emission proﬁle is non-Gaussian. e The HST/STIS E230M spectrum (Savaglio et al. 1999) is included in the analysis 3 since its observed wavelength at 2550–3057 ˚A covers high-order Lyman lines of saturated Hi lines in the analysed redshift range. f Although Hi Lyman lines higher than Lyβ are not covered at z < 1.972, a robust Hi column density of a sub-DLA at z = 1.839 can be obtained due to the damping wing. In order to increase the high-NHi absorbers in our sample, the redshift range for this QSO was extended to z = 1.800. When metal lines were blended with H i lines and/or other continuum placement to achieve a overall better ﬁt result. metal lines, all the blended lines were included in the ﬁt si- Initially, the VPFIT continuum adjustment option was turned multaneously. To obtain reliable line parameters of saturated on. Then, comparing the unnormalised spectrum with the H i lines, all the available higher-order Lyman series such as adjusted continuum, we decided whether to take the VPFIT Lyβ and Lyγ were also included in the ﬁt. Since there is no adjustment as it was or to apply a slightly diﬀerent con- unique solution to the proﬁle ﬁtting, we imposed only one tinuum. With this re-adjusted new continuum, the entire condition: a minimum number of necessary components to spectrum was ﬁtted again. We iterated the continuum re- (cid:54) reach a reduced χ2 value to be 1.2, cf. Boksenberg & Sar- adjustment and ﬁtting several times until the satisfactory gent (2014). Note that the STIS E230M line spread function ﬁts were obtained, ﬁnding some more previously unidenti- − was used to ﬁt the J2233 606 STIS spectrum. ﬁed metal lines and ﬁxing any wrong line parameters pre- The redshifts and b parameters for H i and C iv were al- viously obtained. The ﬁnal iteration was done without the lowed to vary freely to obtain a minimum χ2 in VPFIT. The VPFIT continuum adjustment option. C iv absorbers found in QSO spectra are usually associated Note that all the quoted errors of the ﬁtted line parame- with a saturated Lyα H i and have a multi-component un- ters are directly from VPFIT. These do not include continuum saturated C iv. Even the higher order Lyman line proﬁles do uncertainties usually adopted in the Milky Way ISM stud- ± not reveal velocity structures as detailed as those of C iv, at ies, i.e. changing the continuum by 0.5 times the standard least in part because the thermal line broadening is greater deviation of a local continuum (?). We also note that VPFIT for hydrogen than carbon due to the atomic mass diﬀerence. does not work like the apparent optical depth analysis (?), in Consequently it is not generally possible to use H i to deter- that VPFIT looks for the best-ﬁt solution by minimising χ2. mine the C iv redshift. Indeed there is no physical reason to This is not necessarily a lower limit column density for sat- expect the velocity structure of C iv to closely follow that of urated lines. If the VPFIT column density errors are greater H i, given that the peculiar velocity and bulk motions play than 0.2–0.3 dex, the error estimates can be far from true for a role in the kinematics of the absorbers. Moreover, studies single saturated lines and one should treat the errors with of close QSO pairs show that H i and C iv display a diﬀerent caution (see the documents provided with VPFIT for more small-scale structure (?). It has also been found that there details, in particular Chapter 17). While the decomposition − is a velocity diﬀerence at 5–18 km s 1 between the centroids of absorption features depends on the local S/N and res- of H i and C iv (?). olution, especially b parameters, the total column density During the simultaneous ﬁt of diﬀerent transitions of integrated over a given velocity range is in general more se- the same ions, we have often adjusted a small amount of the curely determined. MNRAS 000, 000–000 (0000) ##LTLine## ##LTLine## ##LTLine##

text: Kim

text: et

text: al.

text: Table

text: Analysed

text: QSOs

text: QSO

label: table

text: zeam

text: zHi,Civ

text: S/Nb

text: Inst.

text: ref.c

text: Notes

text: UVES

text: UVES

text: HIRES

text: DLA

text: at

text: z

text: sub-DLA

text: at

text: z

text: HIRES

text: UVES

text: sub-DLA

text: at

text: z

text: UVES

text: UVES

text: UVES

text: mini-BAL

text: UVES

text: UVES

text: UVES

text: sub-DLA

text: at

text: z

text: UVES

text: UVES

text: UVES

text: mini-BAL

text: UVES

text: UVES

text: UVES

text: sub-DLA

text: at

text: z

text: UVES

text: mini-BAL

text: UVES

text: sub-DLA

text: at

text: z

text: UVES

text: UVES

text: UVES

text: sub-DLA

text: at

text: z

text: UVES

text: mini-BAL

text: a

text: The

text: redshift

text: is

text: measured

text: from

text: the

text: observed

text: Lyα

text: emission

text: line

text: of

text: the

text: QSOs.

text: b

text: The

text: ﬁrst

text: and

text: the

text: second

text: numbers

text: separated

text: by

text: a

text: comma

text: in

text: the

text: brackets

text: are

text: the

text: S/N

text: per

text: pixel

text: estimated

text: from

text: the

text: central

text: parts

text: of

text: the

text: Hi

text: and

text: Civ

text: regions,

text: respectively.

text: Due

text: to

text: an

text: instrument

text: setup

text: which

text: determines

text: the

text: wavelength

text: ranges

text: to

text: be

text: overlapped,

text: some

text: QSOs

text: have

text: a

text: much

text: higher

text: S/N

text: for

text: part

text: of

text: the

text: Civ

text: region.

text: In

text: this

text: case,

text: two

text: numbers

text: are

text: listed

text: separated

text: by

text: c

text: Kim

text: et

text: al.

text: Kim

text: et

text: al.

text: Kim

text: et

text: al.

text: Boksenberg

text: Sargent

text: Savaglio

text: et

text: al.

text: d

text: The

text: redshift

text: estimated

text: from

text: the

text: Lyα

text: emission

text: proﬁle

text: is

text: uncertain

text: as

text: there

text: are

text: many

text: absorption

text: lines

text: in

text: the

text: peak

text: of

text: the

text: Lyα

text: emission

text: line

text: or

text: as

text: the

text: emission

text: proﬁle

text: is

text: non-Gaussian.

text: e

text: The

text: HST/STIS

text: spectrum

text: (Savaglio

text: et

text: al.

text: is

text: included

text: in

text: the

text: analysis

text: since

text: its

text: observed

text: wavelength

text: at

text: ˚A

text: covers

text: high-order

text: Lyman

text: lines

text: of

text: saturated

text: Hi

text: lines

text: in

text: the

text: analysed

text: redshift

text: range.

text: f

text: Although

text: Hi

text: Lyman

text: lines

text: higher

text: than

text: Lyβ

text: are

text: not

text: covered

text: at

text: z

text: a

text: robust

text: Hi

text: column

text: density

text: of

text: a

text: sub-DLA

text: at

text: z

text: can

text: be

text: obtained

text: due

text: to

text: the

text: damping

text: wing.

text: In

text: order

text: to

text: increase

text: the

text: high-NHi

text: absorbers

text: in

text: our

text: sample,

text: the

text: redshift

text: range

text: for

text: this

text: QSO

text: was

text: extended

text: to

text: z

text: When

text: metal

text: lines

text: were

text: blended

text: with

text: H

text: i

text: lines

text: and/or

text: other

text: continuum

text: placement

text: to

text: achieve

text: a

text: overall

text: better

text: ﬁt

text: result.

text: metal

text: lines,

text: all

text: the

text: blended

text: lines

text: were

text: included

text: in

text: the

text: ﬁt

text: si-

text: Initially,

text: the

text: VPFIT

text: continuum

text: adjustment

text: option

text: was

text: turned

text: multaneously.

text: To

text: obtain

text: reliable

text: line

text: parameters

text: of

text: saturated

text: on.

text: Then,

text: comparing

text: the

text: unnormalised

text: spectrum

text: with

text: the

text: H

text: i

text: lines,

text: all

text: the

text: available

text: higher-order

text: Lyman

text: series

text: such

text: as

text: adjusted

text: continuum,

text: we

text: decided

text: whether

text: to

text: take

text: the

text: VPFIT

text: Lyβ

text: and

text: Lyγ

text: were

text: also

text: included

text: in

text: the

text: ﬁt.

text: Since

text: there

text: is

text: no

text: adjustment

text: as

text: it

text: was

text: or

text: to

text: apply

text: a

text: slightly

text: diﬀerent

text: con-

text: unique

text: solution

text: to

text: the

text: proﬁle

text: ﬁtting,

text: we

text: imposed

text: only

text: one

text: tinuum.

text: With

text: this

text: re-adjusted

text: new

text: continuum,

text: the

text: entire

text: condition:

text: a

text: minimum

text: number

text: of

text: necessary

text: components

text: to

text: spectrum

text: was

text: ﬁtted

text: again.

text: We

text: iterated

text: the

text: continuum

text: re-

text: reach

text: a

text: reduced

text: χ2

text: value

text: to

text: be

text: cf.

text: Boksenberg

text: Sar-

text: adjustment

text: and

text: ﬁtting

text: several

text: times

text: until

text: the

text: satisfactory

text: gent

text: Note

text: that

text: the

text: STIS

text: line

text: spread

text: function

text: ﬁts

text: were

text: obtained,

text: ﬁnding

text: some

text: more

text: previously

text: unidenti-

text: was

text: used

text: to

text: ﬁt

text: the

text: STIS

text: spectrum.

text: ﬁed

text: metal

text: lines

text: and

text: ﬁxing

text: any

text: wrong

text: line

text: parameters

text: pre-

text: The

text: redshifts

text: and

text: b

text: parameters

text: for

text: H

text: i

text: and

text: C

text: iv

text: were

text: al-

text: viously

text: obtained.

text: The

text: ﬁnal

text: iteration

text: was

text: done

text: without

text: the

text: lowed

text: to

text: vary

text: freely

text: to

text: obtain

text: a

text: minimum

text: χ2

text: in

text: VPFIT.

text: The

text: VPFIT

text: continuum

text: adjustment

text: option.

text: C

text: iv

text: absorbers

text: found

text: in

text: QSO

text: spectra

text: are

text: usually

text: associated

text: Note

text: that

text: all

text: the

text: quoted

text: errors

text: of

text: the

text: ﬁtted

text: line

text: parame-

text: with

text: a

text: saturated

text: Lyα

text: H

text: i

text: and

text: have

text: a

text: multi-component

text: un-

text: ters

text: are

text: directly

text: from

text: VPFIT.

text: These

text: do

text: not

text: include

text: continuum

text: saturated

text: C

text: iv.

text: Even

text: the

text: higher

text: order

text: Lyman

text: line

text: proﬁles

text: do

text: uncertainties

text: usually

text: adopted

text: in

text: the

text: Milky

text: Way

text: ISM

text: stud-

text: not

text: reveal

text: velocity

text: structures

text: as

text: detailed

text: as

text: those

text: of

text: C

text: iv,

text: at

text: ies,

text: i.e.

text: changing

text: the

text: continuum

text: by

text: times

text: the

text: standard

text: least

text: in

text: part

text: because

text: the

text: thermal

text: line

text: broadening

text: is

text: greater

text: deviation

text: of

text: a

text: local

text: continuum

text: We

text: also

text: note

text: that

text: VPFIT

text: for

text: hydrogen

text: than

text: carbon

text: due

text: to

text: the

text: atomic

text: mass

text: diﬀerence.

text: does

text: not

text: work

text: like

text: the

text: apparent

text: optical

text: depth

text: analysis

text: in

text: Consequently

text: it

text: is

text: not

text: generally

text: possible

text: to

text: use

text: H

text: i

text: to

text: deter-

text: that

text: VPFIT

text: looks

text: for

text: the

text: best-ﬁt

text: solution

text: by

text: minimising

text: mine

text: the

text: C

text: iv

text: redshift.

text: Indeed

text: there

text: is

text: no

text: physical

text: reason

text: to

text: This

text: is

text: not

text: necessarily

text: a

text: lower

text: limit

text: column

text: density

text: for

text: sat-

text: expect

text: the

text: velocity

text: structure

text: of

text: C

text: iv

text: to

text: closely

text: follow

text: that

text: of

text: urated

text: lines.

text: If

text: the

text: VPFIT

text: column

text: density

text: errors

text: are

text: greater

text: H

text: i,

text: given

text: that

text: the

text: peculiar

text: velocity

text: and

text: bulk

text: motions

text: play

text: than

text: dex,

text: the

text: error

text: estimates

text: can

text: be

text: far

text: from

text: true

text: for

text: a

text: role

text: in

text: the

text: kinematics

text: of

text: the

text: absorbers.

text: Moreover,

text: studies

text: single

text: saturated

text: lines

text: and

text: one

text: should

text: treat

text: the

text: errors

text: with

text: of

text: close

text: QSO

text: pairs

text: show

text: that

text: H

text: i

text: and

text: C

text: iv

text: display

text: a

text: diﬀerent

text: caution

text: (see

text: the

text: documents

text: provided

text: with

text: VPFIT

text: for

text: more

text: small-scale

text: structure

text: It

text: has

text: also

text: been

text: found

text: that

text: there

text: details,

text: in

text: particular

text: Chapter

text: While

text: the

text: decomposition

text: is

text: a

text: velocity

text: diﬀerence

text: at

text: km

text: s

text: between

text: the

text: centroids

text: of

text: absorption

text: features

text: depends

text: on

text: the

text: local

text: S/N

text: and

text: res-

text: of

text: H

text: i

text: and

text: C

text: iv

text: olution,

text: especially

text: b

text: parameters,

text: the

text: total

text: column

text: density

text: During

text: the

text: simultaneous

text: ﬁt

text: of

text: diﬀerent

text: transitions

text: of

text: integrated

text: over

text: a

text: given

text: velocity

text: range

text: is

text: in

text: general

text: more

text: se-

text: the

text: same

text: ions,

text: we

text: have

text: often

text: adjusted

text: a

text: small

text: amount

text: of

text: the

text: curely

text: determined.

text: MNRAS

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: least τ. It has been shown in [19] by the ﬁrst two authors that the binary). In fact, the POSSLP lower bound for the cost problem cost problem can be decided in PSPACE. The starting point of this is strongly based on the POSSLP-hardness of POSPARIKH [19, paper is the question left open in [19] whether this PSPACE-upper Prop. 5]. This tight relationship between the two classes of prob- bound can be improved. lems is our main motivation for studying in the second part of this Our ﬁrst contribution is to answer this question positively: we paper the complexity of BITPARIKH and POSPARIKH also for other show that the cost problem belongs to the counting hierarchy (CH). variants: Instead of a DFA, one can specify the language by an NFA The counting hierarchy is deﬁned similarly to the polynomial-time or even a context-free grammar (CFG). Indeed, Kopczyn´ski [26] hierarchy using counting quantiﬁers, see [4] or Section for more recently asked about the complexity of computing the number of details. It is contained in PSPACE and this inclusion is believed words with a given Parikh image accepted by a CFG. Our results on to be strict. In recent years, several numerical problems, for which the complexity of POSPARIKH are collected in Table and similar only PSPACE upper bounds had been known, have been shown to results also hold for BITPARIKH. As the table shows, the complex- be in CH. Two of the most important and fundamental problems ity may depend on the encoding of the numbers in the Parikh vector of this kind are POSSLP and BITSLP: POSSLP is the problem (unary or binary) and the size of the alphabet (unary alphabet, ﬁxed − × whether a given arithmetic circuit over the operations +, and alphabet or a variable alphabet that is part of the input). evaluates to a positive number, and BITSLP asks whether a certain Perhaps remarkably, we show that POSPARIKH for DFA over bit of the computed number is equal to 1. Note that an arithmetic a two-letter alphabet and Parikh vectors encoded in binary is hard circuit with n gates can evaluate to a number in the order of 22n; for POSMATPOW. The latter problem was recently introduced by hence the number of output bits can be exponential and a certain Galby, Ouaknine and Worrell [17] and asks, given a square integer ∈ Z × Z × → Z bit of the output number can be speciﬁed with polynomially many matrix M m m, a linear function f : m m with integer ≥ bits. In addition to the PSPACE upper bound, it has been shown coefﬁcients, and a positive integer n, whether f(Mn) 0, where in [19] that the cost problem is hard for both POSSLP and PP all numbers in M, f and n are encoded in binary. Note that the (probabilistic polynomial time). entries of Mn are generally of size exponential in the size of n. It In order to show that the cost problem belongs to CH, we iden- is shown in [17] that POSMATPOW can be decided in polynomial tify a counting problem for certain words accepted by a determinis- time for ﬁxed dimension m = 2. The same holds for m = 3 tic ﬁnite-state automaton as the core underlying problem and show provided that M is given in unary [17]. The general POSMATPOW its membership in CH. Relating to our previous example in Figure , problem is in CH; in fact, it is is reducible to POSSLP, but the observe that any path that reaches the state t induces a function p complexity of POSMATPOW is left open in [17]. In particular, it is mapping every transition t to the number of times t is traversed not known whether POSMATPOW is easier to decide than POSSLP. i i along this path. In particular, given such a function p we can eas- Our result that POSPARIKH is POSMATPOW-hard already for a ily check whether it exceeds a certain time budget and compute the ﬁxed-size alphabet while POSSLP-hardness seems to require an probability of a path with the induced function p. Thus, viewing alphabet of variable size [19] could be seen as an indication that a cost chain as a deterministic ﬁnite-state automaton whose edges POSMATPOW is easier to decide than POSSLP. are labelled by alphabet symbols t , this observation gives rise to 1.1 Related Work i the following two counting problems for words that are deﬁned The problems studied in this paper lie at the intersection of prob- analAogously to POSSLP and BITSLP: For a ﬁnite-state automa- abilistic veriﬁcation, automata theory, enumerative combinatorics ton over a ﬁniNte alphabet Σ and a PAarikh vector p (i.e., a map- and computational complexity. Hence, there is a large body of re- ping from ΣAto ) we denote by N( , p) the number of words lated work that we brieﬂy discuss here. accepted by whose Parikh image is p. Then BITPARIKH is the A problem of computing a certain bit of the number N( , p) for a Probabilistic Veriﬁcation. Over the last decade and in particu- A given ﬁnite-state automaton and a Parikh vector p encoded in lar in recent years, there has been strong interest in extensions binary. Further, POSPARIKH is the problem of checking whether of Markov chains and Markov decision processes (MDPs) with A B A B N( , p) > N( , p) for two given automata and (over the (multi-dimensional) weights. Laroussinie and Sproston were the same alphabet) and a Parikh vector p encoded in binary. We prove ﬁrst to show that model checking PCTL on cost chains, a generali- that BITPARIKH and POSPARIKH both belong to the counting hier- sation of the cost problem, is NP-hard and in EXPTIME [30]; the archy if the input automata are deterministic. The main ingredient lower bound has recently been improved to PP in [20]. Qualitative of our proof is the so-called BEST theorem which gives a formula aspects of quantile problems in weighted MDPs where the proba- for the number of Eulerian circuits in a directed graph. From the bility threshold τ is either 0 or 1 have been studied by Ummels and A BEST theorem we derive a formula for the number N( , p). In Baier in [39], and iterative linear programming based approaches addition, based on techniques introduced in [3, 21], we develop for solving reward quantiles have been described in [5]. There is a toolbox for showing membership of numerical problems in the also a large body of work on synthesising strategies for weighted counting hierarchy. This enables us to evaluate the formula for MDPs that ensure both worst case as well as expected value guar- A N( , p) in the counting hierarchy. We then reduce the cost prob- antees [12, 14, 15, 33]; see [34] for a survey on such beyond-worst- lem for Markov chains to the problem of comparing two numbers, case-analysis problems. In addition, some other POSSLP-hard nu- A one of which involves N( , p) for a certain deterministic ﬁnite merical problems have recently been discovered, for instance the A state automaton and Parikh vector p encoded in binary. Since problem of ﬁnding mixed strategy proﬁles close to exact Nash equi- single bits of this number can be computed in CH, we ﬁnally ob- libria in three-person games [16] or the model-checking problem of tain our main result: The cost problem belongs to CH. To the best interval Markov chains against unambiguous Bu¨chi automata [9]. of our knowledge, the cost problem and POSPARIKH (for DFA with These problems also belong to the counting hierarchy – it would be Parikh vectors encoded in binary) are the only known natural prob- interesting to investigate whether they are also PP-hard. lems, besides BITSLP, which are (i) POSSLP-hard, (ii) PP-hard, Counting Paths. We use the BEST theorem in the proofs of our and (iii) belong to the counting hierarchy. In particular, whilst being CH upper bounds for BITPARIKH and POSPARIKH (for DFA with decidable in CH, both problems seem to be harder than POSSLP: Parikh vectors encoded in binary) in order to count the number of for the latter problem, no nontrivial lower bound is known. Eulerian circuits in a directed multi-graph. This multi-graph is suc- As discussed above, the cost problem is closely related to BIT- cinctly given: There may be exponentially many edges between PARIKH and POSPARIKH (for DFA and Parikh vectors encoded in two nodes. For an explicitly given directed graph, the BEST the- 2 2020/5/28

text: least

label: paragraph

text: τ.

text: It

text: has

text: been

text: shown

text: in

text: by

text: the

text: ﬁrst

text: two

text: authors

text: that

text: the

text: binary).

text: In

text: fact,

text: the

text: POSSLP

text: lower

text: bound

text: for

text: the

text: cost

text: problem

text: cost

text: problem

text: can

text: be

text: decided

text: in

text: PSPACE.

text: The

text: starting

text: point

text: of

text: this

text: is

text: strongly

text: based

text: on

text: the

text: POSSLP-hardness

text: of

text: POSPARIKH

text: paper

text: is

text: the

text: question

text: left

text: open

text: in

text: whether

text: this

text: PSPACE-upper

text: Prop.

text: This

text: tight

text: relationship

text: between

text: the

text: two

text: classes

text: of

text: prob-

text: bound

text: can

text: be

text: improved.

text: lems

text: is

text: our

text: main

text: motivation

text: for

text: studying

text: in

text: the

text: second

text: part

text: of

text: this

text: Our

text: ﬁrst

text: contribution

text: is

text: to

text: answer

text: this

text: question

text: positively:

text: we

text: paper

text: the

text: complexity

text: of

text: BITPARIKH

text: and

text: POSPARIKH

text: also

text: for

text: other

text: show

text: that

text: the

text: cost

text: problem

text: belongs

text: to

text: the

text: counting

text: hierarchy

text: (CH).

text: variants:

text: Instead

text: of

text: a

text: DFA,

text: one

text: can

text: specify

text: the

text: language

text: by

text: an

text: NFA

text: The

text: counting

text: hierarchy

text: is

text: deﬁned

text: similarly

text: to

text: the

text: polynomial-time

text: or

text: even

text: a

text: context-free

text: grammar

text: (CFG).

text: Indeed,

text: Kopczyn´ski

text: hierarchy

text: using

text: counting

text: quantiﬁers,

text: see

text: or

text: Section

text: for

text: more

text: recently

text: asked

text: about

text: the

text: complexity

text: of

text: computing

text: the

text: number

text: of

text: details.

text: It

text: is

text: contained

text: in

text: PSPACE

text: and

text: this

text: inclusion

text: is

text: believed

text: words

text: with

text: a

text: given

text: Parikh

text: image

text: accepted

text: by

text: a

text: CFG.

text: Our

text: results

text: on

text: to

text: be

text: strict.

text: In

text: recent

text: years,

text: several

text: numerical

text: problems,

text: for

text: which

text: the

text: complexity

text: of

text: POSPARIKH

text: are

text: collected

text: in

text: Table

text: and

text: similar

text: only

text: PSPACE

text: upper

text: bounds

text: had

text: been

text: known,

text: have

text: been

text: shown

text: to

text: results

text: also

text: hold

text: for

text: BITPARIKH.

text: As

text: the

text: table

text: shows,

text: the

text: complex-

text: be

text: in

text: CH.

text: Two

text: of

text: the

text: most

text: important

text: and

text: fundamental

text: problems

text: ity

text: may

text: depend

text: on

text: the

text: encoding

text: of

text: the

text: numbers

text: in

text: the

text: Parikh

text: vector

text: of

text: this

text: kind

text: are

text: POSSLP

text: and

text: BITSLP:

text: POSSLP

text: is

text: the

text: problem

text: (unary

text: or

text: binary)

text: and

text: the

text: size

text: of

text: the

text: alphabet

text: (unary

text: alphabet,

text: ﬁxed

text: whether

text: a

text: given

text: arithmetic

text: circuit

text: over

text: the

text: operations

text: and

text: alphabet

text: or

text: a

text: variable

text: alphabet

text: that

text: is

text: part

text: of

text: the

text: input).

text: evaluates

text: to

text: a

text: positive

text: number,

text: and

text: BITSLP

text: asks

text: whether

text: a

text: certain

text: Perhaps

text: remarkably,

text: we

text: show

text: that

text: POSPARIKH

text: for

text: DFA

text: over

text: bit

text: of

text: the

text: computed

text: number

text: is

text: equal

text: to

text: Note

text: that

text: an

text: arithmetic

text: a

text: two-letter

text: alphabet

text: and

text: Parikh

text: vectors

text: encoded

text: in

text: binary

text: is

text: hard

text: circuit

text: with

text: n

text: gates

text: can

text: evaluate

text: to

text: a

text: number

text: in

text: the

text: order

text: of

text: for

text: POSMATPOW.

text: The

text: latter

text: problem

text: was

text: recently

text: introduced

text: by

text: hence

text: the

text: number

text: of

text: output

text: bits

text: can

text: be

text: exponential

text: and

text: a

text: certain

text: Galby,

text: Ouaknine

text: and

text: Worrell

text: and

text: asks,

text: given

text: a

text: square

text: integer

text: Z

text: Z

text: Z

text: bit

text: of

text: the

text: output

text: number

text: can

text: be

text: speciﬁed

text: with

text: polynomially

text: many

text: matrix

text: M

text: m

text: m,

text: a

text: linear

text: function

text: f

text: m

text: m

text: with

text: integer

text: bits.

text: In

text: addition

text: to

text: the

text: PSPACE

text: upper

text: bound,

text: it

text: has

text: been

text: shown

text: coefﬁcients,

text: and

text: a

text: positive

text: integer

text: n,

text: whether

text: f(Mn)

text: where

text: in

text: that

text: the

text: cost

text: problem

text: is

text: hard

text: for

text: both

text: POSSLP

text: and

text: PP

text: all

text: numbers

text: in

text: M,

text: f

text: and

text: n

text: are

text: encoded

text: in

text: binary.

text: Note

text: that

text: the

text: (probabilistic

text: polynomial

text: time).

text: entries

text: of

text: Mn

text: are

text: generally

text: of

text: size

text: exponential

text: in

text: the

text: size

text: of

text: n.

text: It

text: In

text: order

text: to

text: show

text: that

text: the

text: cost

text: problem

text: belongs

text: to

text: CH,

text: we

text: iden-

text: is

text: shown

text: in

text: that

text: POSMATPOW

text: can

text: be

text: decided

text: in

text: polynomial

text: tify

text: a

text: counting

text: problem

text: for

text: certain

text: words

text: accepted

text: by

text: a

text: determinis-

text: time

text: for

text: ﬁxed

text: dimension

text: m

text: The

text: same

text: holds

text: for

text: m

text: tic

text: ﬁnite-state

text: automaton

text: as

text: the

text: core

text: underlying

text: problem

text: and

text: show

text: provided

text: that

text: M

text: is

text: given

text: in

text: unary

text: The

text: general

text: POSMATPOW

text: its

text: membership

text: in

text: CH.

text: Relating

text: to

text: our

text: previous

text: example

text: in

text: Figure

text: problem

text: is

text: in

text: CH;

text: in

text: fact,

text: it

text: is

text: is

text: reducible

text: to

text: POSSLP,

text: but

text: the

text: observe

text: that

text: any

text: path

text: that

text: reaches

text: the

text: state

text: t

text: induces

text: a

text: function

text: p

text: complexity

text: of

text: POSMATPOW

text: is

text: left

text: open

text: in

text: In

text: particular,

text: it

text: is

text: mapping

text: every

text: transition

text: t

text: to

text: the

text: number

text: of

text: times

text: t

text: is

text: traversed

text: not

text: known

text: whether

text: POSMATPOW

text: is

text: easier

text: to

text: decide

text: than

text: POSSLP.

text: i

text: i

text: along

text: this

text: path.

text: In

text: particular,

text: given

text: such

text: a

text: function

text: p

text: we

text: can

text: eas-

text: Our

text: result

text: that

text: POSPARIKH

text: is

text: POSMATPOW-hard

text: already

text: for

text: a

text: ily

text: check

text: whether

text: it

text: exceeds

text: a

text: certain

text: time

text: budget

text: and

text: compute

text: the

text: ﬁxed-size

text: alphabet

text: while

text: POSSLP-hardness

text: seems

text: to

text: require

text: an

text: probability

text: of

text: a

text: path

text: with

text: the

text: induced

text: function

text: p.

text: Thus,

text: viewing

text: alphabet

text: of

text: variable

text: size

text: could

text: be

text: seen

text: as

text: an

text: indication

text: that

text: a

text: cost

text: chain

text: as

text: a

text: deterministic

text: ﬁnite-state

text: automaton

text: whose

text: edges

text: POSMATPOW

text: is

text: easier

text: to

text: decide

text: than

text: POSSLP.

text: are

text: labelled

text: by

text: alphabet

text: symbols

text: t

text: this

text: observation

text: gives

text: rise

text: to

text: Related

text: Work

text: i

text: the

text: following

text: two

text: counting

text: problems

text: for

text: words

text: that

text: are

text: deﬁned

text: The

text: problems

text: studied

text: in

text: this

text: paper

text: lie

text: at

text: the

text: intersection

text: of

text: prob-

text: analAogously

text: to

text: POSSLP

text: and

text: BITSLP:

text: For

text: a

text: ﬁnite-state

text: automa-

text: abilistic

text: veriﬁcation,

text: automata

text: theory,

text: enumerative

text: combinatorics

text: ton

text: over

text: a

text: ﬁniNte

text: alphabet

text: Σ

text: and

text: a

text: PAarikh

text: vector

text: p

text: (i.e.,

text: a

text: map-

text: and

text: computational

text: complexity.

text: Hence,

text: there

text: is

text: a

text: large

text: body

text: of

text: re-

text: ping

text: from

text: ΣAto

text: we

text: denote

text: by

text: N(

text: p)

text: the

text: number

text: of

text: words

text: lated

text: work

text: that

text: we

text: brieﬂy

text: discuss

text: here.

text: accepted

text: by

text: whose

text: Parikh

text: image

text: is

text: p.

text: Then

text: BITPARIKH

text: is

text: the

text: A

text: problem

text: of

text: computing

text: a

text: certain

text: bit

text: of

text: the

text: number

text: N(

text: p)

text: for

text: a

text: Probabilistic

text: Veriﬁcation.

text: Over

text: the

text: last

text: decade

text: and

text: in

text: particu-

text: A

text: given

text: ﬁnite-state

text: automaton

text: and

text: a

text: Parikh

text: vector

text: p

text: encoded

text: in

text: lar

text: in

text: recent

text: years,

text: there

text: has

text: been

text: strong

text: interest

text: in

text: extensions

text: binary.

text: Further,

text: POSPARIKH

text: is

text: the

text: problem

text: of

text: checking

text: whether

text: of

text: Markov

text: chains

text: and

text: Markov

text: decision

text: processes

text: (MDPs)

text: with

text: A

text: B

text: A

text: B

text: N(

text: p)

text: N(

text: p)

text: for

text: two

text: given

text: automata

text: and

text: (over

text: the

text: (multi-dimensional)

text: weights.

text: Laroussinie

text: and

text: Sproston

text: were

text: the

text: same

text: alphabet)

text: and

text: a

text: Parikh

text: vector

text: p

text: encoded

text: in

text: binary.

text: We

text: prove

text: ﬁrst

text: to

text: show

text: that

text: model

text: checking

text: PCTL

text: on

text: cost

text: chains,

text: a

text: generali-

text: that

text: BITPARIKH

text: and

text: POSPARIKH

text: both

text: belong

text: to

text: the

text: counting

text: hier-

text: sation

text: of

text: the

text: cost

text: problem,

text: is

text: NP-hard

text: and

text: in

text: EXPTIME

text: the

text: archy

text: if

text: the

text: input

text: automata

text: are

text: deterministic.

text: The

text: main

text: ingredient

text: lower

text: bound

text: has

text: recently

text: been

text: improved

text: to

text: PP

text: in

text: Qualitative

text: of

text: our

text: proof

text: is

text: the

text: so-called

text: BEST

text: theorem

text: which

text: gives

text: a

text: formula

text: aspects

text: of

text: quantile

text: problems

text: in

text: weighted

text: MDPs

text: where

text: the

text: proba-

text: for

text: the

text: number

text: of

text: Eulerian

text: circuits

text: in

text: a

text: directed

text: graph.

text: From

text: the

text: bility

text: threshold

text: τ

text: is

text: either

text: or

text: have

text: been

text: studied

text: by

text: Ummels

text: and

text: A

text: BEST

text: theorem

text: we

text: derive

text: a

text: formula

text: for

text: the

text: number

text: N(

text: p).

text: In

text: Baier

text: in

text: and

text: iterative

text: linear

text: programming

text: based

text: approaches

text: addition,

text: based

text: on

text: techniques

text: introduced

text: in

text: we

text: develop

text: for

text: solving

text: reward

text: quantiles

text: have

text: been

text: described

text: in

text: There

text: is

text: a

text: toolbox

text: for

text: showing

text: membership

text: of

text: numerical

text: problems

text: in

text: the

text: also

text: a

text: large

text: body

text: of

text: work

text: on

text: synthesising

text: strategies

text: for

text: weighted

text: counting

text: hierarchy.

text: This

text: enables

text: us

text: to

text: evaluate

text: the

text: formula

text: for

text: MDPs

text: that

text: ensure

text: both

text: worst

text: case

text: as

text: well

text: as

text: expected

text: value

text: guar-

text: A

text: N(

text: p)

text: in

text: the

text: counting

text: hierarchy.

text: We

text: then

text: reduce

text: the

text: cost

text: prob-

text: antees

text: see

text: for

text: a

text: survey

text: on

text: such

text: beyond-worst-

text: lem

text: for

text: Markov

text: chains

text: to

text: the

text: problem

text: of

text: comparing

text: two

text: numbers,

text: case-analysis

text: problems.

text: In

text: addition,

text: some

text: other

text: POSSLP-hard

text: nu-

text: A

text: one

text: of

text: which

text: involves

text: N(

text: p)

text: for

text: a

text: certain

text: deterministic

text: ﬁnite

text: merical

text: problems

text: have

text: recently

text: been

text: discovered,

text: for

text: instance

text: the

text: A

text: state

text: automaton

text: and

text: Parikh

text: vector

text: p

text: encoded

text: in

text: binary.

text: Since

text: problem

text: of

text: ﬁnding

text: mixed

text: strategy

text: proﬁles

text: close

text: to

text: exact

text: Nash

text: equi-

text: single

text: bits

text: of

text: this

text: number

text: can

text: be

text: computed

text: in

text: CH,

text: we

text: ﬁnally

text: ob-

text: libria

text: in

text: three-person

text: games

text: or

text: the

text: model-checking

text: problem

text: of

text: tain

text: our

text: main

text: result:

text: The

text: cost

text: problem

text: belongs

text: to

text: CH.

text: To

text: the

text: best

text: interval

text: Markov

text: chains

text: against

text: unambiguous

text: Bu¨chi

text: automata

text: of

text: our

text: knowledge,

text: the

text: cost

text: problem

text: and

text: POSPARIKH

text: (for

text: DFA

text: with

text: These

text: problems

text: also

text: belong

text: to

text: the

text: counting

text: hierarchy

text: it

text: would

text: be

text: Parikh

text: vectors

text: encoded

text: in

text: binary)

text: are

text: the

text: only

text: known

text: natural

text: prob-

text: interesting

text: to

text: investigate

text: whether

text: they

text: are

text: also

text: PP-hard.

text: lems,

text: besides

text: BITSLP,

text: which

text: are

text: (i)

text: POSSLP-hard,

text: (ii)

text: PP-hard,

text: Counting

text: Paths.

text: We

text: use

text: the

text: BEST

text: theorem

text: in

text: the

text: proofs

text: of

text: our

text: and

text: (iii)

text: belong

text: to

text: the

text: counting

text: hierarchy.

text: In

text: particular,

text: whilst

text: being

text: CH

text: upper

text: bounds

text: for

text: BITPARIKH

text: and

text: POSPARIKH

text: (for

text: DFA

text: with

text: decidable

text: in

text: CH,

text: both

text: problems

text: seem

text: to

text: be

text: harder

text: than

text: POSSLP:

text: Parikh

text: vectors

text: encoded

text: in

text: binary)

text: in

text: order

text: to

text: count

text: the

text: number

text: of

text: for

text: the

text: latter

text: problem,

text: no

text: nontrivial

text: lower

text: bound

text: is

text: known.

text: Eulerian

text: circuits

text: in

text: a

text: directed

text: multi-graph.

text: This

text: multi-graph

text: is

text: suc-

text: As

text: discussed

text: above,

text: the

text: cost

text: problem

text: is

text: closely

text: related

text: to

text: BIT-

text: cinctly

text: given:

text: There

text: may

text: be

text: exponentially

text: many

text: edges

text: between

text: PARIKH

text: and

text: POSPARIKH

text: (for

text: DFA

text: and

text: Parikh

text: vectors

text: encoded

text: in

text: two

text: nodes.

text: For

text: an

text: explicitly

text: given

text: directed

text: graph,

text: the

text: BEST

text: the-


text: Proposition 24. The compressed word problem for unary NFA is in NL. Hence, POSPARIKH is in NL for unary NFA with Parikh vectors encoded in binary. A { } Proof. Let = (Q, a , q , F, ∆) be the given unary NFA, and ∈ N 0 let n be given in binary. We claim that, given two states ∈ ∈ N p , p Q and a number c whose binary representation is 1 2 of size logarithmic in the input size, we can check in NL whether −→ p c p holds. To prove the claim, consider the directed graph G 1 2 × { } over vertices Q 0, . . . , c , with an edge from (q , i) to (q , j) −→ 1 2 if and only if q 1 q and j = i + 1. The graph G can be 1 2 −→ computed by a logspace transducer. Then p c p holds if and 1 2 only if (p , c) is reachable from (p , 0) in G. The claim follows as 2 1 graph reachability is in NL. Now we give an NL algorithm for the compressed word prob- ∈ lem. If n < m2 then guess q F and check, using the claim −→ f ≥ above, in NL whether q n q . If n m2 we use Lemma 23 0 ∈f ∈ ∈ { } as follows. We run over all q Q, q F, b 1, . . . , m , ∈ { − − − f} and a m2 b 1, . . . , m2 2 (all four values can be ∈ N stored in logspace), and check (i) whether n a + b and (ii) −−−−→ −→ −−−−−−−−→ q m 1 q b q a (m 1) q holds. Condition (i) can be checked 0 f in logspace (as in the proof of Proposition 18), and condition (ii) can be checked in NL by the above claim. It follows that POSPARIKH is in NL for unary NFA with Parikh A B ∈ N vectors encoded in binary: Given NFA , and n in binary, A B we have N( , n) > N( , n) (where we identity the mapping p : { } → N A a with the single number p(a)) if and only if N( , n) = 1 B ∈ A and N( , n) = 0, which holds if and only if an L( ) and (cid:54)∈ B an L( ). Since NL is closed under complement, the latter condition can be checked in NL. Proof of Part (iii). The P-upper bound is clear since the word prob- lem for CFG is in P. Regarding the DP-upper bound, Huynh [23] shows that the uniform word problem for context-free grammars { } over a singleton alphabet a is NP-complete; where the input word an is given by the binary representation of n. Given CFG A B { } A B , over a and a number n, we have that N( , n) > N( , n) ∈ A (cid:54)∈ B if and only if an L( ) and an L( ). The latter is a decision problem in DP by the above result from [23]. Let us now turn to the lower bounds. For the P-lower bound, we reduce from the (cid:15)-membership problem for context-free grammars, which is known to be P-hard even for grammars with no terminal A B symbol [18, Prob. A.7.2]. Let be such a grammar, and let be B ∅ A B such that L( ) = . Then N( , 0) > N( , 0) if and only if ∈ A (cid:15) L( ). For the DP-lower bound, the following problem is DP- complete: Given two instances (s, v , . . . , v ), (t, w , . . . , w ) of 1 m 1 n SUBSETSUM (all numbers s, v , . . . , v , t, w , . . . , w are binary 1 m 1 n encoded), does the following hold? • ∈ { } · · · There exist a , . . . , a 0, 1 with s = a v + +a v . • 1 ∈ {m } (cid:54) · · ·1 1 m m For all b , . . . , b 0, 1 , t = b w + + b w . 1 n 1 1 n n DP-hardness of this problem follows by a reduction from the problem SAT-UNSAT (one can take the standard reduction from ≥ SAT to SUBSETSUM). Let us assume that s t (if t > s we A can argue similarly). We then construct in logspace CFG and B A ··· such that pro∈du{ces a}ll worBds of the form aa1v1+ +amvm, where a , . . . , a 0, 1 and produces all words of the form − 1 ··· m ∈ { } a(s∈t)+b1Aw1+\ +bBnwn, where b1, . . . , bm 0, 1 . We t∈hen{hav}e as L( ) L( ) if and only if there are a , . . . , a 0, 1 · · · (cid:54) 1 · · · m with s = a v + + a v but t = b w + + b w for all 1∈ 1{ } m m 1 1 n n b , . . . , b 0, 1 . 1 n 15 2020/5/28 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proposition

text: The

text: compressed

text: word

text: problem

text: for

text: unary

text: NFA

text: is

text: in

text: NL.

text: Hence,

text: POSPARIKH

text: is

text: in

text: NL

text: for

text: unary

text: NFA

text: with

text: Parikh

text: vectors

text: encoded

text: in

text: binary.

text: A

text: Proof.

text: Let

text: (Q,

text: a

text: q

text: F,

text: be

text: the

text: given

text: unary

text: NFA,

text: and

text: N

text: let

text: n

text: be

text: given

text: in

text: binary.

text: We

text: claim

text: that,

text: given

text: two

text: states

text: N

text: p

text: p

text: Q

text: and

text: a

text: number

text: c

text: whose

text: binary

text: representation

text: is

text: of

text: size

text: logarithmic

text: in

text: the

text: input

text: size,

text: we

text: can

text: check

text: in

text: NL

text: whether

text: p

text: c

text: p

text: holds.

text: To

text: prove

text: the

text: claim,

text: consider

text: the

text: directed

text: graph

text: G

text: over

text: vertices

text: Q

text: c

text: with

text: an

text: edge

text: from

text: (q

text: i)

text: to

text: (q

text: j)

text: if

text: and

text: only

text: if

text: q

text: q

text: and

text: j

text: i

text: The

text: graph

text: G

text: can

text: be

text: computed

text: by

text: a

text: logspace

text: transducer.

text: Then

text: p

text: c

text: p

text: holds

text: if

text: and

text: only

text: if

text: (p

text: c)

text: is

text: reachable

text: from

text: (p

text: in

text: G.

text: The

text: claim

text: follows

text: as

text: graph

text: reachability

text: is

text: in

text: NL.

text: Now

text: we

text: give

text: an

text: NL

text: algorithm

text: for

text: the

text: compressed

text: word

text: prob-

text: lem.

text: If

text: n

text: then

text: guess

text: q

text: F

text: and

text: check,

text: using

text: the

text: claim

text: f

text: above,

text: in

text: NL

text: whether

text: q

text: n

text: q

text: If

text: n

text: we

text: use

text: Lemma

text: ∈f

text: as

text: follows.

text: We

text: run

text: over

text: all

text: q

text: Q,

text: q

text: F,

text: b

text: m

text: f}

text: and

text: a

text: b

text: (all

text: four

text: values

text: can

text: be

text: N

text: stored

text: in

text: logspace),

text: and

text: check

text: (i)

text: whether

text: n

text: a

text: b

text: and

text: (ii)

text: q

text: m

text: q

text: b

text: q

text: a

text: (m

text: q

text: holds.

text: Condition

text: (i)

text: can

text: be

text: checked

text: f

text: in

text: logspace

text: (as

text: in

text: the

text: proof

text: of

text: Proposition

text: and

text: condition

text: (ii)

text: can

text: be

text: checked

text: in

text: NL

text: by

text: the

text: above

text: claim.

text: It

text: follows

text: that

text: POSPARIKH

text: is

text: in

text: NL

text: for

text: unary

text: NFA

text: with

text: Parikh

text: A

text: B

text: N

text: vectors

text: encoded

text: in

text: binary:

text: Given

text: NFA

text: and

text: n

text: in

text: binary,

text: A

text: B

text: we

text: have

text: N(

text: n)

text: N(

text: n)

text: (where

text: we

text: identity

text: the

text: mapping

text: p

text: N

text: A

text: a

text: with

text: the

text: single

text: number

text: p(a))

text: if

text: and

text: only

text: if

text: N(

text: n)

text: B

text: A

text: and

text: N(

text: n)

text: which

text: holds

text: if

text: and

text: only

text: if

text: an

text: L(

text: and

text: B

text: an

text: L(

text: Since

text: NL

text: is

text: closed

text: under

text: complement,

text: the

text: latter

text: condition

text: can

text: be

text: checked

text: in

text: NL.

text: Proof

text: of

text: Part

text: (iii).

text: The

text: P-upper

text: bound

text: is

text: clear

text: since

text: the

text: word

text: prob-

text: lem

text: for

text: CFG

text: is

text: in

text: P.

text: Regarding

text: the

text: DP-upper

text: bound,

text: Huynh

text: shows

text: that

text: the

text: uniform

text: word

text: problem

text: for

text: context-free

text: grammars

text: over

text: a

text: singleton

text: alphabet

text: a

text: is

text: NP-complete;

text: where

text: the

text: input

text: word

text: an

text: is

text: given

text: by

text: the

text: binary

text: representation

text: of

text: n.

text: Given

text: CFG

text: A

text: B

text: A

text: B

text: over

text: a

text: and

text: a

text: number

text: n,

text: we

text: have

text: that

text: N(

text: n)

text: N(

text: n)

text: A

text: B

text: if

text: and

text: only

text: if

text: an

text: L(

text: and

text: an

text: L(

text: The

text: latter

text: is

text: a

text: decision

text: problem

text: in

text: DP

text: by

text: the

text: above

text: result

text: from

text: Let

text: us

text: now

text: turn

text: to

text: the

text: lower

text: bounds.

text: For

text: the

text: P-lower

text: bound,

text: we

text: reduce

text: from

text: the

text: problem

text: for

text: context-free

text: grammars,

text: which

text: is

text: known

text: to

text: be

text: P-hard

text: even

text: for

text: grammars

text: with

text: no

text: terminal

text: A

text: B

text: symbol

text: Prob.

text: Let

text: be

text: such

text: a

text: grammar,

text: and

text: let

text: be

text: B

text: A

text: B

text: such

text: that

text: L(

text: Then

text: N(

text: N(

text: if

text: and

text: only

text: if

text: A

text: L(

text: For

text: the

text: DP-lower

text: bound,

text: the

text: following

text: problem

text: is

text: DP-

text: complete:

text: Given

text: two

text: instances

text: (s,

text: v

text: v

text: (t,

text: w

text: w

text: of

text: m

text: n

text: SUBSETSUM

text: (all

text: numbers

text: s,

text: v

text: v

text: t,

text: w

text: w

text: are

text: binary

text: m

text: n

text: encoded),

text: does

text: the

text: following

text: hold?

text: There

text: exist

text: a

text: a

text: with

text: s

text: a

text: v

text: +a

text: v

text: {m

text: ·1

text: m

text: m

text: For

text: all

text: b

text: b

text: t

text: b

text: w

text: b

text: w

text: n

text: n

text: n

text: DP-hardness

text: of

text: this

text: problem

text: follows

text: by

text: a

text: reduction

text: from

text: the

text: problem

text: SAT-UNSAT

text: (one

text: can

text: take

text: the

text: standard

text: reduction

text: from

text: SAT

text: to

text: SUBSETSUM).

text: Let

text: us

text: assume

text: that

text: s

text: t

text: (if

text: t

text: s

text: we

text: A

text: can

text: argue

text: similarly).

text: We

text: then

text: construct

text: in

text: logspace

text: CFG

text: and

text: B

text: A

text: such

text: that

text: pro∈du{ces

text: a}ll

text: worBds

text: of

text: the

text: form

text: +amvm,

text: where

text: a

text: a

text: and

text: produces

text: all

text: words

text: of

text: the

text: form

text: m

text: +bBnwn,

text: where

text: bm

text: We

text: t∈hen{hav}e

text: as

text: L(

text: L(

text: if

text: and

text: only

text: if

text: there

text: are

text: a

text: a

text: m

text: with

text: s

text: a

text: v

text: a

text: v

text: but

text: t

text: b

text: w

text: b

text: w

text: for

text: all

text: 1∈

text: m

text: m

text: n

text: n

text: b

text: b

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: We say that G is loop-free if G does not have loops. The in-degree and NOT) may also use threshold gates. DLOGTIME-uniformity of v is d+(v) d=ef #t−1(v) (note that the preimage t−1(v) is the means that one can compute in time O(log n) (i) the type of a given set of allGincoming edges for node v) and the out-degree of v is gate of the n-th circuit, and (ii) whether two given gates of the n- d−G(v) d=ef #s−1(v). tahreceirnccuoitdeadrebcyobnintescttreidngbsyoaf lwenirget.hHOer(elo, ggant)e.sIoffwtheedno-nthotcairlclouwit An edge-weighted multi-graph is a tuple→G N= (V, E, s, t, w), threshold gates in this deﬁnition, we obtain DLOGTIME-uniform where (V, E, s, t) is a multi-graph and w: E assigns a weight ≥ AC0. The class NCk (k 1) is the class of all of all languages to every edge. We can deﬁne the ∈ordinary multi-graph G˜ induced that can be decided with a polynomial-size DLOGTIME-uniform by G by replacing every edge e E by k = w(e) many e∈dges circuit family of depth O(logk n), where only Boolean gates of e , . . . , e with s(e ) = s(e) and t(e ) = t(e). For u, v V an1d n ∈k N, deﬁneiN(G, u, v, n) as tihe num−ber of pa−ths in G˜ fDaLn-OinGtTwIoMaEre-uanlilfoowrmedN. DCL1O. GTIME-uniform TC0 is contained in from u to v of length n. Moreover, we set d (v) = d (v) and There are obvious generalization of the above language classes G G˜ d+(v) = d+(v). AC0, TC0, and NCk to function classes. Given two n-bit numbers 2.G3 CompG˜utational Complexity x, y ∈ Z, x + y (resp., x · y) can be computed in DLOGTIME- We assume familiarity with basic complexity classes such as L uniform AC0 (resp., DLOGTIME-u∈niNform TC0) [40]. Even the (deterministic logspace), NL, P, NP, PH (the polynomial time hi- product of n numbers x1, . . . , xn , each of bit-size at most erarchy) and PSPACE. The class DP is the class of all intersections n, and matrix powers An with n given in unary and A of constant K ∩ L with K ∈ NP and L ∈ coNP. Hardness for a complexity dimension can be computed in DLOGTIME-uniform TC0 [2, 21]. class will always refer to logspace reductions. If n is given in binary (and A has again constant dimension) then A counting problem is a function f : Σ∗ → N for a ﬁnite the computation of a certain bit of An can be done in PHPPPPPP [2]. alphabet Σ. A counting class is a set of counting problems. A Finally, computing the determinant of an integer matrix with entries ∗ → N logspace reduction from∗ →a cNounting problem f : Σ to a encoded in binary is in NC2. More details on the counting hierarchy counting problem g: Γ is a logspace computable function (resp., circuit complexity) can be found in [4] (resp., [40]). ∗ → ∗ ∈ ∗ h: Σ Γ such that for all x Σ : f(x) = g(h(x)). Note that 3. A Toolbox for the Counting Hierarchy no post-computation is allowed. Such reductions are also called parsimonious. Hardness for a counting class will always refer to In the subsequent sections, in order to show our CH upper parsimonious logspace reductions. bounds we require some closure results for the counting hierarchy. The counting class #P contains all functions f : Σ∗ → N for These results are based on ideas and results developed in [3, 13], which there exists a non-deterministic polynomial-time Turing ma- which are, however, not sufﬁciently gene(cid:80)ral for our purposes. chine M such that for every x ∈ Σ∗, f(x) is the number of accept- Let B d=ef {0, 1}∗ in the following deﬁnitions. For a k-tuple ing computation paths of M on input x. The class PP (probabilistic x = (x , . . . , x ) ∈ Bk let |x| = k |x |. The following polynomial time) contains all problems A for which there exists a deﬁnition1is a sligkht variant of the deﬁnitioi=n1in [i13] that suits our non-deterministic poly∈nomial-time Turing machine M such that purposes better. Consider a function f : Bk → N that maps a k- for every input x, x A if and only if more than half of all tuple of binary words to a natural number. We say that f is in CH computation paths of M⊆on input x are accepting. By a famous if there exists a polynomial p(n) such that the following holds: result of Toda [38], PH PPP, where PPP is the class of all lan- • For all x ∈ Bk we have f(x) ≤ 22p(|x|). guages that can be decided in deterministic polynomial time with • the help of an oracle from PP. Hence, if a problem is PP-hard, The set of tuples tnhoetnbtehliosncgantobPeHsee(nothaserawsistreonPgHinwdoicualtdiocnotlhlaaptsteh)e. Ipfrowbelemrepdloacees Lf d=ef {(x, i) ∈ Bk × N : the i-th bit of f(x) is equal to 1} in the deﬁnition of #P and PP non-deterministic polynomial-time belongs to CH (here, we ass(cid:81)ume that i is given in binary repre- Turing machines by non-deterministic logspace Turing machines sentation). (dreetsepr.m, innoinst-idceteexrpmoinneisnttiicalp-otilmyneoTmuiariln-sgpamceacThuinriensg),mwaechoinbetasi;nnothne- We also consider mappBings f : kj=1 Dj → N, where the domains classes #L and PL (resp., #PSPACE and PPSPACE; #EXP and D1, . . . , Dk are not . In this case, we assume some standard PEXP). Ladner [29] has shown that a function f belongs to encoding of the elements from D1, . . . , Dk as words over a binary #PSPACE if and only if for a given input x and a binary encoded alphabet. number i the i-th bit of f(x) can be computed in PSPACE. It fol- Lemma 2. If the function f : Bk+1 → N belongs to CH and lows that PPSPACE = PSPACE. It is well known that PP can be p(n) is a po(cid:88)lynomial, then also the functions g(cid:89): Bk → N and also deﬁned as the class of all languages L f∈or which there ex- h: Bk → N belong to CH, where ist two #P-functions f and f such that x L if and only if 1 2 f1(x) > f2(x) and similarly for PL and PEXP≥. g(x) = f(x, y) and h(x) = f(x, y). The levels of the counting hierarchy Cp (i 0) are inductively ∈{ } | | ∈{ } | | dacecﬁenpetdedasbfyolaloPwPs:-mCp0ac=hi(cid:83)nPeaansdaCbpio+v1e=wiPthPi aCnpi (otrhaecsleetforofmlanCgpu)agfoesr Proof. Wye o0n,1lyp(pxro)ve the statement for proyduc0t,s1, pt(hex )proof for all i ≥ 0. Let CH = ≥ Cp be the counting hierarchyi. It is sums is the same. To this end, we follow the arguments from [3] not difﬁcult to show that Ci H0 ⊆i PSPACE, and most complexity showing that BITSLP belongs to the counting hierarchy. As men- (cid:40) tioned in Section , iterated product, i.e., the problem of comput- theorists conjecture that CH PSPACE. Hence, if a problem ing the product of a sequence of binary encoded integers, be- belongs to the counting hierarchy, then the problem is probably not PSPACE-complete. longs to DLOGTIME-uniform TC0. More precisely, there is a The circuit complexity class DLOGTIME-uniform TC0 is DLOGTIME(cid:81)-uniform TC0 circuit family, where the n-th circuit the class of all languages that can be decided with a constant- Cn has n2 many input gates, which are interpreted as n-bit inte- depth polynomial-size DLOGTIME-uniform circuit family of un- gers x1, . . . , xn, and n2 output gates, which evaluate to the bits in bounded fan-in that in addition to normal Boolean gates (AND, OR the product ni=1 xi. Let c be the depth of the circuits Cn, which is a ﬁxed constant. 4 2020/5/28 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: We

text: say

text: that

text: G

text: is

text: loop-free

text: if

text: G

text: does

text: not

text: have

text: loops.

text: The

text: in-degree

text: and

text: NOT)

text: may

text: also

text: use

text: threshold

text: gates.

text: DLOGTIME-uniformity

text: of

text: v

text: is

text: d+(v)

text: d=ef

text: (note

text: that

text: the

text: preimage

text: is

text: the

text: means

text: that

text: one

text: can

text: compute

text: in

text: time

text: O(log

text: n)

text: (i)

text: the

text: type

text: of

text: a

text: given

text: set

text: of

text: allGincoming

text: edges

text: for

text: node

text: v)

text: and

text: the

text: out-degree

text: of

text: v

text: is

text: gate

text: of

text: the

text: n-th

text: circuit,

text: and

text: (ii)

text: whether

text: two

text: given

text: gates

text: of

text: the

text: n-

text: d−G(v)

text: d=ef

text: lwenirget.hHOer(elo,

text: ggant)e.sIoffwtheedno-nthotcairlclouwit

text: An

text: edge-weighted

text: multi-graph

text: is

text: a

text: tuple→G

text: N=

text: (V,

text: E,

text: s,

text: t,

text: w),

text: threshold

text: gates

text: in

text: this

text: deﬁnition,

text: we

text: obtain

text: DLOGTIME-uniform

text: where

text: (V,

text: E,

text: s,

text: t)

text: is

text: a

text: multi-graph

text: and

text: w:

text: E

text: assigns

text: a

text: weight

text: The

text: class

text: NCk

text: (k

text: is

text: the

text: class

text: of

text: all

text: of

text: all

text: languages

text: to

text: every

text: edge.

text: We

text: can

text: deﬁne

text: the

text: ∈ordinary

text: multi-graph

text: G˜

text: induced

text: that

text: can

text: be

text: decided

text: with

text: a

text: polynomial-size

text: DLOGTIME-uniform

text: by

text: G

text: by

text: replacing

text: every

text: edge

text: e

text: E

text: by

text: k

text: w(e)

text: many

text: e∈dges

text: circuit

text: family

text: of

text: depth

text: O(logk

text: n),

text: where

text: only

text: Boolean

text: gates

text: of

text: e

text: e

text: with

text: s(e

text: s(e)

text: and

text: t(e

text: t(e).

text: For

text: u,

text: v

text: V

text: n

text: ∈k

text: N,

text: deﬁneiN(G,

text: u,

text: v,

text: n)

text: as

text: tihe

text: num−ber

text: of

text: pa−ths

text: in

text: G˜

text: fDaLn-OinGtTwIoMaEre-uanlilfoowrmedN.

text: GTIME-uniform

text: is

text: contained

text: in

text: from

text: u

text: to

text: v

text: of

text: length

text: n.

text: Moreover,

text: we

text: set

text: d

text: (v)

text: d

text: (v)

text: and

text: There

text: are

text: obvious

text: generalization

text: of

text: the

text: above

text: language

text: classes

text: G

text: G˜

text: d+(v)

text: d+(v).

text: and

text: NCk

text: to

text: function

text: classes.

text: Given

text: two

text: n-bit

text: numbers

text: CompG˜utational

text: Complexity

text: x,

text: y

text: Z,

text: x

text: y

text: (resp.,

text: x

text: y)

text: can

text: be

text: computed

text: in

text: DLOGTIME-

text: We

text: assume

text: familiarity

text: with

text: basic

text: complexity

text: classes

text: such

text: as

text: L

text: uniform

text: (resp.,

text: DLOGTIME-u∈niNform

text: Even

text: the

text: (deterministic

text: logspace),

text: NL,

text: P,

text: NP,

text: PH

text: (the

text: polynomial

text: time

text: hi-

text: product

text: of

text: n

text: numbers

text: xn

text: each

text: of

text: bit-size

text: at

text: most

text: erarchy)

text: and

text: PSPACE.

text: The

text: class

text: DP

text: is

text: the

text: class

text: of

text: all

text: intersections

text: n,

text: and

text: matrix

text: powers

text: An

text: with

text: n

text: given

text: in

text: unary

text: and

text: A

text: of

text: constant

text: K

text: L

text: with

text: K

text: NP

text: and

text: L

text: coNP.

text: Hardness

text: for

text: a

text: complexity

text: dimension

text: can

text: be

text: computed

text: in

text: DLOGTIME-uniform

text: class

text: will

text: always

text: refer

text: to

text: logspace

text: reductions.

text: If

text: n

text: is

text: given

text: in

text: binary

text: (and

text: A

text: has

text: again

text: constant

text: dimension)

text: then

text: A

text: counting

text: problem

text: is

text: a

text: function

text: f

text: Σ∗

text: N

text: for

text: a

text: ﬁnite

text: the

text: computation

text: of

text: a

text: certain

text: bit

text: of

text: An

text: can

text: be

text: done

text: in

text: PHPPPPPP

text: alphabet

text: Σ.

text: A

text: counting

text: class

text: is

text: a

text: set

text: of

text: counting

text: problems.

text: A

text: Finally,

text: computing

text: the

text: determinant

text: of

text: an

text: integer

text: matrix

text: with

text: entries

text: N

text: logspace

text: reduction

text: from∗

text: →a

text: cNounting

text: problem

text: f

text: Σ

text: to

text: a

text: encoded

text: in

text: binary

text: is

text: in

text: More

text: details

text: on

text: the

text: counting

text: hierarchy

text: counting

text: problem

text: g:

text: Γ

text: is

text: a

text: logspace

text: computable

text: function

text: (resp.,

text: circuit

text: complexity)

text: can

text: be

text: found

text: in

text: (resp.,

text: h:

text: Σ

text: Γ

text: such

text: that

text: for

text: all

text: x

text: Σ

text: f(x)

text: g(h(x)).

text: Note

text: that

text: A

text: Toolbox

text: for

text: the

text: Counting

text: Hierarchy

text: no

text: post-computation

text: is

text: allowed.

text: Such

text: reductions

text: are

text: also

text: called

text: parsimonious.

text: Hardness

text: for

text: a

text: counting

text: class

text: will

text: always

text: refer

text: to

text: In

text: the

text: subsequent

text: sections,

text: in

text: order

text: to

text: show

text: our

text: CH

text: upper

text: parsimonious

text: logspace

text: reductions.

text: bounds

text: we

text: require

text: some

text: closure

text: results

text: for

text: the

text: counting

text: hierarchy.

text: The

text: counting

text: class

text: #P

text: contains

text: all

text: functions

text: f

text: Σ∗

text: N

text: for

text: These

text: results

text: are

text: based

text: on

text: ideas

text: and

text: results

text: developed

text: in

text: which

text: there

text: exists

text: a

text: non-deterministic

text: polynomial-time

text: Turing

text: ma-

text: which

text: are,

text: however,

text: not

text: sufﬁciently

text: for

text: our

text: purposes.

text: chine

text: M

text: such

text: that

text: for

text: every

text: x

text: Σ∗,

text: f(x)

text: is

text: the

text: number

text: of

text: accept-

text: Let

text: B

text: d=ef

text: in

text: the

text: following

text: deﬁnitions.

text: For

text: a

text: k-tuple

text: ing

text: computation

text: paths

text: of

text: M

text: on

text: input

text: x.

text: The

text: class

text: PP

text: (probabilistic

text: x

text: (x

text: x

text: Bk

text: let

text: |x|

text: k

text: |x

text: The

text: following

text: polynomial

text: time)

text: contains

text: all

text: problems

text: A

text: for

text: which

text: there

text: exists

text: a

text: a

text: sligkht

text: variant

text: of

text: the

text: that

text: suits

text: our

text: non-deterministic

text: poly∈nomial-time

text: Turing

text: machine

text: M

text: such

text: that

text: purposes

text: better.

text: Consider

text: a

text: function

text: f

text: Bk

text: N

text: that

text: maps

text: a

text: k-

text: for

text: every

text: input

text: x,

text: x

text: A

text: if

text: and

text: only

text: if

text: more

text: than

text: half

text: of

text: all

text: tuple

text: of

text: binary

text: words

text: to

text: a

text: natural

text: number.

text: We

text: say

text: that

text: f

text: is

text: in

text: CH

text: computation

text: paths

text: of

text: M⊆on

text: input

text: x

text: are

text: accepting.

text: By

text: a

text: famous

text: if

text: there

text: exists

text: a

text: polynomial

text: p(n)

text: such

text: that

text: the

text: following

text: holds:

text: result

text: of

text: Toda

text: PH

text: PPP,

text: where

text: PPP

text: is

text: the

text: class

text: of

text: all

text: lan-

text: For

text: all

text: x

text: Bk

text: we

text: have

text: f(x)

text: guages

text: that

text: can

text: be

text: decided

text: in

text: deterministic

text: polynomial

text: time

text: with

text: the

text: help

text: of

text: an

text: oracle

text: from

text: PP.

text: Hence,

text: if

text: a

text: problem

text: is

text: PP-hard,

text: The

text: set

text: of

text: tuples

text: Ipfrowbelemrepdloacees

text: Lf

text: d=ef

text: {(x,

text: i)

text: Bk

text: N

text: the

text: i-th

text: bit

text: of

text: f(x)

text: is

text: equal

text: to

text: in

text: the

text: deﬁnition

text: of

text: #P

text: and

text: PP

text: non-deterministic

text: polynomial-time

text: belongs

text: to

text: CH

text: (here,

text: we

text: that

text: i

text: is

text: given

text: in

text: binary

text: repre-

text: Turing

text: machines

text: by

text: non-deterministic

text: logspace

text: Turing

text: machines

text: sentation).

text: (dreetsepr.m,

text: We

text: also

text: consider

text: mappBings

text: f

text: Dj

text: N,

text: where

text: the

text: domains

text: classes

text: #L

text: and

text: PL

text: (resp.,

text: #PSPACE

text: and

text: PPSPACE;

text: #EXP

text: and

text: Dk

text: are

text: not

text: In

text: this

text: case,

text: we

text: assume

text: some

text: standard

text: PEXP).

text: Ladner

text: has

text: shown

text: that

text: a

text: function

text: f

text: belongs

text: to

text: encoding

text: of

text: the

text: elements

text: from

text: Dk

text: as

text: words

text: over

text: a

text: binary

text: #PSPACE

text: if

text: and

text: only

text: if

text: for

text: a

text: given

text: input

text: x

text: and

text: a

text: binary

text: encoded

text: alphabet.

text: number

text: i

text: the

text: i-th

text: bit

text: of

text: f(x)

text: can

text: be

text: computed

text: in

text: PSPACE.

text: It

text: fol-

text: Lemma

text: If

text: the

text: function

text: f

text: N

text: belongs

text: to

text: CH

text: and

text: lows

text: that

text: PPSPACE

text: PSPACE.

text: It

text: is

text: well

text: known

text: that

text: PP

text: can

text: be

text: p(n)

text: is

text: a

text: then

text: also

text: the

text: functions

text: Bk

text: N

text: and

text: also

text: deﬁned

text: as

text: the

text: class

text: of

text: all

text: languages

text: L

text: f∈or

text: which

text: there

text: ex-

text: h:

text: Bk

text: N

text: belong

text: to

text: CH,

text: where

text: ist

text: two

text: #P-functions

text: f

text: and

text: f

text: such

text: that

text: x

text: L

text: if

text: and

text: only

text: if

text: and

text: similarly

text: for

text: PL

text: and

text: PEXP≥.

text: g(x)

text: f(x,

text: y)

text: and

text: h(x)

text: f(x,

text: y).

text: The

text: levels

text: of

text: the

text: counting

text: hierarchy

text: Cp

text: (i

text: are

text: inductively

text: aCnpi

text: (otrhaecsleetforofmlanCgpu)agfoesr

text: Proof.

text: Wye

text: the

text: statement

text: for

text: pt(hex

text: )proof

text: for

text: all

text: i

text: Let

text: CH

text: Cp

text: be

text: the

text: counting

text: hierarchyi.

text: It

text: is

text: sums

text: is

text: the

text: same.

text: To

text: this

text: end,

text: we

text: follow

text: the

text: arguments

text: from

text: not

text: difﬁcult

text: to

text: show

text: that

text: Ci

text: ⊆i

text: PSPACE,

text: and

text: most

text: complexity

text: showing

text: that

text: BITSLP

text: belongs

text: to

text: the

text: counting

text: hierarchy.

text: As

text: men-

text: tioned

text: in

text: Section

text: iterated

text: product,

text: i.e.,

text: the

text: problem

text: of

text: comput-

text: theorists

text: conjecture

text: that

text: CH

text: PSPACE.

text: Hence,

text: if

text: a

text: problem

text: ing

text: the

text: product

text: of

text: a

text: sequence

text: of

text: binary

text: encoded

text: integers,

text: be-

text: belongs

text: to

text: the

text: counting

text: hierarchy,

text: then

text: the

text: problem

text: is

text: probably

text: not

text: PSPACE-complete.

text: longs

text: to

text: DLOGTIME-uniform

text: More

text: precisely,

text: there

text: is

text: a

text: The

text: circuit

text: complexity

text: class

text: DLOGTIME-uniform

text: is

text: circuit

text: family,

text: where

text: the

text: n-th

text: circuit

text: the

text: class

text: of

text: all

text: languages

text: that

text: can

text: be

text: decided

text: with

text: a

text: constant-

text: Cn

text: has

text: many

text: input

text: gates,

text: which

text: are

text: interpreted

text: as

text: n-bit

text: inte-

text: depth

text: polynomial-size

text: DLOGTIME-uniform

text: circuit

text: family

text: of

text: un-

text: gers

text: xn,

text: and

text: output

text: gates,

text: which

text: evaluate

text: to

text: the

text: bits

text: in

text: bounded

text: fan-in

text: that

text: in

text: addition

text: to

text: normal

text: Boolean

text: gates

text: (AND,

text: OR

text: the

text: product

text: xi.

text: Let

text: c

text: be

text: the

text: depth

text: of

text: the

text: circuits

text: Cn,

text: which

text: is

text: a

text: ﬁxed

text: constant.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: √ Figure 8: Flow graph for n points NDST-III ( n SIII) n √ Figure 9: Flow graph for n points NDST-IV ( n SIV ) n [11] D. Fan, X. Meng, Y. Wang, X. Yang, X. Peng, W. He, G. Dong and H. Chen. Optical identity authentication scheme based on elliptic curve digital signature algorithm and phase retrieval algorithm. Applied Optics, 52(23):5645-5652, 2013. [12] J. Han, A. Saxena, V. Melkote and K. Rose, Towards jointly optimal spatial prediction and adaptive transform in video/image coding, IEEE Transactions on Image Processing, 21(4):1874-1884, 2012. [13] H. Huang, L. Xiao, and J. Liu. CORDIC-Based Uniﬁed Architectures for Computation of DCT/IDCT/DST/IDST. Circuits Syst Signal Process, 33:799-814, 2014. [14] A. K. Jain. A sinusoidal family of unitary transform. IEEE. Trans. Pattern Anal. Mach. Intell., PAMI-1:356-365, 1979. [15] A. K. Jain. A fast Karhunen-Loeve transform for a class of stochastic processes. IEEE. Trans. Commun., COM-24:1023-1029, 1976. ##LTFigure## ##LTFigure## ##LTLine## ##LTLine##

label: caption

text: Figure

text: Flow

text: graph

text: for

text: n

text: points

text: NDST-III

text: n

text: SIII)

text: n

text: Figure

text: Flow

text: graph

text: for

text: n

text: points

text: NDST-IV

text: n

text: SIV

text: n

label: reference

text: D.

text: Fan,

text: X.

text: Meng,

text: Y.

text: Wang,

text: X.

text: Yang,

text: X.

text: Peng,

text: W.

text: He,

text: G.

text: Dong

text: and

text: H.

text: Chen.

text: Optical

text: identity

text: authentication

text: scheme

text: based

text: on

text: elliptic

text: curve

text: digital

text: signature

text: algorithm

text: and

text: phase

text: retrieval

text: algorithm.

text: Applied

text: Optics,

text: J.

text: Han,

text: A.

text: Saxena,

text: V.

text: Melkote

text: and

text: K.

text: Rose,

text: Towards

text: jointly

text: optimal

text: spatial

text: prediction

text: and

text: adaptive

text: transform

text: in

text: video/image

text: coding,

text: IEEE

text: Transactions

text: on

text: Image

text: Processing,

text: H.

text: Huang,

text: L.

text: Xiao,

text: and

text: J.

text: Liu.

text: CORDIC-Based

text: Uniﬁed

text: Architectures

text: for

text: Computation

text: of

text: DCT/IDCT/DST/IDST.

text: Circuits

text: Syst

text: Signal

text: Process,

text: A.

text: K.

text: Jain.

text: A

text: sinusoidal

text: family

text: of

text: unitary

text: transform.

text: IEEE.

text: Trans.

text: Pattern

text: Anal.

text: Mach.

text: Intell.,

text: A.

text: K.

text: Jain.

text: A

text: fast

text: Karhunen-Loeve

text: transform

text: for

text: a

text: class

text: of

text: stochastic

text: processes.

text: IEEE.

text: Trans.

text: Commun.,

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##


text: Example 2.10. By following algorithms (2.5) and (2.6), the factorization for DST-II given by: √   8 S8II(cid:20) (cid:21) (cid:20) (cid:21)√    √  2 SII √ 0 0 0  2 PT 0 2V 0 0 2 SII √ 0 0 = PT 4 4 2 8(cid:20) 0 PT (cid:21) 0 I 0 0 2 SIV √ 0 (3) 4 4 2 0 0 0 2 SII √ 2 Q √ 0 4 2 H 0 2 H 8  4    where  √         0 2 0 0   sin π 0 0 cos π  √ − 16 − − 16 1 0 1 0 0 sin3π cos3π 0 2V4 = −1 0 −1 √0 , Q4 = 0 −cos136π sin3π16 0 − 16 16 0 0 0 2 cos π 0 0 sin π 16 16 Example 2.11. By following algorithms (2.5), (2.6) and (2.7), the factorization for DST-III given by: √   8 S8III (cid:20) (cid:21) (cid:20) (cid:21)√    √  2 SII √ 0 0 0  √ 2 PT 0 2V √ 0 0 2 SII √ 0 0 = 2 HT 4 4 2 (cid:20) 8 0(cid:21) I 0 2 HT 0 0 2 SIV √ 0 (4) 4 4 2 0 0 0 2 SIII 2 Q 0 4 P 0 P 8 4 Example 2.12. By following algorithms (2.5) and (2.6), the factorization for DST-IV given by: √   8 S8IV (cid:20) (cid:21)√     2 SIV √ 0 0 0  √ 2 PT 0 0 2 SII √ 0 0 = P8T(cid:20) 2V8 04 PT (cid:21) 0 0 2 2 SIV √ 0 (5) 4 2 √ 0 0 0 2 SII 2 2 H √ 0 4 Q 0 2 H 8  4  √ where      0 0 0 2 0 0 0 0   −   0 0 1 0 1 0 0 0     0 1 0 0 0 1 0 0  √  −   1 0 0 0 0 0 1 0  2V8 =  0 0 −1 0 −1 0 0 0  − 0 1 0 0 0 1 0 0 − − 1 0 0 0 0 0 1 √0 0 0 0 0 0 0 0 2 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Example

text: By

text: following

text: algorithms

text: and

text: the

text: factorization

text: for

text: DST-II

text: given

text: by:

label: equation

text: SII

text: PT

text: SII

text: PT

text: PT

text: I

text: SIV

text: SII

text: Q

text: H

text: H

text: where

text: sin

text: π

text: cos

text: π

text: −1

text: −1

text: √0

text: cos

text: π

text: sin

text: π

text: Example

text: By

text: following

text: algorithms

text: and

text: the

text: factorization

text: for

text: DST-III

text: given

text: by:

text: SII

text: PT

text: SII

text: HT

text: I

text: HT

text: SIV

text: SIII

text: Q

text: P

text: P

text: Example

text: By

text: following

text: algorithms

text: and

text: the

text: factorization

text: for

text: DST-IV

text: given

text: by:

text: SIV

text: PT

text: SII

text: PT

text: SIV

text: SII

text: H

text: Q

text: H

text: where

text: −1

text: −1

text: √0

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Would the Existence of CTCs Allow for Nonlocal Signaling? Lucas Dunlap Abstract A recent paper from Brun et al. has argued that access to a closed timelike curve (CTC) would allow for the possibility of perfectly dis- tinguishing nonorthogonal quantum states. This result can be used to develop a protocol for instantaneous nonlocal signaling. Several com- menters have argued that nonlocal signaling must fail in this and in similar cases, often citing consistency with relativity as the justiﬁca- tion. I argue that this objection fails to rule out nonlocal signaling in the presence of a CTC. I argue that the reason these authors are moti- vated to exclude the prediction of nonlocal signaling is because the No Signaling principle is considered to a fundamental part of the formula- tion of the quantum information approach. I draw out the relationship between nonlocal signaling, quantum information, and relativity, and argue that the principle theory formulation of quantum mechanics, which is at the foundation of the quantum information approach, is in tension with foundational assumptions of Deutsch D-CTC model, on which this protocol is based. 1 Introduction Quantum information theory (QIT) has been a majorly productive re- search program over the last two decades. It has enabled scientists to make progress theoretically, experimentally, and in terms of the development of technology. However, our understanding of what quantum information is telling us about the world—and what it is telling us about quantum theory itself—remains underdeveloped. Broadly speaking, this paper is an attempt 1

text: Would

label: title

text: the

text: Existence

text: of

text: CTCs

text: Allow

text: for

text: Nonlocal

text: Signaling?

text: Lucas

label: author

text: Dunlap

text: Abstract

text: A

label: abstract

text: recent

text: paper

text: from

text: Brun

text: et

text: al.

text: has

text: argued

text: that

text: access

text: to

text: a

text: closed

text: timelike

text: curve

text: (CTC)

text: would

text: allow

text: for

text: the

text: possibility

text: of

text: perfectly

text: dis-

text: tinguishing

text: nonorthogonal

text: quantum

text: states.

text: This

text: result

text: can

text: be

text: used

text: to

text: develop

text: a

text: protocol

text: for

text: instantaneous

text: nonlocal

text: signaling.

text: Several

text: com-

text: menters

text: have

text: argued

text: that

text: nonlocal

text: signaling

text: must

text: fail

text: in

text: this

text: and

text: in

text: similar

text: cases,

text: often

text: citing

text: consistency

text: with

text: relativity

text: as

text: the

text: justiﬁca-

text: tion.

text: I

text: argue

text: that

text: this

text: objection

text: fails

text: to

text: rule

text: out

text: nonlocal

text: signaling

text: in

text: the

text: presence

text: of

text: a

text: CTC.

text: I

text: argue

text: that

text: the

text: reason

text: these

text: authors

text: are

text: moti-

text: vated

text: to

text: exclude

text: the

text: prediction

text: of

text: nonlocal

text: signaling

text: is

text: because

text: the

text: No

text: Signaling

text: principle

text: is

text: considered

text: to

text: a

text: fundamental

text: part

text: of

text: the

text: formula-

text: tion

text: of

text: the

text: quantum

text: information

text: approach.

text: I

text: draw

text: out

text: the

text: relationship

text: between

text: nonlocal

text: signaling,

text: quantum

text: information,

text: and

text: relativity,

text: and

text: argue

text: that

text: the

text: principle

text: theory

text: formulation

text: of

text: quantum

text: mechanics,

text: which

text: is

text: at

text: the

text: foundation

text: of

text: the

text: quantum

text: information

text: approach,

text: is

text: in

text: tension

text: with

text: foundational

text: assumptions

text: of

text: Deutsch

text: D-CTC

text: model,

text: on

text: which

text: this

text: protocol

text: is

text: based.

text: Introduction

text: Quantum

text: information

text: theory

text: (QIT)

text: has

text: been

text: a

text: majorly

text: productive

text: re-

text: search

text: program

text: over

text: the

text: last

text: two

text: decades.

text: It

text: has

text: enabled

text: scientists

text: to

text: make

text: progress

text: theoretically,

text: experimentally,

text: and

text: in

text: terms

text: of

text: the

text: development

text: of

text: technology.

text: However,

text: our

text: understanding

text: of

text: what

text: quantum

text: information

text: is

text: telling

text: us

text: about

text: the

text: world—and

text: what

text: it

text: is

text: telling

text: us

text: about

text: quantum

text: theory

text: itself—remains

text: underdeveloped.

text: Broadly

text: speaking,

text: this

text: paper

text: is

text: an

text: attempt


text: Figure 4: The method for using the BHW circuit in Gisin’s instantaneous signaling device. Alice measures ﬁrst measures her particle along the X or Z axis. Bob then uses the BHW circuit to determine what state his particle is in. to measure in the X direction (for “yes”) or the Z direction (for “no”). Bob, using the BHW circuit, can recover Alice’s message, which is transmitted | (cid:105) | (cid:105) instantaneously. That is, if the output of Bob’s device is 10 or 11 , he knows Alice measured her half of the singlet pair in the X direction (intending | (cid:105) | (cid:105) the message to be “yes”), and if his results are either 00 or 01 , he knows she measured in the Z direction (meaning “no”). 3.3 The Bub-Stairs Consistency Condition In a recent paper [5] Jeﬀrey Bub and Allen Stairs propose a consistency condition to solve one of the outstanding conceptual problems with Nonlocal Signaling. Their condition solves some potential ambiguity associated with the possibility of signaling. The issue that the consistency condition is designed to solve arises be- cause of the fact that the nature of Nonlocal Signaling allows for cause/eﬀect to happen at spacelike separation. Alice’s choice of measurement causes Bob to get the result he does faster than a light signal would have been able to 14 ##LTFigure##

text: Figure

text: The

text: method

text: for

text: using

text: the

text: BHW

text: circuit

text: in

text: Gisin’s

text: instantaneous

text: signaling

text: device.

text: Alice

text: measures

text: ﬁrst

text: measures

text: her

text: particle

text: along

text: the

text: X

text: or

text: Z

text: axis.

text: Bob

text: then

text: uses

text: the

text: BHW

text: circuit

text: to

text: determine

text: what

text: state

text: his

text: particle

text: is

text: in.

text: to

text: measure

text: in

text: the

text: X

text: direction

text: (for

text: “yes”)

text: or

text: the

text: Z

text: direction

text: (for

text: “no”).

text: Bob,

text: using

text: the

text: BHW

text: circuit,

text: can

text: recover

text: Alice’s

text: message,

text: which

text: is

text: transmitted

text: instantaneously.

text: That

text: is,

text: if

text: the

text: output

text: of

text: Bob’s

text: device

text: is

text: or

text: he

text: knows

text: Alice

text: measured

text: her

text: half

text: of

text: the

text: singlet

text: pair

text: in

text: the

text: X

text: direction

text: (intending

text: the

text: message

text: to

text: be

text: “yes”),

text: and

text: if

text: his

text: results

text: are

text: either

text: or

text: he

text: knows

text: she

text: measured

text: in

text: the

text: Z

text: direction

text: (meaning

text: “no”).

text: The

text: Bub-Stairs

text: Consistency

text: Condition

text: In

text: a

text: recent

text: paper

text: Jeﬀrey

text: Bub

text: and

text: Allen

text: Stairs

text: propose

text: a

text: consistency

text: condition

text: to

text: solve

text: one

text: of

text: the

text: outstanding

text: conceptual

text: problems

text: with

text: Nonlocal

text: Signaling.

text: Their

text: condition

text: solves

text: some

text: potential

text: ambiguity

text: associated

text: with

text: the

text: possibility

text: of

text: signaling.

text: The

text: issue

text: that

text: the

text: consistency

text: condition

text: is

text: designed

text: to

text: solve

text: arises

text: be-

text: cause

text: of

text: the

text: fact

text: that

text: the

text: nature

text: of

text: Nonlocal

text: Signaling

text: allows

text: for

text: cause/eﬀect

text: to

text: happen

text: at

text: spacelike

text: separation.

text: Alice’s

text: choice

text: of

text: measurement

text: causes

text: Bob

text: to

text: get

text: the

text: result

text: he

text: does

text: faster

text: than

text: a

text: light

text: signal

text: would

text: have

text: been

text: able

text: to

text: ##LTFigure##


text: particular, it is one of the most promising principles used in the reconstruc- tions of quantum theory from the space of generalized probabilistic theories. This research project considers the space of all possible theories formulated in terms of their information processing capabilities and their allowed corre- lations between events. For any theory, whether it applies to Nature or not, one can consider the information processing possibilities of this theory, the diﬀerences from those of classical or quantum theory, and attempt to trace these possibilities back to the fundamental features of the theory. [1] Principles are introduced, which partition the theories in that generalized theory space. The hope is that a small number of physically plausible prin- ciples can be identiﬁed which will pick out exactly those correlations allowed by quantum theory. On this view, these principles would give us an answer to the question of why our world allows for the quantum correlations to obtain, and not others. No Signaling is one of the core principles at the heart of this approach. If the privileged status of the No Signaling principle were to be undermined, that would in turn undermine the status of other principles promising for this project, which live or die with No Signaling. One such example is the princi- ple of “information causality”, which generalizes the No Signaling principle in the following way. If Alice sends Bob m classical bits, the most classical information Bob can extract from that message is m bits. This reduces to the No Signaling principle in the case where m = 0 [17]. This is consistent with the teleportation protocol because, even though Alice can send Bob a quantum state that would take a potentially inﬁnite amount of classical in- formation to perfectly specify, Bob cannot extract more than the 2 classical | (cid:105) bits Alice sent to him. Having Alice’s input state ψ in hand does not give Bob any more information. This approach is closely associated with the principle-based conception of physical theories. This is a conception in which the fundamental formulation of a physical theory is in terms of principled restrictions on the kinematical level. These principles never need to be justiﬁed by ontological or dynam- ical considerations. An empirically equivalent theory theory formulated in terms of dynamics and ontology is taken on this approach to represent a less fundamental formulation. The special theory of relativity is taken to be the paradigm example of 19

text: particular,

text: it

text: is

text: one

text: of

text: the

text: most

text: promising

text: principles

text: used

text: in

text: the

text: reconstruc-

text: tions

text: of

text: quantum

text: theory

text: from

text: the

text: space

text: of

text: generalized

text: probabilistic

text: theories.

text: This

text: research

text: project

text: considers

text: the

text: space

text: of

text: all

text: possible

text: theories

text: formulated

text: in

text: terms

text: of

text: their

text: information

text: processing

text: capabilities

text: and

text: their

text: allowed

text: corre-

text: lations

text: between

text: events.

text: For

text: any

text: theory,

text: whether

text: it

text: applies

text: to

text: Nature

text: or

text: not,

text: one

text: can

text: consider

text: the

text: information

text: processing

text: possibilities

text: of

text: this

text: theory,

text: the

text: diﬀerences

text: from

text: those

text: of

text: classical

text: or

text: quantum

text: theory,

text: and

text: attempt

text: to

text: trace

text: these

text: possibilities

text: back

text: to

text: the

text: fundamental

text: features

text: of

text: the

text: theory.

text: Principles

text: are

text: introduced,

text: which

text: partition

text: the

text: theories

text: in

text: that

text: generalized

text: theory

text: space.

text: The

text: hope

text: is

text: that

text: a

text: small

text: number

text: of

text: physically

text: plausible

text: prin-

text: ciples

text: can

text: be

text: identiﬁed

text: which

text: will

text: pick

text: out

text: exactly

text: those

text: correlations

text: allowed

text: by

text: quantum

text: theory.

text: On

text: this

text: view,

text: these

text: principles

text: would

text: give

text: us

text: an

text: answer

text: to

text: the

text: question

text: of

text: why

text: our

text: world

text: allows

text: for

text: the

text: quantum

text: correlations

text: to

text: obtain,

text: and

text: not

text: others.

text: No

text: Signaling

text: is

text: one

text: of

text: the

text: core

text: principles

text: at

text: the

text: heart

text: of

text: this

text: approach.

text: If

text: the

text: privileged

text: status

text: of

text: the

text: No

text: Signaling

text: principle

text: were

text: to

text: be

text: undermined,

text: that

text: would

text: in

text: turn

text: undermine

text: the

text: status

text: of

text: other

text: principles

text: promising

text: for

text: this

text: project,

text: which

text: live

text: or

text: die

text: with

text: No

text: Signaling.

text: One

text: such

text: example

text: is

text: the

text: princi-

text: ple

text: of

text: “information

text: causality”,

text: which

text: generalizes

text: the

text: No

text: Signaling

text: principle

text: in

text: the

text: following

text: way.

text: If

text: Alice

text: sends

text: Bob

text: m

text: classical

text: bits,

text: the

text: most

text: classical

text: information

text: Bob

text: can

text: extract

text: from

text: that

text: message

text: is

text: m

text: bits.

text: This

text: reduces

text: to

text: the

text: No

text: Signaling

text: principle

text: in

text: the

text: case

text: where

text: m

text: This

text: is

text: consistent

text: with

text: the

text: teleportation

text: protocol

text: because,

text: even

text: though

text: Alice

text: can

text: send

text: Bob

text: a

text: quantum

text: state

text: that

text: would

text: take

text: a

text: potentially

text: inﬁnite

text: amount

text: of

text: classical

text: in-

text: formation

text: to

text: perfectly

text: specify,

text: Bob

text: cannot

text: extract

text: more

text: than

text: the

text: classical

text: bits

text: Alice

text: sent

text: to

text: him.

text: Having

text: Alice’s

text: input

text: state

text: ψ

text: in

text: hand

text: does

text: not

text: give

text: Bob

text: any

text: more

text: information.

text: This

text: approach

text: is

text: closely

text: associated

text: with

text: the

text: principle-based

text: conception

text: of

text: physical

text: theories.

text: This

text: is

text: a

text: conception

text: in

text: which

text: the

text: fundamental

text: formulation

text: of

text: a

text: physical

text: theory

text: is

text: in

text: terms

text: of

text: principled

text: restrictions

text: on

text: the

text: kinematical

text: level.

text: These

text: principles

text: never

text: need

text: to

text: be

text: justiﬁed

text: by

text: ontological

text: or

text: dynam-

text: ical

text: considerations.

text: An

text: empirically

text: equivalent

text: theory

text: theory

text: formulated

text: in

text: terms

text: of

text: dynamics

text: and

text: ontology

text: is

text: taken

text: on

text: this

text: approach

text: to

text: represent

text: a

text: less

text: fundamental

text: formulation.

text: The

text: special

text: theory

text: of

text: relativity

text: is

text: taken

text: to

text: be

text: the

text: paradigm

text: example

text: of