In this paper, we study the precise complexity of XPath

1.0 query processing. Even though heavily used by its incorporation

into a variety of XML-related standards, the

precise cost of evaluating an XPath query is not yet wellunderstood.

The first polynomial-time algorithm for XPath

processing (with respect to combined complexity) was proposed

only recently, and even to this day all major XPath

engines take time exponential in the size of the input queries.

From the standpoint of theory, the precise complexity of

XPath query evaluation is open, and it is thus unknown

whether the query evaluation problem can be parallelized.

In this work, we show that both the data complexity and

the query complexity of XPath 1.0 fall into lower (highly parallelizable)

complexity classes, but that the combined complexity

is PTIME-hard. Subsequently, we study the sources

of this hardness and identify a large and practically important

fragment of XPath 1.0 for which the combined complexity

is LOGCFL-complete and, therefore, in the highly

parallelizable complexity class NC2.