Algebraic characterizations of the computational aspects of functions defined over the real numbers provide very effective tool to understand what computability and complexity over the reals, and generally over continuous spaces, mean. This is relevant for both communities of computer scientists and mathematical analysts, particularly the latter who do not understand (and or like) the language of machines and string encodings. Recursive analysis can be considered the most standard framework of computation over continuous spaces, it is however defined in a very machine specific way which does not leave much to intuitiveness. Recently several characterizations, in the form of function algebras, of recursively computable functions and some sub-recursive classes were introduced. These characterizations shed light on the hidden behavior of recursive analysis as they convert complex computational operations on sequences of real objects to "simple" intuitive mathematical operations such as integration or taking limits. The authors previously presented a framework for obtaining algebraic characterizations at the complexity level over compact domains. The current paper presents a comprehensive extension to that framework. Though we focus our attention in this paper on functions defined over the whole real line, the framework, and accordingly the obtained results, can be easily extended to functions defined over arbitrary domains.
We prove our results by relating the notion of polytime (polynomial time) computable functions over the reals (arbitrary domains) to the corresponding notion over the integers. This gives a direct way to lift algebraic characterizations of integer computability and complexity to algebraic characterizations of the corresponding analog notions. Our setting is actually proved to be robust to approximations. One does not need to be able to compute exactly the computability and or complexity class over the integers, but only some defined approximation of it in order to be able to compute the corresponding class over the reals. This can be seen as a way to reformulate reprove reread very nicely some constructions already used in @cite_7 @cite_16 .
@cite_16 @cite_7
2044637393 2084050956 2130190334 2159268377
We look at the hypothesis that all honest onto polynomial-time computable functions have a polynomial-time computable inverse. We show this hypothesis equivalent to several other complexity conjectures including: • In polynomial time, one can find accepting paths of nondeterministic polynomial-time Turing machines that accept Σ*. • Every total multivalued nondeterministic function has a polynomial-time computable refinement. • In polynomial time, one can compute satisfying assignments for any polynomial-time computable set of satisfiable formulae. • In polynomial time, one can convert the accepting computations of any nondeterministic Turing machine that accepts SAT to satisfying assignments.We compare these hypotheses with several other important complexity statements. We also examine the complexity of these statements where we only require a single bit instead of the entire inverse. We show that, over Q, if an n-variate polynomial of degree d = nO(1) is computable by an arithmetic circuit of size s (respectively by an arithmetic branching program of size s) then it can also be computed by a depth three circuit (i.e. a ΣΠΣ-circuit) of size exp(O(√(d log n log d log s))) (respectively of size exp(O(√(d log n log s))). In particular this yields a ΣΠΣ circuit of size exp(O(√(d log d))) computing the d × d determinant Detd. It also means that if we can prove a lower bound of exp(omega(√(d log d))) on the size of any ΣΠΣ-circuit computing the d × d permanent Permd then we get super polynomial lower bounds for the size of any arithmetic branching program computing Permd. We then give some further results pertaining to derandomizing polynomial identity testing and circuit lower bounds. The ΣΠΣ circuits that we construct have the property that (some of) the intermediate polynomials have degree much higher than d. Indeed such a counterintuitive construction is unavoidable - it is known that in any ΣΠΣ circuit C computing either Detd or Perm_d, if every multiplication gate has fanin at most d (or any constant multiple thereof) then C must have size at least exp(Ω(d)). We develop new techniques for deriving strong computational lower bounds for a class of well-known NP-hard problems. This class includes weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(n^k) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k)n^o^(^k^) for any function f, even if we restrict the parameter values to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be of the order @Q(@m(n)) for any reasonable function @m, no algorithm of running time n^o^(^k^) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds on the computational complexity are also derived for other NP-hard problems in the above class. Our techniques can be further extended to derive computational lower bounds on polynomial time approximation schemes for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1 @e)n^o^(^1^ ^@e^) for any function f unless an unlikely collapse occurs in parameterized complexity theory. We study the complexity of computing the kth-power of an element of F2n by constant depth arithmetic circuits over F2 (also known as ACP). Our study encompasses the complexity of basic arithmetic operations such as computing cube-root and computing cubic-residuosity of elements of F2n. Our main result is that these problems require exponential size circuits. We also derive strong average-case versions of these results. For example, we show that no subexponential-size, constant-depth, arithmetic circuit over F2 can correctly compute the cubic residue symbol for more than 1 3 + o(1) fraction of the elements of F2n. As a corollary, we deduce a character sum bound showing that the cubic residue character over F2n is uncorrelated with all degree-d n-variate F2 polynomials (viewed as functions over F2n in a natural way), provided d l ne for some universal e > 0. Classical methods (based on van der Corput differencing and the Weil bounds) show this only for d l log(n). Our proof revisits the classical Razborov-Smolensky method for circuit lower bounds, and executes an analogue of it in the land of univariate polynomials over F2n. The tools we use come from both F2n and F2n. In recent years, this interplay between F2n and F2n has played an important role in many results in pseudorandomness, property testing and coding theory.