Wyniki wyszukiwania - BazTech

1

On the Complexity of L-reachability

Komarath B., Sarma J., Sunil K. S.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 4

471--483

EN

We initiate a complexity theoretic study of the language based graph reachability problem (L-REACH) : Fix a language L. Given a graph whose edges are labelled with alphabet symbols of the language L and two special vertices s and t, test if there is path P from s to t in the graph such that the concatenation of the symbols seen from s to t in the path P forms a string in the language L. We study variants of this problem with different graph classes and different language classes and obtain complexity theoretic characterizations for all of them. Our main results are the following: • Restricting the language using formal language theory we show that the complexity of L- REACH increases with the power of the formal language class. We show that there is a regular language for which the L-REACH is NL-complete even for undirected graphs. In the case of linear languages, the complexity of L-REACH does not go beyond the complexity of L itself. Further, there is a deterministic context-free language L for which L-DAGREACH is LogCFL- complete. • We use L-REACH as a lens to study structural complexity. In this direction we show that there is a language A in TC0 for which A-DAGREACH is NP-complete. Using this we show that P vs NP question is equivalent to P vs DAGREACH-1(P)1 question. This leads to the intriguing possibility that by proving DAGREACH-1(P) is contained in some subclass of P, we can prove an upward translation of separation of complexity classes. Note that we do not know a way to upward translate the separation of complexity classes.

2

A Representation Theorem for Primitive Recursive Algorithms

Andary P., Patrou B., Valarcher P.

Fundamenta Informaticae

|

2011

|

Vol. 107, nr 4

313-330

EN

We formalize the algorithms computing primitive recursive (PR) functions as the abstract state machines (ASMs) whose running length is computable by a PR function. Then we show that there exists a programming language (implementing only PR functions) by which it is possible to implement any one of the previously defined algorithms for the PR functions in such a way that their complexity is preserved.

3

Relativized helping operators

Cintioli P.

TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk

|

2005

|

Vol. 9, No 3

357-367

EN

Schöning and Ko respectively introduced the concepts of helping and one-side-helping, and then defined new operators, Phelp(•) and P1-help(•), acting on classes of sets C and returning classes of sets Phelp(C) and P1-help(C). A number of results have been obtained on this subject, principally devoted to understanding how wide the Phelp(C) and P1-help(C) classes are. For example, it seems that the Phelp(•) operator contracts NP ∩ coNP}, while the P1-help(•) operator enlarges UP. To better understand the relative power of P1-help(•) versus Phelp(•) we propose to search, for every relativizable class D containing P, the largest relativizable class C containing P such that for every oracle B PBhelp(CB)? PB1-help(DB). In the following paper: Cintioli P. and Silvestri R. 1997 Inf. Proc. Let. 61 189, it has been observed that Phelp(UP ∩ coUP)= P1-help(UP ∩ coUP), and this is true in any relativized world. In this paper we consider the case of D=UP ∩ coUP and demonstrate the existence of an oracle A for which PAhelp(UPA2 ∩ coUPA2) is not contained in PA1-help(UPA ∩ coUPA). We also prove that for every integer k ≥ 2 there exists an oracle A such that PAhelp(UPAk ∩ coUPAk) ? UPAk.