 # Ctic 35º Concurso de Trabalhos de Iniciação Científica Blum axioms and nondeterministic computation of functions

Yüklə 157,92 Kb.

 tarix 08.08.2018 ölçüsü 157,92 Kb.
 451 CTIC - 35º Concurso de Trabalhos de Iniciação Científica Blum axioms and nondeterministic computation of functions Tiago Royer 1 , Jerusa Marchi 1 1 Universidade Federal de Santa Catarina — Departamento de Informática e Estatística royertiago@gmail.com, jerusa.marchi@ufsc.br Abstract. In his doctoral thesis, Manuel Blum proposed two axioms for com- plexity measures that allows us to talk about complexity in an axiomatic man- ner. His axioms does not even specify the machine model — it just requires it to satisfy some properties. Blum axioms, however, are deﬁned in the context of function computation. This restriction is easy to implement with determin- istic machines, since there is only one output for a given input, but how can a nondeterministic Turing machine compute a function? This paper surveys tech- niques to associate nondeterministic machines with functions and analyze how they interact with computational complexity. 1. Introduction In Theory of Computation, we usually use languages to mathematically model problems in the real world. Decision problems (“yes/no”) are mapped to languages in a very natural way, by just putting every “yes” instance in the language, and leaving the rest out. Search problems usually are rewritten as a decision problem, and then this problem is converted to a language. For instance, the task of ﬁnding a satisfying assignment for a Boolean for- mula is reinterpreted as the task of deciding whether such an assignment exists, and this task is then converted to a language — in this example we have SAT, the Boolean satisﬁ- ability problem. This does the trick when it comes to proving that something is hard; for instance, if we show that the decision problem is NP-hard or undecidable, then intuitively the corresponding search problem must be at least as hard. Therefore, concepts like “de- cidable”, “NP-complete”, “polynomial-time decidable” arise naturally in the context of decision problems. However, even from the theoretical standpoint, it is useful to extend these concepts to functions. For instance, the concept of polynomial-time computable functions are re- quired to deﬁne Karp reductions [Arora and Barak 2009, p. 42]. For single-tape determin- istic Turing machines, this deﬁnition is easy to extend: A function f : {0, 1} ∗ → {0, 1} ∗ is said to be polynomial-time computable if there is a Turing machine M and a poly- nomial p such that, when given the string x as input, M halts with f(x) in its tape within p(|x|) steps. Most extensions to this basic model, like the use of several tracks, or several tapes, or multidimensional tapes, can be easily incorporated in the deﬁnition of polynomial- time computable. Except nondeterminism. We hit a wall right in the start: how does a nondeterministic machine computes a function in the ﬁrst place? This paper presents several attempts to establish how a nondeterministic Turing machine could compute a function, and to extend the concept of “polynomial-time com- putable” under each deﬁnition. Section 2 sets reasonableness criteria to both the deﬁnition D-STHARk: Avaliando Escalonadores Dinâmicos de Tarefas em Arquiteturas -  Híbridas Simuladas  Savyo Machado (Universidade Federal de São João del-Rei)  Danilo Amaral (Universidade Federal de São João del-Rei)  Guilherme Andrade (Universidade Federal de Minas Gerais)  Fernando Mourão (Universidade Federal de São João Del Rei)  Leonardo Rocha (Universidade Federal de São João Del Rei)  GPU Accelerated Data Indexing for Hierarchical Density-Based Clustering Danilo Amaral (Universidade Federal de São João del-Rei)  Savyo Machado (Universidade Federal de São João del-Rei)  Guilherme Andrade (Universidade Federal de Minas Gerais)  Fernando Mourão (Universidade Federal de São João Del Rei)  Leonardo Rocha (Universidade Federal de São João Del Rei)  XXXVI Congresso da Sociedade Brasileira de Computação 452 of function computation and complexity of the computation. Section 3, which contains the several deﬁnitions, presents and criticizes Hopcroft and Ullman’s and Goldreich’s def- initions (sections 3.1 and 3.2), proposes one possible deﬁnition that meet the quality stan- dards (section 3.3), and shows other two deﬁnitions, by Krentel (section 3.4) and Valiant (section 3.5), that, altough were not proposed in the context of general nondeterministic computation of functions, also meet the quality standards and sidesteps the problems with the proposed deﬁnition (presented in section 3.3.1). The development of this project is mentioned in section 5, after the concluding remarks (section 4). 2. Our approach: Gödel numberings and Blum axioms In this paper, we will try to associate nondeterministic computation with partial recur- sive functions, in some well-behaved manner, and preserving the apparent 1 exponential speed-up present in nondeterministic deciders. The concept of Gödel numberings (sec- tion 2.1) captures the notion of “well-behaved”. The Blum axioms (section 2.2) capture the notions of computational complexity. We thus will demand the deﬁnitions to satisfy the requirements of Gödel numberings and Blum axioms. We are restricting ourselves to using single-valued functions, but there are alter- native approaches. Complexity classes like NPVM (see, for example, the paper of Sel- man [Selman 1994, p. 359]) are deﬁned using multivalued functions, which are allowed to return several values for a single input. Another approach is to use function problems associated to problems in NP, where the machine is required to return any certiﬁcate for the given instance, or to reject the input if it is not in the language [Papadimitriou 1994, p. 229]. We will not consider these approaches here. 2.1. Reasonableness criterion: acceptable Gödel numberings One of the most important theoretical results concerning Turing machines is the existence of undecidable problems. Namely, the halting problem (the task of deciding whether a given Turing machine will halt on a given input) cannot be solved by Turing machines [Arora and Barak 2009, p. 23]. The formalization (and proof) of this fact requires the deﬁnition of some sort of encoding; since Turing machines can only reason about strings, we need somehow to encode Turing machines into strings, to be able to pose the halting problem as a language question. Each Turing machine can be associated to the corresponding partial recursive function it computes. There are several ways to encode Turing machines as strings, but what is most important about them is that they allow us to manipulate these partial recur- sive functions indirectly — partial recursive functions are (potentially) inﬁnite objects, so we cannot write them down on a Turing machine tape, but we can write the encoding of a Turing machine that compute these functions. Therefore, these encodings provide a way to associate a string (which is a ﬁnite, manipulable object) with a partial recursive function (which is an inﬁnite, mathematical, “untouchable” object). Encodings are enumerations of all partial recursive functions. 1 It is apparent in the sense that, if proven would show P = NP, and if disproved (showing a polynomial slowdown is the best we can do) would show P = NP. Although most researchers expect the former to be the case [Gasarch 2012, p. 54], as Papadimitriou noted [Papadimitriou 1994, p. 412], in the absence of a proof that P = NP we should not be too emphatic in stating the simulation require (as opposed to seemingly require) exponential slowdown. 453 CTIC - 35º Concurso de Trabalhos de Iniciação Científica One important feature about the standard encodings of deterministic Turing ma- chines is the Universal Turing Machine Theorem: the existence of a partial recursive function U : {0, 1} ∗ × {0, 1} ∗ → {0, 1} ∗ such that, if w encodes the machine M, then U (m, x) is the result of running the machine M on x. A machines that compute U is called universal Turing machine. The concept of acceptable Gödel numbering ([Rogers 1987, p. 41], [Blum 1967, p. 324]) encompasses the existence of universal machines and a little more. We will use it as our reasonableness criteria to our deﬁnitions. Deﬁnition 1. Let P be the set of all partial recursive functions. An acceptable Gödel numbering is a function φ : {0, 1} ∗ → P, that associates each string (or program 2 ) w ∈ {0, 1} ∗ to a function φ w ∈ P, that satisﬁes 1. φ is surjective; that is, every partial recursive function f ∈ P has a program w ∈ {0, 1} ∗ such that φ w = f ; 2. There is a partial recursive function U : {0, 1} ∗ × {0, 1} ∗ → {0, 1} ∗ such that, for every w and x, U(w, x) is deﬁned if and only if φ w (x) is deﬁned, and, in this case, U (w, x) = φ w (x); 3. There is a total recursive function σ : {0, 1} ∗ × {0, 1} ∗ → {0, 1} ∗ such that, for every y, φ w (x, y) is deﬁned if and only if φ σ(w,x) (y) is deﬁned, and, in this case, φ w (x, y) = φ σ(w,x) (y). This concept captures the intuitive notion of “well-behaved numbering”. Condition 1 guarantees that the image of φ is all of P, so that the numbering neither “forgets” a partial recursive function nor generate a function that is not partial recursive. Condition 2 is the universal Turing machine theorem. Condition 3 is the “little more” we mentioned earlier. It is known as the S mn theo- rem [Rogers 1987, p. 24]. Essentially, given a partial recursive function of two variables, we can obtain a partial recursive function of one variable by ﬁxing the ﬁrst argument. The function σ provides a systematic way of doing this: given a description w of a partial recursive function of two variables and the value x to be ﬁxed as the ﬁrst variable, σ(w, x) is a machine that computes this new partial recursive function. Example 2. Any encoding of deterministic Turing machines as a binary string yields an acceptable numbering of the recursive functions. Example 3. Any programming language can be understood as an acceptable Gödel num- bering. For example, if we restrict a C program to perform input and output only using the standard input and standard output (that is, forbid interactions with the user, ﬁle reading, GUIs, access to system clock, etc.), the resulting program will map a binary input to a binary output, characterizing a partial recursive function. Thus, we can see a C compiler as an implementation of an acceptable Gödel numbering. 3 2 In texts like Rogers’ [Rogers 1987], the partial recursive functions have the naturals as domain and codomain (that is, they are of the form f : N → N), and Gödel numberings associates natural numbers with recursive functions. In this paper we will work with binary strings instead of numbers, which will simplify the deﬁnition of complexity classes and allows us to think the string w as a program for φ w (see example 3). 3 Note we are ignoring here issues like compilation and run-time errors. These can be dealt with as in the case of Turing machines: any invalid program will signify some ﬁxed partial recursive function (say, the function that is deﬁned nowhere); and any invalid step in computation makes the function to be not deﬁned on that input. of function computation and complexity of the computation. Section 3, which contains the several deﬁnitions, presents and criticizes Hopcroft and Ullman’s and Goldreich’s def- initions (sections 3.1 and 3.2), proposes one possible deﬁnition that meet the quality stan- dards (section 3.3), and shows other two deﬁnitions, by Krentel (section 3.4) and Valiant (section 3.5), that, altough were not proposed in the context of general nondeterministic computation of functions, also meet the quality standards and sidesteps the problems with the proposed deﬁnition (presented in section 3.3.1). The development of this project is mentioned in section 5, after the concluding remarks (section 4). 2. Our approach: Gödel numberings and Blum axioms In this paper, we will try to associate nondeterministic computation with partial recur- sive functions, in some well-behaved manner, and preserving the apparent 1 exponential speed-up present in nondeterministic deciders. The concept of Gödel numberings (sec- tion 2.1) captures the notion of “well-behaved”. The Blum axioms (section 2.2) capture the notions of computational complexity. We thus will demand the deﬁnitions to satisfy the requirements of Gödel numberings and Blum axioms. We are restricting ourselves to using single-valued functions, but there are alter- native approaches. Complexity classes like NPVM (see, for example, the paper of Sel- man [Selman 1994, p. 359]) are deﬁned using multivalued functions, which are allowed to return several values for a single input. Another approach is to use function problems associated to problems in NP, where the machine is required to return any certiﬁcate for the given instance, or to reject the input if it is not in the language [Papadimitriou 1994, p. 229]. We will not consider these approaches here. 2.1. Reasonableness criterion: acceptable Gödel numberings One of the most important theoretical results concerning Turing machines is the existence of undecidable problems. Namely, the halting problem (the task of deciding whether a given Turing machine will halt on a given input) cannot be solved by Turing machines [Arora and Barak 2009, p. 23]. The formalization (and proof) of this fact requires the deﬁnition of some sort of encoding; since Turing machines can only reason about strings, we need somehow to encode Turing machines into strings, to be able to pose the halting problem as a language question. Each Turing machine can be associated to the corresponding partial recursive function it computes. There are several ways to encode Turing machines as strings, but what is most important about them is that they allow us to manipulate these partial recur- sive functions indirectly — partial recursive functions are (potentially) inﬁnite objects, so we cannot write them down on a Turing machine tape, but we can write the encoding of a Turing machine that compute these functions. Therefore, these encodings provide a way to associate a string (which is a ﬁnite, manipulable object) with a partial recursive function (which is an inﬁnite, mathematical, “untouchable” object). Encodings are enumerations of all partial recursive functions. 1 It is apparent in the sense that, if proven would show P = NP, and if disproved (showing a polynomial slowdown is the best we can do) would show P = NP. Although most researchers expect the former to be the case [Gasarch 2012, p. 54], as Papadimitriou noted [Papadimitriou 1994, p. 412], in the absence of a proof that P = NP we should not be too emphatic in stating the simulation require (as opposed to seemingly require) exponential slowdown. XXXVI Congresso da Sociedade Brasileira de Computação 454 One important theorem that can be proven using acceptable Gödel numberings alone is the recursion theorem [Rogers 1987, p. 181]. It states that, if φ is any acceptable Gödel numbering and f is any total recursive function, then there is some program w 0 such that φ w 0 = φ f (w 0 ) . That is, if f is any systematic transformation on programs, there is a program w (a ﬁxed point for f) whose meaning under φ is unchanged. The recursion theorem can be used, for example, to show the existence of quines (programs whose output are their own source codes) in any Turing-complete programming language: choose f to be the function that, given a program w, returns another program f(w) that prints the string w when run. 4 Then, by the recursion theorem, there is some program w 0 that is equivalent to its transformed version f(w 0 ) ; thus, w 0 already writes the string w 0 , its own source code. Therefore, any programming language has quines [Kozen 2006, p. 227]. 2.2. Efﬁciency criterion: Blum axioms The complexity of a computation is how much of a resource that is invested in that compu- tation [Hopcroft and Ullman 1979, p. 285]. For each model of computation and each re- source under that model, we can establish a complexity measure concerning that resource. This section is devoted to formalizing this notion. As we did with the machine encod- ings, we will impose some restrictions on what can be a complexity measure to be able to manipulate it (at least indirectly). In our case, we will use Blum axioms [Blum 1967, p. 324]. Deﬁnition 4. Given an acceptable Gödel numbering φ, a complexity measure for φ is a function Φ : Σ ∗ × Σ ∗ → N of two variables that satisﬁes [Blum 1967, p. 324]: 1. For every w and x, φ w (x) exists if and only if Φ(w, x) exists; and 2. For every string w, x and every natural number k, the predicate “Φ(w, x) = k?” is decidable. Φ(w, x) is the complexity of computing φ w (x) using the program w. The ﬁrst axiom says that it only makes sense to talk about the complexity of a computation that ends. The second axiom gives minimum tools to manipulate Φ indirectly, in the same manner we require φ to be an acceptable Gödel numbering. Example 5. The standard measures of time and space can be constructed over the accept- able numbering of example 2. They are, respectively, the number of moves and tape cells scanned before halting. Leave the complexity undeﬁned if the machine does not halt — this satisﬁes the ﬁrst axiom. The predicate of the second axiom is simple for time com- plexity; for space complexity, we must keep the whole history of computation to make sure the machine does not loop in a limited amount of space (because the complexity is not deﬁned in this case). Deﬁnition 6. Given a complexity measure Φ for an acceptable Gödel numbering φ and a total recursive function f : N → N, deﬁne the complexity class C Φ (f ) by ([Kozen 2006, p. 232]) C Φ (f ) = {φ w | Φ(w, x) ≤ f(|x|) almost everywhere 5 }. 4 For Turing machines, for instance, we can encode the bits of w in the transition table of f(w). 5 Almost everywhere means that the inequality Φ i (x) ≤ f(|x|) holds for all but a ﬁnite number of different x. 455 CTIC - 35º Concurso de Trabalhos de Iniciação Científica This formalizes the notion of complexity class. There are some important theo- rems concerning complexity classes under the Blum axioms; we mention only the Union Theorem [Kozen 2006, p. 234]. It states that, if {f i } is any recursive list of increasing functions such that f i (n) ≤ f i+1 (n) for all x (that is, each f i is greater than the previous), then there is some function g such that C Φ (g) = i ∈N C Φ (f i ). That is, the class C Φ (g) contains exactly all functions present in the classes C Φ (f i ) . Choos- ing Φ as the time complexity and f i (n) = n i (the polynomial functions), the union in the right is exactly the class P, the problems solvable in polynomial time. By the Union The- orem, P is C Φ (g) for some recursive function g, so, even though P does not have an easily speciﬁable bounding function, such function exists nevertheless. 3. Nondeterministic computation of functions This section surveys several approaches for deﬁning nondeterministic computation of functions. Sections 2.1 and 2.2 introduced the concept of acceptable Gödel numbering, the Blum axioms, and its complexity classes. As we want to regard these concepts as “quality requirements” for the deﬁnitions, we will analyze each of them to see whether they de- ﬁne acceptable Gödel numberings, the analogous time complexity satisﬁes Blum axioms, and that the characteristic function 6 of the Boolean satisﬁability problem can be solved in “polynomial time” according to that complexity measure. (This last requirement ex- presses that the deﬁnition preserves the exponential speed-up that nondeterminism gives to deciders.) 3.1. Hopcroft-Ullman’s deﬁnition Deﬁnition 7 (Hopcroft and Ullman’s deﬁnition 7 ) . If w is an encoding for the Turing machine M, we say that φ w (x) = y if and only if, when processing x, there is some branch of M that halts with y in the tape, and there is no branch that halts with some z = x in the tape. The problem with their deﬁnition is that φ w (x) is allowed to be deﬁned, even if some branch of computation does not halt. This allows us to solve the complement of the halting problem. Proposition 8. Deﬁne the partial function f : Σ ∗ × Σ ∗ → {0, 1} by f (w, x) = 1, if the machine w does not halt on x. undeﬁned, if w halts on x. This function can be computed by a nondeterministic Turing machine under Hopcroft and Ullman’s deﬁnition. 6 The characteristic function of a set A is the function 1 A deﬁned to be 1 for x ∈ A and 0 for x /∈ A. 7 Hopcroft and Ullman’s original deﬁnition [Hopcroft and Ullman 1979, p. 313] was deﬁned in the con- text of computation of integer functions. We are rephrasing here in terms of strings, but keeping the relation they imposed on the execution branches. One important theorem that can be proven using acceptable Gödel numberings alone is the recursion theorem [Rogers 1987, p. 181]. It states that, if φ is any acceptable Gödel numbering and f is any total recursive function, then there is some program w 0 such that φ w 0 = φ f (w 0 ) . That is, if f is any systematic transformation on programs, there is a program w (a ﬁxed point for f) whose meaning under φ is unchanged. The recursion theorem can be used, for example, to show the existence of quines (programs whose output are their own source codes) in any Turing-complete programming language: choose f to be the function that, given a program w, returns another program f(w) that prints the string w when run. 4 Then, by the recursion theorem, there is some program w 0 that is equivalent to its transformed version f(w 0 ) ; thus, w 0 already writes the string w 0 , its own source code. Therefore, any programming language has quines [Kozen 2006, p. 227]. 2.2. Efﬁciency criterion: Blum axioms The complexity of a computation is how much of a resource that is invested in that compu- tation [Hopcroft and Ullman 1979, p. 285]. For each model of computation and each re- source under that model, we can establish a complexity measure concerning that resource. This section is devoted to formalizing this notion. As we did with the machine encod- ings, we will impose some restrictions on what can be a complexity measure to be able to manipulate it (at least indirectly). In our case, we will use Blum axioms [Blum 1967, p. 324]. Deﬁnition 4. Given an acceptable Gödel numbering φ, a complexity measure for φ is a function Φ : Σ ∗ × Σ ∗ → N of two variables that satisﬁes [Blum 1967, p. 324]: 1. For every w and x, φ w (x) exists if and only if Φ(w, x) exists; and 2. For every string w, x and every natural number k, the predicate “Φ(w, x) = k?” is decidable. Φ(w, x) is the complexity of computing φ w (x) using the program w. The ﬁrst axiom says that it only makes sense to talk about the complexity of a computation that ends. The second axiom gives minimum tools to manipulate Φ indirectly, in the same manner we require φ to be an acceptable Gödel numbering. Example 5. The standard measures of time and space can be constructed over the accept- able numbering of example 2. They are, respectively, the number of moves and tape cells scanned before halting. Leave the complexity undeﬁned if the machine does not halt — this satisﬁes the ﬁrst axiom. The predicate of the second axiom is simple for time com- plexity; for space complexity, we must keep the whole history of computation to make sure the machine does not loop in a limited amount of space (because the complexity is not deﬁned in this case). Deﬁnition 6. Given a complexity measure Φ for an acceptable Gödel numbering φ and a total recursive function f : N → N, deﬁne the complexity class C Φ (f ) by ([Kozen 2006, p. 232]) C Φ (f ) = {φ w | Φ(w, x) ≤ f(|x|) almost everywhere 5 }. 4 For Turing machines, for instance, we can encode the bits of w in the transition table of f(w). 5 Almost everywhere means that the inequality Φ i (x) ≤ f(|x|) holds for all but a ﬁnite number of different x. XXXVI Congresso da Sociedade Brasileira de Computação 456 Proof. On input (w, x), create two branches of computation. On the ﬁrst, write 1 on the tape and halt. On the second, simulate the universal Turing machine U in the input, and if U halts, write 0 on the tape and halt too. If w halts on x, there will be two halting branches of computation, each writing a different value in the tape, so, by deﬁnition, the function is not deﬁned on this input. If w never halts, then only the ﬁrst branch will halt (and with 1 written on the tape), so the function is deﬁned on this input and its value is 1. Therefore, under Hopcroft and Ullman’s deﬁnition, we can compute some non- computable functions, violating the requirement 1 of Gödel numberings. We can try to ﬁx this deﬁnition by forcing all branches to halt; but then, as all branches are required to return the same value, the machine will be (almost) determin- istic. Therefore, if there is a machine M that computes the characteristic function of the satisﬁability problem in nondeterministic polynomial time, we could simulate M on a given input, choosing (say) always the ﬁrst option when confronted with nondeterminism. If this branch of computation returns 1, then every branch returns 1 and the input is satisﬁ- able; if this branch returns 0, every branch returns 0 and the input is unsatisﬁable. We thus could solve SAT in deterministic polynomial time. So, with this restriction, we lose the apparent exponential speed-up in computation time we have when using nondeterminism. 3.2. Goldreich’s deﬁnition Deﬁnition 9 (Goldreich’s deﬁnition). Let ⊥ be some special symbol not in {0, 1} ∗ . (This symbol will represents “don’t know”.) A nondeterministic machine M com- putes the function f if, when processing the input x, both the following conditions hold [Goldreich 2008, p. 168]: • Every branch of M halts and outputs either f(x) or ⊥. • At least one branch of M halts with f(x) on the tape. The extra symbol ⊥ sidesteps the problems of a branch looping forever. This al- lows us to mechanically convert nondeterministic machines under Goldreich’s deﬁnition to deterministic machines via simulation — the deterministic machine just need to simu- late all branches until completion, to actually be sure every branch halts; if some branch do not halt, then the simulating machine will not halt either, but the function is not deﬁned in this case, so this behavior is correct. Thus, we only enumerate computable functions. To show the universal machine theorem and the S mn , we can simply ﬁrst convert the machine in question to a deter- ministic machine and use their theorems; thus, this deﬁnition yields an acceptable Gödel numbering. And, by counting the number of steps of the deepest branch, we have a Blum complexity measure. So, Goldreich’s deﬁnition deﬁnes an acceptable Gödel numbering and we can form a complexity measure that satisﬁes Blum axioms. But, again, we have trouble with the “exponential speed-up” requirement. For instance, a machine trying to solve the sat- isﬁability problem would correctly return 1 for a satisﬁable instance, but no branch can write a 0 alone because it cannot be sure that instance is unsatisﬁable — so, the function would be undeﬁned for unsatisﬁable formulas. That is, unless NP = coNP. 457 CTIC - 35º Concurso de Trabalhos de Iniciação Científica Proposition 10. If there is a nondeterministic Turing machine that computes in polyno- mial time, according to Goldreich’s deﬁnition, the characteristic function of the satisﬁa- bility problem, then NP = coNP. 8 Proof. Suppose M is the machine that computes SAT’s characteristic function, under Goldreich’s deﬁnition, in polynomial time. The characteristic function of SAT is a total function, and its only outputs are 0 and 1. Therefore, in every computation of M, there is at least one branch that writes something different that ⊥ on the tape, and whatever it writes is the correct answer. So, if we convert this to a nondeterministic decider and invert the output (branches that write 0 will accept the input and vice-versa; branches that write ⊥ always reject), any satisﬁable formula will be rejected, because no branch of M ever writes 0 on the tape for these formulas; and any unsatisﬁable formula will be accepted, because at least one branch of M writes 0 for these formulas. Thus, we can decide SAT, the complement of SAT. Since SAT is coNP-complete, the existence of such a machine M would show that coNP ⊆ NP, and this implies that coNP = NP. 9 Therefore, even though Goldreich’s deﬁnition yields an acceptable Gödel number- ing and a Blum complexity measure, it also have trouble in transposing the exponential speed-up we have using nondeterminism. 3.3. Proposed deﬁnition Analyzing the problems with the ﬁrst two deﬁnitions, we know the nondeterministic ma- chine must be allowed to return several values (one for each branch) and somehow pick only one to be the value of the function. If M is any deterministic decider for the language L, we can create a machine that computes the characteristic function of L by running M and returning 1 if M accepted and 0 if it rejected. If we apply this transformation to a nondeterministic machine that recognizes the Boolean satisﬁability problem, then, when running this machine, we have three possible results. • For tautological formulas, the set of possible answers is only {1}. • For contradictory formulas, the set of answers is {0}. • For satisﬁable formulas that are not tautological, we have both values: {0, 1}. We want the return value for all satisﬁable formulas to be 1 and for unsatisﬁable formulas to be 0. Note that this corresponds exactly to the maximum value of each set; so, our def- inition of nondeterministic computation of functions will preserve exactly this behavior. Deﬁnition 11 (Proposed deﬁnition). Let M be a nondeterministic Turing machine, and x an input. If every branch of M halts when processing x, the value of the function 8 NP = coNP implies that NP = PH; that is, the polynomial hierarchy collapses to the ﬁrst level [Kozen 2006, p. 280]. 9 To see why coNP ⊆ NP implies coNP = NP, pick a language L ∈ NP. Its complement L is in coNP, by the deﬁnition of coNP. But by hypothesis, L is in NP, so, by the deﬁnition of coNP, its complement, L = L is in coNP, thus showing coNP = NP. Proof. On input (w, x), create two branches of computation. On the ﬁrst, write 1 on the tape and halt. On the second, simulate the universal Turing machine U in the input, and if U halts, write 0 on the tape and halt too. If w halts on x, there will be two halting branches of computation, each writing a different value in the tape, so, by deﬁnition, the function is not deﬁned on this input. If w never halts, then only the ﬁrst branch will halt (and with 1 written on the tape), so the function is deﬁned on this input and its value is 1. Therefore, under Hopcroft and Ullman’s deﬁnition, we can compute some non- computable functions, violating the requirement 1 of Gödel numberings. We can try to ﬁx this deﬁnition by forcing all branches to halt; but then, as all branches are required to return the same value, the machine will be (almost) determin- istic. Therefore, if there is a machine M that computes the characteristic function of the satisﬁability problem in nondeterministic polynomial time, we could simulate M on a given input, choosing (say) always the ﬁrst option when confronted with nondeterminism. If this branch of computation returns 1, then every branch returns 1 and the input is satisﬁ- able; if this branch returns 0, every branch returns 0 and the input is unsatisﬁable. We thus could solve SAT in deterministic polynomial time. So, with this restriction, we lose the apparent exponential speed-up in computation time we have when using nondeterminism. 3.2. Goldreich’s deﬁnition Deﬁnition 9 (Goldreich’s deﬁnition). Let ⊥ be some special symbol not in {0, 1} ∗ . (This symbol will represents “don’t know”.) A nondeterministic machine M com- putes the function f if, when processing the input x, both the following conditions hold [Goldreich 2008, p. 168]: • Every branch of M halts and outputs either f(x) or ⊥. • At least one branch of M halts with f(x) on the tape. The extra symbol ⊥ sidesteps the problems of a branch looping forever. This al- lows us to mechanically convert nondeterministic machines under Goldreich’s deﬁnition to deterministic machines via simulation — the deterministic machine just need to simu- late all branches until completion, to actually be sure every branch halts; if some branch do not halt, then the simulating machine will not halt either, but the function is not deﬁned in this case, so this behavior is correct. Thus, we only enumerate computable functions. To show the universal machine theorem and the S mn , we can simply ﬁrst convert the machine in question to a deter- ministic machine and use their theorems; thus, this deﬁnition yields an acceptable Gödel numbering. And, by counting the number of steps of the deepest branch, we have a Blum complexity measure. So, Goldreich’s deﬁnition deﬁnes an acceptable Gödel numbering and we can form a complexity measure that satisﬁes Blum axioms. But, again, we have trouble with the “exponential speed-up” requirement. For instance, a machine trying to solve the sat- isﬁability problem would correctly return 1 for a satisﬁable instance, but no branch can write a 0 alone because it cannot be sure that instance is unsatisﬁable — so, the function would be undeﬁned for unsatisﬁable formulas. That is, unless NP = coNP. XXXVI Congresso da Sociedade Brasileira de Computação 458 computed by M on x is the lexicographically maximum between all strings written in the computation branches. If some branch does not halt, leave the function undeﬁned in x. The same reasoning of Goldreich’s deﬁnition applies here; therefore, we have an acceptable Gödel numbering, and counting steps of the deepest branch (as in Goldreich’s deﬁnition) yields a Blum complexity measure. And, using exactly the algorithm mentioned above, we can compute the charac- teristic function of the satisﬁability problem under linear time; thus, this deﬁnition meets all the requirements proposed in the beginning of section 3. 3.3.1. Extending NP-completeness The last deﬁnition provides an extension of the class NP to function computation, so the next step is extend the concept of NP-completeness. Call FNP the class of all functions computable in polynomial time, under our deﬁnition 10 . A language L is NP-complete if both L ∈ NP and every language in NP reduces to L; that is, for every language L ∈ NP, there is a polynomial-time computable function f such that, for every x, x ∈ L if and only if f(x) ∈ L. (We are using Karp reductions here [Arora and Barak 2009, p. 42].) If we rephrase in terms of the characteristic functions 1 L and 1 L , of L and L , respectively, we have 1 L (x) = 1 L (f (x)) for all x. We will generalize speciﬁcally this equation to deﬁne FNP- completeness. Deﬁnition 12. A function f is FNP-complete if f ∈ FNP and, for every function g in FNP , there is a polynomial-time computable function h such that g(x) = f (h(x)) for every x ∈ {0, 1} ∗ . We can construct a FNP-complete function based on the halting problem: deﬁne f : {0, 1} ∗ ×N → {0, 1} ∗ such that f(w, n) is the lexicographically greatest value written by any branch of w after running for n steps. Such functions are FNP-complete because they simulate Turing machines directly. However, this deﬁnition is very rigid and allow for few functions to be FNP-complete; the requirement of directly returning the output of the function g above restricts the class of FNP-complete functions to functions that perform simulations. 3.4. Krentel’s OptP class The next two authors were not speciﬁcally concerned with nondeterministic computation of functions, but rather in generalizing the NP class for functions. Therefore, the corre- sponding notion of NP-completeness behave better than our proposed generalization. Krentel’s deﬁnition, in particular, are very similar to ours. 10 Note that this deﬁnition is different from the one given by Papadimitriou [Papadimitriou 1994, p 229]. 459 CTIC - 35º Concurso de Trabalhos de Iniciação Científica Deﬁnition 13. A function f : {0, 1} ∗ → N is in OptP if there is some nondeterministic Turing machine M such that [Krentel 1988, p. 493]: • For every input, every branch of M halts within a polynomial number of steps and writes in its tape a number in binary; and • Either, for all x, the largest number written by M on x is f(x), or, for all x, the smallest number written by M on x is f(x). Therefore, Krentel’s OptP class contains the optimization problems that can be “solved” in polynomial time by nondeterministic Turing machines. (Note we must always take the maximum value, or always take the minimum value.) The deﬁnition of OptP- completeness, however, is signiﬁcantly different. Deﬁnition 14. A function f is OptP-complete if f ∈ OptP and, for every function g ∈ OptP , there are two functions T 1 : {0, 1} ∗ → {0, 1} ∗ and T 2 : {0, 1} ∗ × N → {0, 1} ∗ , both computable in deterministic polynomial time, such that, for all x, g(x) = T 2 x, f (T 1 (x)) . That is, besides the preprocessing function T 1 , we are allowed to make a post- processing which have access both to the input x and to the “reduced output” f(T 1 (x)) . Under this deﬁnition, the traveling salesperson problem and 0 − 1 integer linear program- ming are both OptP-complete [Krentel 1988, p 495]. 3.5. Valiant’s #P class Deﬁnition 15 (Valiant’s deﬁnition). A nondeterministic machine M computes a function f : {0, 1} ∗ → N if, for every input x, M halts on every branch 11 and the number of accepting branches of computation is f(x) [Valiant 1979, p. 191]. The class #P is the set of functions computed in polynomial time, under Valiant’s deﬁnition. #P-completeness is deﬁned through oracles; that is, a function f is #P- complete if f ∈ #P and #P ⊆ FP f (that is, every function of #P can be computed by a deterministic machine with access to an oracle that computes f) [Valiant 1979, p. 191]. Besides problems like counting the number of satisfying assignments for a given formula, Valiant also proves less trivial problems are #P-complete, like the task of com- puting the permanent of a matrix [Valiant 1979, p. 194]. Therefore, this deﬁnition is also ﬂexible, like Krentel’s. Krentel note that both his and Valiant’s deﬁnition arise from applying an associa- tive operator to all values returned in the branches of computation — maximum/minimum in Krentel’s case, and cardinality (counting) in Valiant’s case. Therefore, using other asso- ciative operations yield alternative deﬁnitions of nondeterministic function computation [Krentel 1988, p. 493]. 4. Concluding Remarks As we have seen, it is possible to associate nondeterministic Turing machines with func- tion computation, although the association is not so straightforward as with deterministic machines. 11 Valiant did not include the requirement of halting in his deﬁnition, but we will include it to avoid having the same problems of Hopcroft and Ullman’s deﬁnition. computed by M on x is the lexicographically maximum between all strings written in the computation branches. If some branch does not halt, leave the function undeﬁned in x. The same reasoning of Goldreich’s deﬁnition applies here; therefore, we have an acceptable Gödel numbering, and counting steps of the deepest branch (as in Goldreich’s deﬁnition) yields a Blum complexity measure. And, using exactly the algorithm mentioned above, we can compute the charac- teristic function of the satisﬁability problem under linear time; thus, this deﬁnition meets all the requirements proposed in the beginning of section 3. 3.3.1. Extending NP-completeness The last deﬁnition provides an extension of the class NP to function computation, so the next step is extend the concept of NP-completeness. Call FNP the class of all functions computable in polynomial time, under our deﬁnition 10 . A language L is NP-complete if both L ∈ NP and every language in NP reduces to L; that is, for every language L ∈ NP, there is a polynomial-time computable function f such that, for every x, x ∈ L if and only if f(x) ∈ L. (We are using Karp reductions here [Arora and Barak 2009, p. 42].) If we rephrase in terms of the characteristic functions 1 L and 1 L , of L and L , respectively, we have 1 L (x) = 1 L (f (x)) for all x. We will generalize speciﬁcally this equation to deﬁne FNP- completeness. Deﬁnition 12. A function f is FNP-complete if f ∈ FNP and, for every function g in FNP , there is a polynomial-time computable function h such that g(x) = f (h(x)) for every x ∈ {0, 1} ∗ . We can construct a FNP-complete function based on the halting problem: deﬁne f : {0, 1} ∗ ×N → {0, 1} ∗ such that f(w, n) is the lexicographically greatest value written by any branch of w after running for n steps. Such functions are FNP-complete because they simulate Turing machines directly. However, this deﬁnition is very rigid and allow for few functions to be FNP-complete; the requirement of directly returning the output of the function g above restricts the class of FNP-complete functions to functions that perform simulations. 3.4. Krentel’s OptP class The next two authors were not speciﬁcally concerned with nondeterministic computation of functions, but rather in generalizing the NP class for functions. Therefore, the corre- sponding notion of NP-completeness behave better than our proposed generalization. Krentel’s deﬁnition, in particular, are very similar to ours. 10 Note that this deﬁnition is different from the one given by Papadimitriou [Papadimitriou 1994, p 229]. XXXVI Congresso da Sociedade Brasileira de Computação 460 Through the use of the notions of acceptable Gödel numberings and Blum axioms, we formalized the notion of “reasonable” deﬁnition for nondeterministic function compu- tation, and by consequence we formalized what is a “generalization of NP to functions”. Krentel’s and Valiant’s deﬁnitions, besides generalizing NP, in particular, also allow for a ﬂexible generalization of NP-completeness — that is, they allow for interesting problems to be “functionally NP-complete”, under each deﬁnition. 5. Project Development Tiago Royer studied this problem of associating a nondeterministic machine with a func- tion in his undergraduate thesis 12 , under the supervision of Jerusa Marchi. After ﬁnding Hopcroft and Ullman’s deﬁnition (section 3.1) and noting it yields a computation that is very close to be deterministic, he devised the deﬁnition of section 3.3 (using the concept of acceptable Gödel numberings and Blum axioms to be sure his deﬁnition would not bee too unreasonable). As noted in section 3.3.1, his generalization to NP and NP-completeness are very rigid. Krentel’s and Valiant’s deﬁnitions (which were discovered later in the project), although not created speciﬁcally to associate nondeterministic machine with functions, provides a more elegant generalization of NP and NP-completeness; this paper summarize all these ﬁndings under the light of Gödel numberings and Blum axioms. References Arora, S. and Barak, B. (2009). Computational Complexity - A Modern Approach. Cam- bridge University Press. Blum, M. (1967). A machine-independent theory of the complexity of recursive functions. J. ACM, 14(2):322–336. Gasarch, W. I. (2012). Guest column: the second P =? NP poll. SIGACT News, 43(2):53– 77. Goldreich, O. (2008). Computational complexity - a conceptual perspective. Cambridge University Press. Hopcroft, J. E. and Ullman, J. D. (1979). Introduction to Automata Theory, Languages and Computation. Addison-Wesley. Kozen, D. (2006). Theory of Computation. Texts in Computer Science. Springer. Krentel, M. W. (1988). The complexity of optimization problems. Journal of Computer and System Sciences, 36(3):490 – 509. Papadimitriou, C. H. (1994). Computational complexity. Addison-Wesley. Rogers, Jr., H. (1987). Theory of recursive functions and effective computability (Reprint from 1967). MIT Press, Cambridge, MA, USA. Selman, A. L. (1994). A taxonomy of complexity classes of functions. Journal of Com- puter and System Sciences, 48(2):357–381. Valiant, L. G. (1979). The complexity of computing the permanent. Theoretical Computer Science, 8:189–201. 12 The project was developed while he was an undergraduate student at Federal University of Santa Cata- rina (UFSC). Currently, he is pursuing his master’s degree at the University of São Paulo (USP). Dostları ilə paylaş:

Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2019
rəhbərliyinə müraciət Ana səhifə