Search

Multivalued functions are common in computable analysis (built upon the Type 2 Theory of Effectivity), and have made an appearance in complexity theory under the moniker search problems leading to complexity classes such as PPAD and PLS being studied. However, a systematic investigation of the resulting degree structures has only been initiated in the former situation so far (the Weihrauch-degrees).A more general understanding is possible, if the category-theoretic properties of multivalued functions are taken into account. In the present paper, the category-theoretic framework is established, and it is demonstrated that many-one degrees of multivalued functions form a distributive lattice under very general conditions, regardless of the actual reducibility notions used (e.g. Cook, Karp, Weihrauch).Beyond this, an abundance of open questions arises. Some classic results for reductions between functions carry over to multivalued functions, but others do not. The basic theme here again depends on category-theoretic differences between functions and multivalued functions. [ABSTRACT FROM PUBLISHER]

This paper investigates the complexity of real functions through proof techniques inspired by formal language theory. Productiveness, which is a stronger form of non-recursive enumerability, is employed to analyze the complexity of various problems related to real functions. Our work provides a deep reexamination of Hilbert's tenth problem and the equivalence to the identically 0 function problem, extending the undecidability results of these problems into the realm of productiveness. Additionally, we study the complexity of the equivalence to the identically 0 function problem over different domains. We then construct highly efficient many-one reductions to establish Rice-style theorems for the study of real functions. Specifically, we show that many predicates, including those related to continuity, differentiability, uniform continuity, right and left differentiability, semi-differentiability, and continuous differentiability, are as hard as the equivalence to the identically 0 function problem. Due to their high efficiency, these reductions preserve nearly any level of complexity, allowing us to address both complexity and productiveness results simultaneously. By demonstrating these results, which highlight a more nuanced and potentially more intriguing aspect of real function theory, we provide new insights into how various properties of real functions can be analyzed. [ABSTRACT FROM AUTHOR]

Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for nonuniform completeness vs uniform complessness in NP. Under various hypotheses, we obtain the following separations: There is a set complete for NP under nonuniform many-one reductions, but not under uniform many-one reductions. This is true even with a single bit of nonuniform advice. There is a set complete for NP under nonuniform many-one reductions with polynomial-size advice, but not under uniform Turing reductions. That is, polynomial nonuniformity cannot be replaced by a polynomial number of queries. For any fixed polynomial p(n), there is a set complete for NP under uniform 2-truth-table reductions, but not under nonuniform many-one reductions that use p(n) advice. That is, giving a uniform reduction a second query makes it impossible to simulate by a nonuniform reduction with fixed polynomial advice. There is a set complete for NP under nonuniform many-one reductions with polynomial advice, but not under nonuniform many-one reductions with logarithmic advice. This hierarchy theorem also holds for other reducibilities, such as truth-table and Turing. We also consider uniform upper bounds on nonuniform completeness. Hirahara (2015) showed that unconditionally every set that is complete for NP under nonuniform truth-table reductions that use logarithmic advice is also uniformly Turing-complete. We show that under a derandomization hypothesis, every set that is complete for NP under nonuniform truth-table reductions is also uniformly truth-table complete. [ABSTRACT FROM AUTHOR]

We settle the question of where exactly do the reduced Kronecker coefficients lie on the spectrum between the Littlewood-Richardson and Kronecker coefficients by showing that every Kronecker coefficient of the symmetric group is equal to a reduced Kronecker coefficient by an explicit construction. This implies the equivalence of an open problem by Stanley from 2000 and an open problem by Kirillov from 2004 about combinatorial interpretations of these two families of coefficients. Moreover, as a corollary, we deduce that deciding the positivity of reduced Kronecker coefficients is NP-hard, and computing them is #P-hard under parsimonious many-one reductions. Our proof also provides an explicit isomorphism of the corresponding highest weight vector spaces. [ABSTRACT FROM AUTHOR]

A pumping lemma for a class of languages C is often used to show particular languages are not in C . In contrast, we show that a pumping lemma for a class of languages C can be used to study the computational complexity of the predicate " ∈ C " via highly efficient many-one reductions. In this paper, we use extended regular expressions (EXREGs, introduced in Câmpeanu et al. (Int. J. Foundations Comput. Sci. 14(6), 1007–1018, 2003)) as an example to illustrate the proof technique and establish the complexity of the predicate "is an EXREG language" for several classes of languages. Due to the efficiency of the reductions, both productiveness (a stronger form of non-recursive enumerability) and complexity results can be obtained simultaneously. For example, we show that the predicate "is an EXREG language" is productive (hence, not recursively enumerable) for context-free grammars, and is Co-NEXPTIME-hard for context-free grammars generating bounded languages. The proof technique is easy to use and requires only a few conditions. This suggests that for any class of languages C having a pumping lemma, the language class comparison problems (e.g., does a given context-free grammar generate a language in C ?) are almost guaranteed to be hard. So, pumping lemmas sometimes could be "harmful" when studying computational complexity results. [ABSTRACT FROM AUTHOR]

Semi-unification is the combination of first-order unification and first-order matching. The undecidability of semi-unification has been proven by Kfoury, Tiuryn, and Urzyczyn in the 1990s by Turing reduction from Turing machine immortality (existence of a diverging configuration). The particular Turing reduction is intricate, uses noncomputational principles, and involves various intermediate models of computation. The present work gives a constructive many-one reduction from the Turing machine halting problem to semi-unification. This establishes RE-completeness of semi-unification under many-one reductions. Computability of the reduction function, constructivity of the argument, and correctness of the argument is witnessed by an axiom-free mechanization in the Coq proof assistant. Arguably, this serves as comprehensive, precise, and surveyable evidence for the result at hand. The mechanization is incorporated into the existing, wellmaintained Coq library of undecidability proofs. Notably, a variant of Hooper's argument for the undecidability of Turing machine immortality is part of the mechanization. [ABSTRACT FROM AUTHOR]

We mechanise the undecidability of various first-order axiom systems in Coq, employing the synthetic approach to computability underlying the growing Coq Library of Undecidability Proofs. Concretely, we cover both semantic and deductive entailment in fragments of Peano arithmetic (PA) as well as ZF and related finitary set theories, with their undecidability established by many-one reductions from solvability of Diophantine equations, i.e. Hilbert’s tenth problem (H10), and the Post correspondence problem (PCP), respectively. In the synthetic setting based on the computability of all functions definable in a constructive foundation, such as Coq’s type theory, it suffices to define these reductions as meta-level functions with no need for further encoding in a formalised model of computation. The concrete cases of PA and the considered set theories are supplemented by a general synthetic theory of undecidable axiomatisations, focusing on well-known connections to consistency and incompleteness. Specifically, our reductions rely on the existence of standard models, necessitating additional assumptions in the case of full ZF, and all axiomatic extensions still justified by such standard models are shown incomplete. As a by-product of the undecidability of set theories formulated using only membership and no equality symbol, we obtain the undecidability of first-order logic with a single binary relation. [ABSTRACT FROM AUTHOR]

We prove that deciding the vanishing of the character of the symmetric group is |$\textsf{C}_= \textsf{P}$| -complete. We use this hardness result to prove that the absolute value and also the square of the character are not contained in |$\textsf{#P}$|⁠ , unless the polynomial hierarchy collapses to the second level. This rules out the existence of any (unsigned) combinatorial description for the square of the characters. As a byproduct of our proof, we conclude that deciding positivity of the character is |$\textsf{PP}$| -complete under many-one reductions, and hence |$\textsf{PH}$| -hard under Turing reductions. [ABSTRACT FROM AUTHOR]

In this paper we give several generalized theorems concerning reducibility notions to certain complexity classes. We study classes that are either (I) closed under NP many-one reductions and polynomial-time conjunctive reductions or (II) closed under coNP many-one reductions and polynomial-time disjunctive reductions. We prove that, for such a class K, (1) reducibility notions of sets to K under polynomial-time constant-round truth-table reducibility, polynomial-time log-Turing reducibility, logspace constant-round truth-table reducibility, logspace log-Turing reducibility, and logspace Turing reducibility are all equivalent and (2) every set that is polynomial-time positive Turing reducible to a set in K is already in K. From these results, we derive some observations on the reducibility notions to CP and NP. [ABSTRACT FROM AUTHOR]

Attempts to prove the intractability of the Minimum Circuit Size Problem (\sansM \sansC \sansS \sansP) date as far back as the 1950s and are well motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing \sansM \sansC \sansS \sansP is intractable under worst-case assumptions. While Masek showed in the late 1970s that the version of \sansM \sansC \sansS \sansP for \sansD \sansN \sansF formulas is \sansN \sansP -hard, extending this result to the case of depth-3 AND/OR formulas was open. We show that determining the minimum size of a depth-d formula computing a given Boolean function is \sansN \sansP -hard under quasipolynomial-time randomized reductions for all constant d \geq 2. Our approach is based on a method to "lift"" depth-d formula lower bounds to depth-(d + 1). This method also implies the existence of a function with a 2\Omega d(n) additive gap between its depth-d and depth-(d + 1) formula complexity. We also make progress in the case of general, unrestricted circuits. We show that the version of \sansM \sansC \sansS \sansP where the input is a partial function (represented by a string in \{ 0, 1, \} \ast) is not in \sansP under the Exponential Time Hypothesis (ETH). Intriguingly, we formulate a notion of lower bound statements being (\sansP/\sansp \sanso \sansl \sansy)-recognizable that is closely related to Razborov and Rudich's definition of being (\sansP/\sansp \sanso \sansl \sansy)-constructive. We show that unless there are subexponential-sized circuits computing \sansS \sansA \sansT, the collection of lower bound statements used to prove the correctness of our reductions cannot be (\sansP/\sansp \sanso \sansl \sansy)-recognizable. [ABSTRACT FROM AUTHOR]

Let Γ be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in Γ is in LogSpace or complete for the class CSP(Γ)NP under deterministic polynomial-time many-one reductions. Here, CSP(Γ)NP is the class of problems that can be reduced to the constraint satisfaction problem of Γ under non-deterministic polynomial-time many-one reductions. [ABSTRACT FROM AUTHOR]

The Orbit problem is defined as follows: Given a matrix A∈ℚ and vectors x, y∈ℚ, does there exist a non-negative integer i such that A x= y. This problem was shown to be in deterministic polynomial time by Kannan and Lipton (J. ACM 33(4):808-821, ). In this paper we place the problem in the logspace counting hierarchy GapLH. We also show that the problem is hard for CL with respect to logspace many-one reductions. [ABSTRACT FROM AUTHOR]

Juedes and Lutz [SIAM J. Comput., 24 (1995), pp. 279-295] proved a small span theorem for polynomial-time many-one reductions in exponential time. This result says that for language A decidable in exponential time, either the class of languages reducible to A (the lower span) or the class of Problems to which A can be reduced (the upper span) is small in the sense of resource-bounded measure and, in particular, that the degree of A is small. Small span theorems have been proved for increasingly stronger polynomial-time reductions, and a small span theorem for polynomial-time Turing reductions would imply BPP ≠ EXP. In contrast to the progress in resource- bounded measure, Ambos-Spies et al. [Proceedings of the 16th IEEE Conference on Computational Complexity, Philadelphia, PA, IEEE Computer Society, Los Alamitos, CA, 2001, pp. 210-2171 showed that there is no small span theorem for the resource-bounded dimension of Lutz [SIA M J. Comput., 32 (2003), PP. 1236-1259], even for polynomial-time many-one reductions. Resource-bounded scaled dimension, recently introduced by Hitchcock, Lutz, and Mayordomo [J. Comput. System Sd., 69 (2004), pp. 97-122], Provides rescalings of resource-bounded dimension. We use scaled dimension to further understand the contrast between measure and dimension regarding polynomial-time spans and degrees. We strengthen prior results by showing that the small span theorem holds for polynomial-time many-one reductions in the -3rd-order scaled dimension, but fails to hold in the - 2nd-order scaled dimension. Our results also hold in exponential space. As an application, we show that determining the -2nd- or -1st-order scaled dimension in ESPACE of the many-one complete languages for E would yield a proof of P = BPP or P ≠ PSPACE. On the other hand, it is shown unconditionally that the complete languages for E have -3rd-order scaled dimension 0 in ESPACE and -2nd- and -1st-order scaled dimension 1 in E. [ABSTRACT FROM AUTHOR]

We show that the graph isomorphism problem is hard under DLOGTIME uniform AC0 many-one reductions for the complexity classes NL, PL (probabilistic logarithmic space) for every logarithmic space modular class ModκL and for the class DET of problems NC1 reducible to the determinant. These are the strongest known hardness results for the graph isomorphism problem and imply a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. We also investigate hardness results for the graph automorphism problem. [ABSTRACT FROM AUTHOR]

The constraint satisfaction problem (CSP) on a finite relational structure B is to decide, given a set of constraints on variables where the relations come from B, whether or not there is an assignment to the variables satisfying all of the constraints; the surjective CSP is the variant where one decides the existence of a surjective satisfying assignment onto the universe of B. We present an algebraic framework for proving hardness results on surjective CSPs; essentially, this framework computes global gadgetry that permits one to present a reduction from a classical CSP to a surjective CSP. We show how to derive a number of hardness results for surjective CSP in this framework, including the hardness of the disconnected cut problem, of the no-rainbow three-coloring problem, and of the surjective CSP on all two-element structures known to be intractable (in this setting). Our framework thus allows us to unify these hardness results and reveal common structure among them; we believe that our hardness proof for the disconnected cut problem is more succinct than the original. In our view, the framework also makes very transparent a way in which classical CSPs can be reduced to surjective CSPs. [ABSTRACT FROM AUTHOR]

A set is called r-closed left-r.e. iff every set r-reducible to it is also a left-r.e. set. It is shown that some but not all leftr. e. cohesive sets are many-one closed left-r.e. sets. Ascending reductions are many-one reductions via an ascending function; left-r.e. cohesive sets are also ascending closed left-r.e. sets. Furthermore, it is shown that there is a weakly 1-generic many-one closed left-r.e. set. We also consider initial segment complexity of closed left-r.e. sets. We show that initial segment complexity of ascending closed left-r.e. sets is of sublinear order. Furthermore, this is near optimal as for any non-decreasing unbounded recursive function g, there are ascending closed left-r.e. sets A whose plain complexity satisfies C(A(0)A(1) … A(n)) ≥ n/g(n) for all but finitely many n. The initial segment complexity of a conjunctively (or disjunctively) closed left-r.e. set satisfies, for all ε > 0, for all but finitely many n, C(A(0)A(1) … A(n)) ≤ (2 + ε) log(n). [ABSTRACT FROM AUTHOR]

The solution-graph of a Boolean formula on n variables is the subgraph of the hypercube Hn induced by the satisfying assignments of the formula. The structure of solution-graphs has been the object of much research in recent years since it is important for the performance of SAT-solving procedures based on local search. Several authors have studied connectivity problems in such graphs focusing on how the structure of the original formula might affect the complexity of the connectivity problems in the solution-graph. In this paper we study the complexity of the isomorphism problem of solution-graphs of Boolean formulas. We consider the classes of formulas that arise in the CSP-setting and investigate how the complexity of the isomorphism problem depends on the formula type. We observe that for general formulas the solution-graph isomorphism problem can be solved in exponential time while in the cases of 2CNF formulas, as well as for CPSS formulas, the problem is in the counting complexity class C=P, a subclass of PSPACE. We also prove a strong property on the structure of solution-graphs of Horn formulas showing that they are just unions of partial cubes. In addition, we give a PSPACE lower bound for the problem on general Boolean functions. We prove that for 2CNF, as well as for CPSS formulas the solution-graph isomorphism problem is hard for C=P under polynomial time many-one reductions, thus matching the given upper bound. [ABSTRACT FROM AUTHOR]

The 2-D Tucker search problem is shown to be PPA-hard under many-one reductions; therefore it is complete for PPA. The same holds for k -D Tucker for all k ≥ 2. This corrects a claim in the literature that the Tucker search problem is in PPAD. [ABSTRACT FROM AUTHOR]