Search

In a regular PCP the verifier queries each proof symbol in the same number of tests. This number is called the degree of the proof, and it is at least 1/(sq) where s is the soundness error and q is the number of queries. It is incredibly useful to have regularity and reduced degree in PCP. There is an expander-based transformation by Papadimitriou and Yannakakis that transforms any PCP with a constant number of queries and constant soundness error to a regular PCP with constant degree. There are also transformations for low error projection and unique PCPs. Other PCPs are constructed especially to be regular. In this work we show how to regularize and reduce degree of PCPs with a possibly large number of queries and low soundness error. As an application, we prove NP-hardness of an unweighted variant of the collective minimum monotone satisfying assignment problem, which was introduced by Hirahara (FOCS'22) to prove NP-hardness of MCSP^* (the partial function variant of the Minimum Circuit Size Problem) under randomized reductions. We present a simplified proof and sufficient conditions under which MCSP^* is NP-hard under the standard notion of reduction: MCSP^* is NP-hard under deterministic polynomial-time many-one reductions if there exists a function in E that satisfies certain direct sum properties.

We settle the question of where exactly 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 a question by Stanley from 2000 and a question 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., Comment: 15 pages

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 non-computational 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, well-maintained Coq library of undecidability proofs. Notably, a variant of Hooper's argument for the undecidability of Turing machine immortality is part of the mechanization.

We prove that deciding the vanishing of the character of the symmetric group is $C_=P$-complete. We use this hardness result to prove that the the square of the character is not contained in $\#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 $PP$-complete under many-one reductions, and hence $PH$-hard under Turing-reductions., Comment: 15 pages, 1 figure

The closure of deterministic context-free languages under logarithmic-space many-one reductions ($\mathrm{L}$-m-reductions), known as LOGDCFL, has been studied in depth from an aspect of parallel computability because it is nicely situated between $\mathrm{L}$ and $\mathrm{AC}^{1}\cap\mathrm{SC}^2$. By replacing a memory device from pushdown stacks with access-controlled storage tapes, we introduce a computational model of one-way deterministic depth-$k$ storage automata ($k$-sda's) whose tape cells are freely modified during the first $k$ accesses and then become blank forever. These $k$-sda's naturally induce the language family $k\mathrm{SDA}$. Similarly to $\mathrm{LOGDCFL}$, we study the closure $\mathrm{LOG}k\mathrm{SDA}$ of all languages in $k\mathrm{SDA}$ under $\mathrm{L}$-m-reductions. We demonstrate that $\mathrm{DCFL}\subseteq k\mathrm{SDA}\subseteq \mathrm{SC}^k$ by significantly extending Cook's early result (1979) of $\mathrm{DCFL}\subseteq \mathrm{SC}^2$. The entire hierarch of $\mathrm{LOG}k\mathrm{SDA}$ for all $k\geq1$ therefore lies between $\mathrm{LOGDCFL}$ and $\mathrm{SC}$. As an immediate consequence, we obtain the same simulation bounds for Hibbard's limited automata. We further characterize $\mathrm{LOG}k\mathrm{SDA}$ in terms of a new machine model, called logarithmic-space deterministic auxiliary depth-$k$ storage automata that run in polynomial time. These machines are as powerful as a polynomial-time two-way multi-head deterministic depth-$k$ storage automata. We also provide a ``generic'' $\mathrm{LOG}k\mathrm{SDA}$-complete language under $\mathrm{L}$-m-reductions by constructing a two-way universal simulator working for all $k$-sda's., Comment: (A4, 10pt, p28) This exposition corrects and expands its preliminary report, which appeared in the Proceedings of the 27th International Conference on Computing and Combinatorics (COCOON 2021), Tainan, Taiwan, October 24--26, 2021, Lecture Notes in Computer Science, Springer, vol. 13025, pp. 164--175, 2021. An oral presentation was given online due to the coronavirus pandemic

This work concerns the propositional proof complexity and computational complexity of Frankl's theorem on the trace of sets, the Kneser-Lovász theorem, and the Tucker lemma.We show that propositional translations of Frankl's theorem on the trace of sets has quasi-polynomial size Frege proofs. For constant values of the parameter t, we prove that Frankl's theorem has polynomial size AC0-Frege proofs from instances of the pigeonhole principle.We prove that propositional translations of the Kneser-Lovász theorem have polynomial size extended Frege proofs and quasi-polynomial size Frege proofs for all fixed values of k. We present a new counting-based combinatorial proof of the Kneser-Lovász theorem that avoids the topological arguments of prior proofs for all but finitely many base cases. We introduce new ``truncated Tucker lemma'' principles, which are miniaturizations of the octahedral Tucker lemma. The truncated Tucker lemma implies the Kneser-Lovász theorem. We show that the k=1 case of the truncated Tucker lemma has polynomial size extended Frege proofs.We show that the 2-D TUCKER search problem is 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.Frankl's theorem, the Kneser-Lovász theorem, and the truncated Tucker lemma are all shown to give total NP search problems. These problems are all shown to be PPP-hard under many-one reductions.

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) and Zermelo-Fraenkel set theory (ZF), 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 ZF are prepared 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 ZF formulated using only membership and no equality symbol, we obtain the undecidability of first-order logic with a single binary relation.

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., Peer Reviewed, Postprint (author's final draft)

Complexity theory can be viewed as the study of the relationship between computation and applications, understood the former as complexity classes and the latter as problems. Completeness results are clearly central to that view. Many natural algorithms resulting from current applications have polylogarithmic time (PolylogTime) or space complexity (PolylogSpace). The classical Karp notion of complete problem however does not plays well with these complexity classes. It is well known that PolylogSpace does not have complete problems under logarithmic space many-one reductions. In this paper we show similar results for deterministic and non-deterministic PolylogTime as well as for every other level of the polylogarithmic time hierarchy. We achieve that by following a different strategy based on proving the existence of proper hierarchies of problems inside each class. We then develop an alternative notion of completeness inspired by the concept of uniformity from circuit complexity and prove the existence of a (uniformly) complete problem for PolylogSpace under this new notion. As a consequence of this result we get that complete problems can still play an important role in the study of the interrelationship between polylogarithmic and other classical complexity classes., Comment: Submitted to Annals of Mathematics and Artificial Intelligence. arXiv admin note: text overlap with arXiv:1911.13104

In the framework of computational complexity and in an effort to define a more natural reduction for problems of equivalence, we investigate the recently introduced kernel reduction, a reduction that operates on each element of a pair independently. This paper details the limitations and uses of kernel reductions. We show that kernel reductions are weaker than many-one reductions and provide conditions under which complete problems exist. Ultimately, the number and size of equivalence classes can dictate the existence of a kernel reduction. We leave unsolved the unconditional existence of a complete problem under polynomial-time kernel reductions for the standard complexity classes.

We study the Minimum Circuit Size Problem (MCSP): given the truth-table of a Boolean function f and a number k, does there exist a Boolean circuit of size at most k computing f? This is a fundamental NP problem that is not known to be NP-complete. Previous work has studied consequences of the NP-completeness of MCSP. We extend this work and consider whether MCSP may be complete for NP under more powerful reductions. We also show that NP-completeness of MCSP allows for amplification of circuit complexity. We show the following results. - If MCSP is NP-complete via many-one reductions, the following circuit complexity amplification result holds: If NP cap co-NP requires 2^n^{Omega(1)-size circuits, then E^NP requires 2^Omega(n)-size circuits. - If MCSP is NP-complete under truth-table reductions, then EXP neq NP cap SIZE(2^n^epsilon) for some epsilon> 0 and EXP neq ZPP. This result extends to polylog Turing reductions.

We propose an extension of the framework for discussing the computational complexity of problems involving uncountably many objects, such as real numbers, sets and functions, that can be represented only through approximation. The key idea is to use (a certain class of) string functions as names representing these objects. These are more expressive than infinite sequences, which served as names in prior work that formulated complexity in more restricted settings. An advantage of using string functions is that we can define their "size" in the way inspired by higher-type complexity theory. This enables us to talk about computation on string functions whose time or space is bounded polynomially in the input size, giving rise to more general analogues of the classes P, NP, and PSPACE. We also define NP- and PSPACE-completeness under suitable many-one reductions. Because our framework separates machine computation and semantics, it can be applied to problems on sets of interest in analysis once we specify a suitable representation (encoding). As prototype applications, we consider the complexity of functions (operators) on real numbers, real sets, and real functions. For example, the task of numerical algorithms for solving a certain class of differential equations is naturally viewed as an operator taking real functions to real functions. As there was no complexity theory for operators, previous results only stated how complex the solution can be. We now reformulate them and show that the operator itself is polynomial-space complete., Comment: 22 pages, 9 figures; a few typos fixed after journal publication

To expand a fundamental theory of context-free languages, we equip nondeterministic one-way pushdown automata with additional oracle mechanisms, which naturally induce various nondeterministic reducibilities among formal languages. As a natural restriction of NP-reducibility, we introduce a notion of many-one CFL reducibility and conduct a ground work to formulate a coherent framework for further expositions. Two more powerful reducibilities--bounded truth-table and Turing CFL-reducibilities--are also discussed in comparison. The Turing CFL-reducibility, in particular, helps us introduce an exquisite hierarchy, called the CFL hierarchy, built over the family CFL of context-free languages. For each level of this hierarchy, its basic structural properties are proven and three alternative characterizations are presented. The second level is not included in NC(2) unless NP= NC(2). The first and second levels of the hierarchy are different. The rest of the hierarchy (more strongly, the Boolean hierarchy built over each level of the hierarchy) is also infinite unless the polynomial hierarchy over NP collapses. This follows from a characterization of the Boolean hierarchy over the k-th level of the polynomial hierarchy in terms of the Boolean hierarchy over the k+1st level of the CFL hierarchy using log-space many-one reductions. Similarly, the complexity class Theta(k) is related to the closure of the k-th level of the CFL hierarchy under log-space truth-table reductions. We also argue that the CFL hierarchy coincides with a hierarchy over CFL built by application of many-one CFL-reductions. We show that BPCFL--a bounded-error probabilistic version of CFL--is not included in CFL even in the presence of advice. Employing a known circuit lower bound and a switching lemma, we exhibit a relativized world where BPCFL is not located within the second level of the CFL hierarchy., Comment: This is a complete version of an extended abstract that appeared under a slightly different title in the Proceedings of the 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2014), High Tatras, Slovakia, January 25-30, 2014, Lecture Notes in Computer Science, Springer-Verlag, vol.8327, pp.514-525, 2014

A central theme in distributed network algorithms concerns understanding and coping with the issue of locality. Inspired by sequential complexity theory, we focus on a complexity theory for distributed decision problems. In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. This paper introduces several classes of distributed decision problems, proves separation among them and presents some complete problems. More specifically, we consider the standard LOCAL model of computation and define LD (for local decision) as the class of decision problems that can be solved in constant number of communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class BPLD, and ask whether LD=BPLD. We provide a partial answer to this question by showing that in many cases, randomization does not help for deciding hereditary languages. In addition, we define the notion of local many-one reductions, and introduce the (nondeterministic) class NLD of decision problems for which there exists a certificate that can be verified in constant number of communication rounds. We prove that there exists an NLD-complete problem. We also show that there exist problems not in NLD. On the other hand, we prove that the class NLD#n, which is NLD assuming that each processor can access an oracle that provides the number of nodes in the network, contains all (decidable) languages. For this class we provide a natural complete problem as well.

A dichotomy theorem for counting problems due to Creignou and Hermann states that or any nite set S of logical relations, the counting problem #SAT(S) is either in FP, or #P-complete. In the present paper we show a dichotomy theorem for polynomial evaluation. That is, we show that for a given set S, either there exists a VNP-complete family of polynomials associated to S, or the associated families of polynomials are all in VP. We give a concise characterization of the sets S that give rise to "easy" and "hard" polynomials. We also prove that several problems which were known to be #P-complete under Turing reductions only are in fact #P-complete under many-one reductions.

In 1978, Hartmanis conjectured that there exist no sparse complete sets for P under logspace many-one reductions. In this paper, in support of the conjecture, it is shown that if P has sparse hard sets under logspace many-one reductions, then P \subseteq DSPACE[log^2 n]. The result is derived from a more general statement that if P has 2^{polylog} sparse hard sets under poly-logarithmic space-computable many-one reductions, then P \subseteq DSPACE[polylog].

In 1978, Hartmanis conjectured that there exist no sparse complete sets for P under logspace many-one reductions. In this paper, in support of the conjecture, it is shown that if P has sparse hard sets under logspace many-one reductions, then P \subseteq DSPACE[log^2 n]. The result is derived from a more general statement that if P has 2^{polylog} sparse hard sets under poly-logarithmic space-computable many-one reductions, then P \subseteq DSPACE[polylog].

We study the approximability of Max Ones when the number of variable occurrences is bounded by a constant. For conservative constraint languages (i.e., when the unary relations are included) we give a complete classification when the number of occurrences is three or more and a partial classification when the bound is two. For the non-conservative case we prove that it is either trivial or equivalent to the corresponding conservative problem under polynomial-time many-one reductions., Comment: Accepted to MFCS 2006

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. We prove that recognizing if $F(G)\le 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)\le 3$ and $G$ is 3-chromatic. On the other hand, recognizing if $F(G)\le k$, for each constant $k$, is reducible to a problem in US via disjunctive truth-table reduction. Similar results are obtained also for forcing variants of the clique and the domination numbers of a graph., Comment: 24 pages; This is the final version