Search

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]

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]

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]

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]

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 study the complexity of a restricted version of the universality problem: testing equivalence to { 0 , 1 } ⁎ for languages that are either { 0 , 1 } ⁎ or { 0 , 1 } ⁎ − { w } where w ∈ { 0 , 1 } ⁎. We show that this restricted problem for multi-pattern languages (MPL) is NP-hard, and for multi-pattern languages with regular substitutions (MPL REG) is not recursively enumerable. Moreover, this undecidability result holds for any class of languages that effectively contains { w # w | w ∈ { 0 , 1 } ⁎ } , and is effectively closed under union, and concatenation with regular sets. Consequently, it has broad applicability and extends to many generalizations of regular languages. Sufficient conditions are then presented for a language predicate to be as hard as the restricted universality problem. By applying these conditions, we develop a uniform method for showing undecidability and complexity results simultaneously via highly efficient many-one reductions. In addition, the properties of this restricted universality problem can be used to investigate the descriptional complexity of multi-patterns. We show that the trade-off between multi-patterns and regular expressions is not exponential-size bounded. Non-recursive trade-offs between multi-patterns (or multi-patterns with regular substitutions) and numerous classes of language descriptors are also established. [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]

Abstract: We study the relation of autoreducibility and mitoticity for polylog-space many-one reductions and log-space many-one reductions. For polylog-space these notions coincide, while proving the same for log-space is out of reach. More precisely, we show the following results with respect to nontrivial sets and many-one reductions: [1.] polylog-space autoreducible ⇔ polylog-space mitotic, [2.] log-space mitotic ⇒ log-space autoreducible ⇒ -space mitotic, [3.] relative to an oracle, log-space autoreducible ⇏ log-space mitotic. The oracle is an infinite family of graphs whose construction combines arguments from Ramsey theory and Kolmogorov complexity. [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]

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]

Abstract: Total search problems (TFNP problems) typically have their totality guaranteed by some combinatorial property. This paper proves that, if there is a polynomial time Turing reduction between two TFNP problems, then there are quasipolynomial size, polylogarithmic height, constant depth, free-cut free propositional (Frege) proofs of the combinatorial property associated with the first TFNP problem from the property associated with the second problem. In addition, they have Nullstellensatz derivations of polylogarithmic degree. These results extend the previous work of Buresh-Oppenheim and Morioka first by applying to Turing reductions in place of many-one reductions and second by giving tight bounds on the height of the Frege proofs. As a corollary, PLS-complete problems are not polynomial time Turing reducible to PPA problems relative to a generic oracle. We establish a converse construction as well, by showing that a polynomial time Turing reduction can be obtained from a family of quasipolynomial size, polylogarithmic depth, propositional proofs which are based on “decision tree” substitutions. This establishes the optimality of our constructions, and partially resolves an open question posed by Buresh-Oppenheim and Morioka. We observe that the classes PPA, PPAD, PPADS, and PLS are closed under Turing reductions, and give an example of a TFNP class that is not closed under Turing reductions. [Copyright &y& Elsevier]

Abstract: We introduce a new measure notion on small complexity classes (called -measure), based on martingale families, that gets rid of some drawbacks of previous measure notions: it can be used to define dimension because martingale families can make money on all strings, and it yields random sequences with an equal frequency of ’s and ’s. On larger complexity classes ( and above), -measure is equivalent to Lutz resource-bounded measure. As applications to -measure, we answer a question raised in [E. Allender, M. Strauss, Measure on small complexity classes, with application for BPP, in: Proc. of the 35th Ann. IEEE Symp. on Found. of Comp. Sci., 1994, pp. 807–818] by improving their result to: for almost every language decidable in subexponential time, . We show that almost all languages in  do not have small non-uniform complexity. We compare -measure to previous notions and prove that martingale families are strictly stronger than -measure [E. Allender, M. Strauss, Measure on small complexity classes, with application for BPP, in: Proc. of the 35th Ann. IEEE Symp. on Found. of Comp. Sci., 1994, pp. 807–818], we also discuss the limitations of martingale families concerning finite unions. We observe that all classes closed under polynomial many-one reductions have measure zero in  iff they have measure zero in . We use martingale families to introduce a natural generalization of Lutz resource-bounded dimension [J.H. Lutz, Dimension in complexity classes, in: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000, pp. 158–169] on , which meets the intuition behind Lutz’s notion. We show that -dimension lies between finite-state dimension and dimension on . We prove an analogue of a Theorem of Eggleston in , i.e. the class of languages whose characteristic sequence contains ’s with frequency , has dimension the Shannon entropy of in . [Copyright &y& Elsevier]

We consider vertex colorings of graphs in which adjacent vertices have distinct colors. A graph is s-chromatic if it is colorable in s colors and any coloring of it uses at least s colors. The forcing chromatic number Fχ(G) of an s-chromatic graph G is the smallest number of vertices which must be colored so that, with the restriction that s colors are used, every remaining vertex has its color determined uniquely. We estimate the computational complexity of Fχ(G) relating it to the complexity class US introduced by Blass and Gurevich [Inform. Control, 55 (1982), pp. 80-88]. We prove that recognizing whether Fχ(G) ≤ 2 is US-hard with respect to polynomial-time many-one reductions. Moreover, this problem is coNP-hard even under the promises that Fχ(G) ≤ 3 and G is 3-chromatic. On the other hand, recognizing whether Fχ(G) ≤ k, for each constant k, is reducible to a problem in US via a disjunctive truth-table reduction. Similar results are obtained also for forcing variants of the clique and the domination numbers of a graph. [ABSTRACT FROM AUTHOR]

We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and nonuniform reductions. These sets are provably not complete under the usual many-one reductions. Let RC, RKt, RKS, RKT be the sets of strings x having complexity at least ∣x∣/2, according to the usual Kolmogorov complexity measure C, Levin's time-bounded Kolmogorov complexity Kt [L. Levin, Inform. and Control, 61 (1984), pp. 15–37], a space-bounded Kolmogorov measure KS, and a new time-bounded Kolmogorov complexity measure KT, respectively. Our main results are as follows: 1. RKS and RKt are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. Similar results hold for other classes with PSPACE-robust Turing complete sets. 2. EXP = NPRKt. 3. PSPACE = ZPPRKS ⊆ PRC. 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPPRKT. Our hardness result for PSPACE gives rise to fairly natural problems that are complete for PSPACE under ≤Tp reductions, but not under ≤mlog reductions. Our techniques also allow us to show that all computably enumerable sets are reducible to RC via P/poly-truth-table reductions. This provides the first ‘efficient’ reduction of the halting problem to RC. [ABSTRACT FROM AUTHOR]

The article offers information on small span theorem in scaled dimension. According to the theorem, for a language A decidable in exponential time, either the class of languages reducible to A or the class of problems to which A can be reduced is small in the sense of resource-bounded measure. The resource-bounded scaled dimension provides rescalings of resource-bounded dimension. It is stated that the small span theorems hold for polynomial-time many-one reductions in the -3rd-order scaled dimension but fails to hold in the -2nd-order scaled dimension.

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]

We prove that the graph isomorphism problem restricted to trees and to colored graphs with color multiplicities 2 and 3 is many-one complete for several complexity classes within NC2. In particular we show that tree isomorphism, when trees are encoded as strings, is NC1-hard under AC0-reductions. NC1-completeness thus follows from Buss''s NC1 upper bound. By contrast, we prove that testing isomorphism of two trees encoded as pointer lists is L-complete. Concerning colored graphs we show that the isomorphism problem for graphs with color multiplicities 2 and 3 is complete for symmetric logarithmic space SL under many-one reductions. This result improves the existing upper bounds for the problem. We also show that the graph automorphism problem for colored graphs with color classes of size 2 is equivalent to deciding whether a graph has more than a single connected component and we prove that for color classes of size 3 the graph automorphism problem is contained in SL. [Copyright &y& Elsevier]

We show that approximating the shortest vector problem (in any ℓ[SUBp] norm) to within any constant factor less than p√2 is hard for NP under reverse unfaithful random reductions with inverse polynomial error probability. In particular, approximating the shortest vector problem is not in RP (random polynomial time), unless NP equals RP. We also prove a proper NP-hardness result (i.e., hardness under deterministic many-one reductions) under a reasonable number theoretic conjecture on the distribution of square-free smooth numbers. As part of our proof, we give an alternative construction of Ajtai's constructive variant of Sauer's lemma that greatly simplifies Ajtai's original proof. [ABSTRACT FROM AUTHOR]

The paper analyzes in terms of polynomial time many-one reductions the computational complexity of several natural equivalence relations on Boolean functions which derive from replacing variables by expressions, one of them is the Boolean isomorphism relation. Most of these computational problems turn out to be between co-NP and σ[sup p, sub 2]. [ABSTRACT FROM AUTHOR]

We show that there is a set that is almost complete but not complete under polynomial-time many-one (p-m) reductions for the class E of sets computable in deterministic time 2lin. Here a set in a complexity class C is almost complete for C under some given reducibility if the class of the problems in C that do not reduce to this set has measure 0 in C in the sense of Lutz''s resource-bounded measure theory. We also show that the almost complete sets for E under polynomial time-bounded length-increasing one–one reductions and truth-table reductions of norm 1 coincide with the almost p-m-complete sets for E. Moreover, we obtain similar results for the class EXP of sets computable in deterministic time 2poly. [Copyright &y& Elsevier]