Search

A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, "catalytic" tape, which, while being available as a work tape, has the caveat of being initialized with an arbitrary string, which must be preserved at the end of the computation. Despite this restriction, catalytic machines have been shown to have surprising additional power; a logspace machine with a polynomial length catalytic tape, known as catalytic logspace ($CL$), can compute problems which are believed to be impossible for $L$. A fundamental question of the model is whether the catalytic condition, of leaving the catalytic tape in its exact original configuration, is robust to minor deviations. This study was initialized by Gupta et al. (2024), who defined lossy catalytic logspace ($LCL[e]$) as a variant of $CL$ where we allow up to $e$ errors when resetting the catalytic tape. They showed that $LCL[e] = CL$ for any $e = O(1)$, which remains the frontier of our understanding. In this work we completely characterize lossy catalytic space ($LCSPACE[s,c,e]$) in terms of ordinary catalytic space ($CSPACE[s,c]$). We show that $$LCSPACE[s,c,e] = CSPACE[\Theta(s + e \log c), \Theta(c)]$$ In other words, allowing $e$ errors on a catalytic tape of length $c$ is equivalent, up to a constant stretch, to an equivalent errorless catalytic machine with an additional $e \log c$ bits of ordinary working memory. As a consequence, we show that for any $e$, $LCL[e] = CL$ implies $SPACE[e \log n] \subseteq ZPP$, thus giving a barrier to any improvement beyond $LCL[O(1)] = CL$. We also show equivalent results for non-deterministic and randomized catalytic space., Comment: 21 pages

We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related modulator-based parameters. The main findings are as follows: i) Binary CSP parameterized by the vertex cover number is $\mathrm{W}[3]$-complete. More generally, for every positive integer $d$, Binary CSP parameterized by the size of a modulator to a treedepth-d graph is $\mathrm{W}[2d+1]$-complete. This provides a new family of natural problems that are complete for odd levels of the W-hierarchy. ii) We introduce a new complexity class XSLP, defined so that Binary CSP parameterized by treedepth is complete for this class. We provide two equivalent characterizations of XSLP: the first one relates XSLP to a model of an alternating Turing machine with certain restrictions on conondeterminism and space complexity, while the second one links XSLP to the problem of model-checking first-order logic with suitably restricted universal quantification. Interestingly, the proof of the machine characterization of XSLP uses the concept of universal trees, which are prominently featured in the recent work on parity games iii) We describe a new complexity hierarchy sandwiched between the W-hierarchy and the A-hierarchy: For every odd $t$, we introduce a parameterized complexity class $\mathrm{S}[t]$ with $\mathrm{W}[t]\subseteq \mathrm{S}[t]\subseteq \mathrm{A}[t]$, defined using a parameter that interpolates between the vertex cover number and the treedepth. We expect that many of the studied classes will be useful in the future for pinpointing the complexity of various structural parameterizations of graph problems.

A line of work initiated by Fortnow in 1997 has proven model-independent time-space lower bounds for the $\mathsf{SAT}$ problem and related problems within the polynomial-time hierarchy. For example, for the $\mathsf{SAT}$ problem, the state-of-the-art is that the problem cannot be solved by random-access machines in $n^c$ time and $n^{o(1)}$ space simultaneously for $c < 2\cos(\frac{\pi}{7}) \approx 1.801$. We extend this lower bound approach to the quantum and randomized domains. Combining Grover's algorithm with components from $\mathsf{SAT}$ time-space lower bounds, we show that there are problems verifiable in $O(n)$ time with quantum Merlin-Arthur protocols that cannot be solved in $n^c$ time and $n^{o(1)}$ space simultaneously for $c < \frac{3+\sqrt{3}}{2} \approx 2.366$, a super-quadratic time lower bound. This result and the prior work on $\mathsf{SAT}$ can both be viewed as consequences of a more general formula for time lower bounds against small-space algorithms, whose asymptotics we study in full. We also show lower bounds against randomized algorithms: there are problems verifiable in $O(n)$ time with (classical) Merlin-Arthur protocols that cannot be solved in $n^c$ randomized time and $n^{o(1)}$ space simultaneously for $c < 1.465$, improving a result of Diehl. For quantum Merlin-Arthur protocols, the lower bound in this setting can be improved to $c < 1.5$., Comment: 38 pages, 5 figures. To appear in ITCS 2021

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

We present the concept of the \emph{information efficiency of functions} as a technique to understand the interaction between information and computation. Based on these results we identify a new class of objects that we call \emph{Semi-Countable Sets}. As the name suggests these sets form a separate class of objects between countable and uncountable sets. In principle these objects are countable, but the information in the descriptions of the elements of the class grows faster than the information in the natural numbers that index them. Any characterization of the class in terms of natural numbers is fundamentally incomplete. Semi-countable sets define one-to-one injections into the set of natural numbers that can be computed in exponential time, but not in polynomial time. A characteristic semi-countable object is $\phi_{\Sigma}$ the set of all additions for all finite sets of natural numbers. The class $\phi_{\Sigma}$ codes the Subset Sum problem. This gives a natural and transparant analysis of the separation between the classes $P$ and $NP$., Comment: 44 pages, 16 figures

In parameterized algorithmics, the process of kernelization is defined as a polynomial time algorithm that transforms the instance of a given problem to an equivalent instance of a size that is limited by a function of the parameter. As, afterwards, this smaller instance can then be solved to find an answer to the original question, kernelization is often presented as a form of preprocessing. A natural generalization of kernelization is the process that allows for a number of smaller instances to be produced to provide an answer to the original problem, possibly also using negation. This generalization is called Turing kernelization. Immediately, questions of equivalence occur or, when is one form possible and not the other. These have been long standing open problems in parameterized complexity. In the present paper, we answer many of these. In particular, we show that Turing kernelizations differ not only from regular kernelization, but also from intermediate forms as truth-table kernelizations. We achieve absolute results by diagonalizations and also results on natural problems depending on widely accepted complexity theoretic assumptions. In particular, we improve on known lower bounds for the kernel size of compositional problems using these assumptions.

We show the first unconditional pseudo-determinism result for all of search-BPP. Specifically, we show that every BPP search problem can be computed pseudo-deterministically on average for infinitely many input lengths. In other words, for infinitely many input lengths and for any polynomial-time samplable distribution our algorithm succeeds in producing a unique answer (if one exists) with high probability over the distribution and the coins tossed.

We introduce pseudo-deterministic interactive proofs (psdAM): interactive proof systems for search problems where the verifier is guaranteed with high probability to output the same output on different executions. As in the case with classical interactive proofs, the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover. We view pseudo-deterministic interactive proofs as an extension of the study of pseudo-deterministic randomized polynomial time algorithms: the goal of the latter is to find canonical solutions to search problems whereas the goal of the former is to prove that a solution to a search problem is canonical to a probabilistic polynomial time verifier. Alternatively, one may think of the powerful prover as aiding the probabilistic polynomial time verifier to find canonical solutions to search problems, with high probability over the randomness of the verifier. The challenge is that pseudo-determinism should hold not only with respect to the randomness, but also with respect to the prover: a malicious prover should not be able to cause the verifier to output a solution other than the unique canonical one.

In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2) whose recursive definition is similar to the Fibonacci numbers. Further understanding this polynomial seems to be a promising route to new formula lower bounds. Our methods are rooted in the study of ABPs of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_e-bar. As a natural continuation of this work we prove that the class VNP can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs.

We show that the two main reduction notions in arithmetic circuit complexity, p-projections and c-reductions, differ in power. We do so by showing unconditionally that there are polynomials that are VNP-complete under c-reductions but not under p-projections. We also show that the question of which polynomials are VNP-complete under which type of reductions depends on the underlying field.

Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and artificial intelligence. Forbidding patterns (generic sub-instances) provides a means of defining CSP fragments which are neither exclusively language-based nor exclusively structure-based. It is known that the class of binary CSP instances in which the broken-triangle pattern (BTP) does not occur, a class which includes all tree-structured instances, are decided by arc consistency (AC), a ubiquitous reduction operation in constraint solvers. We provide a characterisation of simple partially-ordered forbidden patterns which have this AC-solvability property. It turns out that BTP is just one of five such AC-solvable patterns. The four other patterns allow us to exhibit new tractable classes.

Large complexity classes, like the exponential time hierarchy, received little attention in terms of finding complete problems. In this work a generalization of propositional logic is investigated which fills this gap with the introduction of Boolean higher-order quantifiers or equivalently Boolean Skolem functions. This builds on the important results of Wrathall and Stockmeyer regarding complete problems, namely QBF and QBF-k, for the polynomial hierarchy. Furthermore it generalizes the Dependency QBF problem introduced by Peterson, Reif and Azhar which is complete for NEXP, the first level of the exponential hierarchy. Also it turns out that the hardness results do not collapse at the consideration of conjunctive and disjunctive normal forms, in contrast to plain QBF.

In this work, we critique two papers, "A Polynomial-Time Solution to the Clique Problem" by Tamta, Pande, and Dhami, and "A Polynomial-Time Algorithm For Solving Clique Problems" by LaPlante. We summarize and analyze both papers, noting that the algorithms presented in both papers are flawed. We conclude that neither author has successfully established that P = NP., Comment: 14 pages, 11 figures arXiv:1403.1178v1 [cs.DS] arXiv:1503.04794v1 [cs.DS]

We give the first super-polynomial separation in the power of bounded-depth boolean formulas vs. circuits. Specifically, we consider the problem Distance $k(n)$ Connectivity, which asks whether two specified nodes in a graph of size $n$ are connected by a path of length at most $k(n)$. This problem is solvable (by the recursive doubling technique) on {\bf circuits} of depth $O(\log k)$ and size $O(kn^3)$. In contrast, we show that solving this problem on {\bf formulas} of depth $\log n/(\log\log n)^{O(1)}$ requires size $n^{\Omega(\log k)}$ for all $k(n) \leq \log\log n$. As corollaries: (i) It follows that polynomial-size circuits for Distance $k(n)$ Connectivity require depth $\Omega(\log k)$ for all $k(n) \leq \log\log n$. This matches the upper bound from recursive doubling and improves a previous $\Omega(\log\log k)$ lower bound of Beame, Pitassi and Impagliazzo [BIP98]. (ii) We get a tight lower bound of $s^{\Omega(d)}$ on the size required to simulate size-$s$ depth-$d$ circuits by depth-$d$ formulas for all $s(n) = n^{O(1)}$ and $d(n) \leq \log\log\log n$. No lower bound better than $s^{\Omega(1)}$ was previously known for any $d(n) \nleq O(1)$. Our proof technique is centered on a new notion of pathset complexity, which roughly speaking measures the minimum cost of constructing a set of (partial) paths in a universe of size $n$ via the operations of union and relational join, subject to certain density constraints. Half of our proof shows that bounded-depth formulas solving Distance $k(n)$ Connectivity imply upper bounds on pathset complexity. The other half is a combinatorial lower bound on pathset complexity.

The polynomial hierarchy is a grading of problems by difficulty, including P, NP and coNP as the best known classes. The promise polynomial hierarchy is similar, but extended to include promise problems. It turns out that the promise polynomial hierarchy is considerably simpler to work with, and many open questions about the polynomial hierarchy can be resolved in the promise polynomial hierarchy. Our main theorem is that, in the world of promise problems, if phi has a weak (Turing, Cook) reduction to SAT then phi has a strong (Karp, many-one) reduction to UVAL2, where UVAL2(f) is the promise problem of finding the unique x such that f(x,y)=1 for all y. We also give a complete promise problem for the promise problem equivalent of UP intersect coUP., Comment: 12 pages

The Inverse 3-SAT problem is known to be coNP Complete. This article shows a new interesting way to solve directly the problem by using closure under resolution and partial assignment properties. An algorithm is proposed which lets solve the (co)Inverse 3-SAT problem., Comment: 8 pages

The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: 1. For any eps > 0, we show the existence of an n vertex graph G where every set of o(n) vertices has expansion 1 - eps, but G's adjacency matrix has more than exp(log^delta n) eigenvalues larger than 1 - eps, where delta depends only on eps. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. 2. A gadget that reduces unique games instances with linear constraints modulo K into instances with alphabet k with a blowup of K^polylog(K), improving over the previously known gadget with blowup of 2^K. 3. An n variable integrality gap for Unique Games that that survives exp(poly(log log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and small set expansion in certain related Cayley graphs, and use this connection to derandomize the noise graph on the Boolean hypercube., Comment: 45 pages

In this paper we discusses the relationship between the known classes P and NP. We show that the difficulties in solving problem "P versus NP" have methodological in nature. An algorithm for solving any problem is sensitive to even small changes in its formulation. As we will shown in the paper, these difficulties are exactly in the formulation of some problems of the class NP., Comment: 9 pages

Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. The longest arc-preserving common subsequence problem has been introduced as a framework for studying the similarity of arc-annotated sequences. In this paper, we consider arc-annotated sequences with various arc structures. We consider the longest arc preserving common subsequence problem. In particular, we show that the decision version of the 1-{\sc fragment LAPCS(crossing,chain)} and the decision version of the 0-{\sc diagonal LAPCS(crossing,chain)} are {\bf NP}-complete for some fixed alphabet $\Sigma$ such that $|\Sigma| = 2$. Also we show that if $|\Sigma| = 1$, then the decision version of the 1-{\sc fragment LAPCS(unlimited, plain)} and the decision version of the 0-{\sc diagonal LAPCS(unlimited, plain)} are {\bf NP}-complete.

We study the quadratic residue problem known as an NP complete problem by way of the prime number and show that a nondeterministic polynomial process does not belong to the class P because of a random distribution of solutions for the quadratic residue problem., Comment: 5 pages

The periods, introduced by Kontsevich and Zagier, form a class of complex numbers which contains all algebraic numbers and several transcendental quantities. Little has been known about qualitative properties of periods. In this paper, we compare the periods with hierarchy of real numbers induced from computational complexities. In particular we prove that periods can be effectively approximated by elementary rational Cauchy sequences. As an application, we exhibit a computable real number which is not a period., Comment: 19 pages

This paper is concerned with the complexity and stability of arithmetic operations in the jacobian variety of curves over the field of complex numbers, as the genus grows to infinity. We focus on modular curves. Efficient and stable computation in the jacobian of modular curves is useful for computing coefficients of modular forms in deterministic polynomial time. This work is part of my contribution to Edixhoven's program for solving this problem., Comment: to appear in Groupe de Galois arithm\'etiques et diff\'erentiels (Luminy, 2004) D. Bertrand, P. D\`ebes (Ed.) S\'eminaires et Congr\`es (2006), Soci\'et\'e Math\'ematique de France

Extending results of Schindler [math.LO/0106087] and Hamkins and Welch [math.LO/0212046], we establish in the context of infinite time Turing machines that P is properly contained in NP intersect coNP. Furthermore, NP intersect coNP is exactly the class of hyperarithmetic sets. For the more general classes, we establish that P+ = (NP+ intersect coNP+) = (NP intersect coNP), though P++ is properly contained in NP++ intersect coNP++. Within any contiguous block of infinite clockable ordinals, we show that P_alpha is not equal to NP_alpha intersect coNP_alpha, but if beta begins a gap in the clockable ordinals, then P_beta = NP_beta intersect coNP_beta. Finally, we establish that P^f is not equal to NP^f intersect coNP^f for most functions f from the reals to the ordinals, although we provide examples where P^f = NP^f intersect coNP^f and P^f is not equal to NP^f., Comment: 26 pages

Schindler recently addressed two versions of the question P $\stackrel{?}{=}$ NP for Turing machines running in transfinite ordinal time. These versions differ in their definition of input length. The corresponding complexity classes are labelled P, NP and ${\rm P}^+,{\rm NP}^+$. Schindler showed that P $\neq$ NP and ${\rm P}^+ \neq {\rm NP}^+$. We show that P $=$ NP $\cap$ co-NP and NP $\neq$ co-NP, whereas ${\rm P}^+ \subset$ NP $\cap$ co-NP and ${\rm NP}^+ \neq $ co-NP$^+$., Comment: 9 pages

We discuss the question of Ralf-Dieter Schindler whether for infinite time Turing machines P^f = NP^f can be true for any function f from the reals into omega_1. We show that ``almost everywhere'' the answer is negative., Comment: 11 pages

We state a version of the P=?NP problem for infinite time Turing machines. It is observed that P not= NP for this version., Comment: 2 pages

We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted, capable of being continuously deformed without self-intersection so that it lies in a plane. We show that this problem, {\sc unknotting problem} is in {\bf NP}. We also consider the problem, {\sc unknotting problem} of determining whether two or more such polygons can be split, or continuously deformed without self-intersection so that they occupy both sides of a plane without intersecting it. We show that it also is in NP. Finally, we show that the problem of determining the genus of a polygonal knot (a generalization of the problem of determining whether it is unknotted) is in {\bf PSPACE}. We also give exponential worst-case running time bounds for deterministic algorithms to solve each of these problems. These algorithms are based on the use of normal surfaces and decision procedures due to W. Haken, with recent extensions by W. Jaco and J. L. Tollefson., Comment: 32 pages, 1 figure