Suppose that $a$ and $d$ are positive integers with $a \geq 2$. Let $h_{a,d}(n)$ be the largest integer $t$ such that any set of $n$ points in $\mathbb{R}^d$ contains a subset of $t$ points for which all the nonzero volumes of the ${t \choose a}$ subsets of order $a$ are distinct. Beginning with Erdös in 1957, the function $h_{2,d}(n)$ has been closely studied and is known to be at least a power of $n$. We improve the best known bound for $h_{2,d}(n)$ and show that $h_{a,d}(n)$ is at least a power of $n$ for all $a$ and $d$.

Abstract Higman essentially showed that ifA is anylanguage then SUBSEQ(A) is regular, where SUBSEQ(A) is the language of all subsequences of strings inA. Lets1,s2,s3,… be the standard lexico-graphic enumeration of all strings over some finite alphabet. We consider the following inductive inference problem:A(s1),A(s2),A(s3),…, learn, in the limit, a DFA for SUBSEQ(A). We consider this model of learning and the variants of it that are usually studied in Inductive Inference: anomalies, mind-changes, teams, and combinations thereof. This paper is a significant revision and expansion of an earlier conference version [10].

There are several ways around the all-too-common ‘bad news’ of NP-completeness. To name two prominent algorithmic strategies: (i) one can look into approximating the solution; (ii) one can look into algorithms that work well on the particular kind of instances likely to be encountered, also known as heuristics. There is another approach that the books under consideration are about, called Fixed Parameter Tractability. Many NP-complete problems are of the form ... If k is fixed then the problem Ak = {G|G has property P(k)} is often solvable in polynomial time, in many cases by trivial, brute-force algorithms that, for example, ‘try all k-subsets’. Such naive algorithms typically yield a polynomial bound on the running time whose exponent depends on k. Some problems of this form, however, admit clever, and sometimes extremely deep algorithms—the Graph Minors problem being one prominent example—where, for fixed k, there is a solution in time O(f(k)nO(1)). Here, the O(1) does not depend on k. Depending on how bad the function f is (which is expected to be exponential in k, since we are discussing NP-hard problems), such algorithms can be, for small (and even moderate) values of k, fast and useful. Indeed, practical algorithms of this sort have been known and used since the beginnings of Computer Science. The algorithmic practice of cleverly exploiting limited natural parameters of computational problems predates the theory of parameterized complexity that ‘gave this phenomenon a name’. Such parameterized problems are now called Fixed Parameter Tractable (FPT), in the mathematical theory under discussion.

The 'Aha!' phenomenon is familiar to us in many domains including computer science and mathematics (e.g., [2,3,6]). It often stems from an unexpected point of view that illuminates an appealing solution path. The 'Aha' reaction is common to all. Its occurrence is related to the problem-solvers' common perspectives and solution repertoires. Whether more frequent or less frequent, 'Aha' occurrences enrich and strengthen perspectives and repertoires in a stimulating manner.Consider the following Ladder Problem: calculate the number of different ways to climb an N-stage ladder when each step is either one or two stages. One solution perspective may be 'forward reasoning', leading to a systematic accumulation of the possible climbing paths. Another perspective may be combinatorial, leading to the calculation of all the combinations of 1 and 2 that sum to N. A third perspective may be 'backward reasoning', yielding recursive decomposition of the Nth case into the N-1 and N-2 cases.Some problem-solvers may fairly quickly invoke the third perspective and elegantly obtain the Nth Fibonacci number. Others may first follow one of the other perspectives and later realize the illuminating third perspective. The 'Aha' reactions among the solvers may vary. However, both less experienced and more experienced solvers will gain from recognizing the relevance and elegance of the recursive decomposition and enhance their problem-solving repertoires.

Let f:{0, 1}/sup n//spl times/{0, 1}/sup n//spl rarr/{0, 1}. Assume Alice has x/sub 1/, ..., x/sub k//spl isin/{0, 1}/sup n/, Bob has y/sub 1/, ..., y/sub k//spl isin/{0, 1}/sup n/, and they want to compute f(x/sub 1/, y/sub 1/)/spl middot//spl middot//spl middot/f(x/sub k/, y/sub k/) communicating as few bits as possible. The Direct Sum Conjecture of Karchmer, Raz, and Wigderson, states that the obvious way to compute it (computing f(x/sub 1/, y/sub 1/), then f(x/sub 2/, y/sub 2/), etc.) is, roughly speaking, the best. This conjecture arose in the study of circuits. Since a variant of it implies NC/sup 1//spl ne/NC/sup 2/. We consider three related problems. Enumeration: Alice and Bob output e/spl les/2/sup k/-1 elements of {0, 1}/sup k/: one of which is f(x/sub 1/, y/sub 1/)/spl middot//spl middot//spl middot/f(x/sub k/, y/sub k/). Elimination: Alice and Bob output an element of {0, 1}/sup k/ that is not f(x/sub 1/ y/sub 1/)/spl middot//spl middot//spl middot/f(x/sub k/, y/sub k/) Selection: (k=2) Alice and Bob output i/spl sim/{1,2} such that if f(x/sub 1/, y/sub 1/)=1 V f(x/sub 2/, Y/sub 2/)=1 then f(x/sub i/, y/sub i/)=1. We establish lower bounds on ELIM(f/sup k/) for particular f and connect the complexity of ELIM(f/sup k/), ENUM(k, f/sup k/), and SELECT(f/sup 2/) to the direct sum conjecture and other conjectures.

Abstract For a fixed set A. the number of queries to A needed in order to decide a set S is a measure of S's complexity. We consider the complexity of certain sets defined in terms of A: and, for m > 2, where #nA. (x1….. xn) = A(x1) + A(xn)(We identify with , where χA is the characteristic function of A.) If A is a nonrecursive semirecursive set or if A is a jump, we give tight bounds on the number of queries needed in order to decide ODDnA and MODmnA: • ODDnA can be decided with n parallel queries to A, but not with n − 1. • ODDnA can be decided with ⌈log(n + 1)⌉ sequential queries to A but not with ⌈log(n + 1)⌉ − 1. • MODmnA can be decided with ⌈n/m⌉ + ⌊n/m⌋ parallel queries to A but not with ⌈n/m⌉ + ⌊n/m⌋ − 1. • MODmnA can be decided with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ sequential queries to A but not with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ − 1. The lower bounds above hold for nonrecursive recursively enumerable sets A as well. (Interestingly, the lower bounds for recursively enumerable sets follow by a general result from the lower bounds for semirecursive sets.) In particular, every nonzero truth-table degree contains a set A such that ODDnA cannot be decided with n − 1 parallel queries to A. Since every truth-table degree also contains a set B such that ODDnB can be decided with one query to B, a set's query complexity depends more on its structure than on its degree. For a fixed set A, Q(n, A) = {S: S can be decided with n sequential queries to A}. Q∥ (n, A) = {S : S can be decided with n parallel queries to A}. We show that if A is semirecursive or recursively enumerable, but is not recursive, then these classes form non-collapsing hierarchies: • Q(0,A) ⊂ Q (1, A) ⊂ Q(2, A) ⊂ … Q∥ (0, A) ⊂ Q∥ (1, A) ⊂ Q∥ (2, A) ⊂ … The same is true if A is a jump.

We demonstrate the use of Kolmogorov complexity in average case analysis of algorithms through a classical example: adding two n-bit numbers in [log2 n] + 2 steps on average. We simplify the analysis of Burks et al. (1961) and (in more complete forms) Briley (1973) and Schay (1995).

The usual focus of recursion-theoretic inductive inference is to infer a program (resp.grammar) for a function f (resp.language A) from observations and/or queries about f (resp.A).We propose a new line of research which examines the question of inferring the answers to querzes.For a given class of recursive funct,ions, we consider t,he learning (in the limit) of propwtzes of these funct,ions that can be captured by queries formulated in a logical language L. We st,udy t,he inference types that arise in this context, and we present preliminary results.Of particular interest is a comparison between the learning of properties and the learning of programs.Our results suggest that these two types of learning are incomparable.In addit,ion, our techniques can be used to prove a general theorem about query inference IGS92].We show that ZcJ* QW) c QJ'P)for many standard inference t)ypes 1, J and many query languages L. Hence any separation that, holds between these inference types also holds between the corresponding query inference types.One bizarre consequence is that [24,49lQEX,([S ucc, <I')-[2,4]QEX,([Succ, <12)# 0. IntroductionWhen scientist,s look at data, they may be trying to answer some question about, the dat,a (e.g., "Is the shape l

This paper investigates the computational complexity of approximating several \NP-optimization problems using the number of queries to an \NP\ oracle as a complexity measure. The results show a tradeoff between the closeness of the approximation and the number of queries required. For an approximation factor $k(n)$, $\log \log_{k(n)} n$ queries to an \NP\ oracle can be used to approximate the maximum clique size of a graph within a factor of $k(n)$. However, this approximation cannot be achieved using fewer than $\log \log_{k(n)} n - c$ queries to any oracle unless $\Pe = \NP$, where c is a constant that does not depend on k. These results hold for approximation factors $k(n) \geq 2$ that belong to a class of functions which includes any integer constant function, $\log n$, $\log^{a} n$, and $n^{1/a}$. Similar results are obtained for Graph Coloring, Set Cover, and other \NP-optimization problems.

There have been several papers over the last ten years that consider the number of queries needed to compute a function as a measure of its complexity. The following function has been studied extensively in that light: FaA(x1,…,xa) = A(x1)…A(xa). We are interested in the complexity (in terms of the number of queries) of approximating FaA. Let b ⩽ a and let f be any function such that FaA(x1,…,xa) and f(x1,…,xa) agree on at least b bits. For a general set A we have matching upper and lower bounds on f that depend on coding theory. These are applied to get exact bounds for the case where A is semirecursive, A is superterse, and (assuming P ≠ NP) A = SAT. We obtain exact bounds when A is the halting problem using different methods.

In [5, 6] the following question was considered: how much can an inductive inference machine learn if it is augmented with the ability to ask questions (about the

Most work in the field of inductive inference regards the learning machine to be a passive recipient of data. In a prior paper the passive approach was compared to an active form of learning where the machine is allowed to ask questions. In this paper we continue the study of machines that ask questions by comparing such machines to teams of passive machines. This yields, via work of Pitt and Smith, a comparison of active learning with probabilistic learning. Also considered are query inference machines that learn an approximation of what is desired. The approximation differs from the desired result in finitely many anomalous places.

This paper investigates the computational complexity of approximating NP-optimization problems using the number of queries to an NP oracle as a complexity measure. The results show a trade-off between the closeness of the approximation and the number of queries required. For an approximation factor k(n), loglog/sub k(n/) n queries to an NP oracle can be used to approximate the maximum clique size of a graph within a factor of k(n). However, this approximation cannot be achieved using fewer than loglog/sub k(n/) n-c queries to any oracle unless P=NP, where c is a constant that does not depend on k. These results hold when k(n) belongs to a class of functions which include any integer constant function, log n, log/sup a/ n and n/sup 1/a/. Similar results are obtained for graph coloring, set cover and other NP-optimization problems.>

Most theories of learning consider inferring a function f from either (1) observations about f or, (2) questions about f. We consider a scenario whereby the learner observes fand asks queries to some set A. EX[A] is the set of concept classes EX-learnable by an inductive inference machine with oracle A. A and F are EX-equivalent if EX[A] = EX[B]. The equivalence classes induced are the degrees of inferability. We prove several results about these degrees: (1) There are an uncountable number of degrees. (2) For A r.e., REC e BC[A] iff O'' ≤T A´, and there is evidence this holds for all sets A. (3) For A, B r.e., A ≡T B iff EX[A] = EX[B]. (4) There exists A, B low2 r.e., A|RB, EX[A] = EX[B]. (hence (3) is optimal).

Traditional work in inductive inference has been to model a learner receiving data about a function f and trying to learn the function. The data is usually just the values f (0), f (1),…. The scenario is modeled so that the learner is also allowed to ask questions about the data (e.g., (∀ χ) [χ> 17 → f ( χ ) = 0]?). An important parameter is the language that the lerner may use to formulate queries. We show that for most languages a learner can learn more by asking questions than by passively receiving data. Mathematical tools used include the solution to Hilbert's tenth problem, the decidability of Presuburger arithmetic, and ω-automata.

Abstract We prove that the set of all recursive functions cannot be inferred using first-order queries in the query language containing extra symbols [+ , <]. The proof of this theorem involves a new decidability result about Presburger arithmetic which is of independent interest. Using our machinery, we show that the set of all primitive recursive functions cannot be inferred with a bounded number of mind changes, again using queries in [+, <]. Additionally, we resolve an open question in [7] about passive versus active learning.

We examine the problem of coloring a subgraph of a k-colorable graph without knowing the entire graph. Our results are phrased in terms of a game with two players: (a) the Mapmaker, who must color a fixed set X of vertices in a manner extendible to a k-coloring of the entire graph, and (b) the Explorer, who adds vertices and edges to the graph, hoping to force the Mapmaker to change his mind many times about how to color X. We show that if k ≥ 3, then the Explorer can force an exponential number of mind-changes; but if k = 2, then she can only force a linear number of mind-changes. Applications to recursive graph theory are given.

A recursive graph is a graph whose edge set and vertex set are both recursive. Although the chromatic number of a recursive graph G (denoted #(G)) cannot be determined recursively, it can be determined if queries to the halting set are allowed. We show that the problem of determining the chromatic number of a recursive graph with a minimum number of queries to the halting set, is closely related to the unbounded search problem. In particular if f is a non-decreasing function such that P i#0 2 -f(i) is effectively computable, then there is an algorithm to determine #(G) with f(#(G)) queries to K i# P i#0 2 -f(i) # 1 (i.e., f satisfies Kraft's inequality). We also investigate recursive chromatic numbers (which require queries to a set much harder than the halting set, namely # ### ), the effect of allowing queries to a weaker set, and the effect of being able to ask p queries at a time. Most of our results are also true for highly recursive graphs (graphs where one can determine t...

A query-bounded Turing machine is an oracle machine which computes its output function from a bounded number of queries to its oracle. In this paper we investigate the behavior of nondeterministic query-bounded Turing machines. In particular we study how easily such machines can compute the function F A n (x 1 , . . . , x n ) from A, where A # N and F A n (x 1 , . . . , x n ) = ##A (x 1 ), . . . , #A (x n )#. We show that each truth-table degree contains a set A such that, F A n can be nondeterministically computed from A by asking at most one question per nondeterministic branch; and that every set of the form A # also has this property. On the other hand, we show that if A is a 1-generic set then F A n cannot be nondeterministically computed from A in less that n queries to A; and that each non-zero r.e. Turing degree contains an r.e. set A with the same property. If the machines involved can only make queries that are part of their input then all sets such that F A n ca...

Intuitively, the more a machine knows the more it can learn. This intuition is formalized in a recursion theoretic framework. A formal definition of what it means for a machine to learn a finite sequence of recursive functions is presented. We prove that there are sets of sequences S, and a sequence 〈ƒ1, ƒ2, …, ƒn〉ϵ S such that in order to learn a program for ƒi a machine must necessarily know programs for ƒ1, …, ƒi−1. Also investigated is the simultaneous inference of programs for a finite set of recursive functions.

The power of various query languages is compared along two dimensions, namely the inherent power of the language and the number of alternations of quantizers. Learning by asking questions is compared to learning by passively reading data. It is found that the extent of what can be learned by queries is largely dependent on the language used by the inference mechanism to formulate questions to ask of its trainer. It is proved that inference machines that are allowed to ask first-order questions with plus and times can be used to solve the halting problem and therefore can learn all the recursive functions. Learning languages are also considered.>

We construct oracles that force all possible relationships between ${\textit{NP}}$ and ${\textit{EXP}}_K = {\textit{DTIME}}(2^{O(n^k )} )$. We generalize these results to obtain a theorem about oracles that force relationships between deterministic and nondeterministic (and alternating) classes, from which many corollaries follow. The corollaries are interesting because we compare a powerful type of machine (e.g., nondeterministic, alternating) to a less powerful type of machine that can use more time. One of our corollaries is that the result ${\textit{DTIME}}(n\log ^ * (n)) \subseteq \Sigma _2 - {\text{TIME}}(n)$ does not relativize.