Skip to main content
Share Your Experience: Take the 2024 Developer Survey
18 votes
Accepted

Is Hartmanis-Stearns conjecture settled by this article?

First, the name of the conjecture is "Hartmanis-Stearns", not "Hartmanis-Stearn". Second, the Hartmanis-Stearns conjecture concerns those real numbers computable by a multi-tape Turing machine in ...
Jeffrey Shallit's user avatar
17 votes
Accepted

Is optimally solving the n×n×n Rubik's Cube NP-hard?

One of my papers was just posted to arXiv and addresses this question: optimally solving the Rubik's Cube is NP-complete.
Mikhail Rudoy's user avatar
14 votes
Accepted

Finding subgraphs with high treewidth and constant degree

See the paper by Julia Chuzhoy and myself on Treewidth sparsifiers. We show that one can obtain a subgraph of degree at most 3 with treewidth $\Omega(k/polylog(k))$ where $k$ is the treewidth of $G$. ...
Chandra Chekuri's user avatar
12 votes
Accepted

Pathwidth of planarized drawing of $K_{3,n}$

A naive drawing of $K_{3,n}$ will have pathwidth $O(n)$. I think that's tight, and that the pathwidth is always $\Omega(n)$. Here's an argument why. (1) Fix a drawing of $K_{3,n}$. Without loss of ...
David Eppstein's user avatar
12 votes
Accepted

Does the first order theory of a finite structure have bounded quantifier rank?

The theory of any finite structure is model complete. In fact, it is easy to see that any formula is equivalent to an existential formula with one quantifier per each element of the structure, after ...
Emil Jeřábek's user avatar
12 votes
Accepted

Number of permutations that satisfy a given set of comparisons

As far as I can tell, your problem is equivalent to the following: given a partial order (represented by its comparability pairs, which forms a DAG), count how many linear extensions it has. This ...
a3nm's user avatar
  • 9,449
12 votes

Combinatorics of a badminton tournament

I finally found the keyword allowing to search for solutions, it's called a "Whist Tournament". Solutions can be found here for instance: https://www.devenezia.com/downloads/round-robin/...
Denis's user avatar
  • 8,893
10 votes
Accepted

The maximum number of induced cycles in a simple directed graph

I don't know what's already known but the obvious bounds are that it is at most $\binom{n}{n/2}$ (Sperner's theorem) and at least $3^{n/3}$ (for $n$ a multiple of three that is at least 9: form a ...
David Eppstein's user avatar
10 votes
Accepted

The asymptotic behavior of a recurrence related to stable matchings

Here is a proof. Parts of the proof involve some real analysis; I've sketched the details in an appendix, and if you know real analysis, you should be able to fill in the details fairly easily. First,...
Peter Shor 's user avatar
9 votes

What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

An exponential upper bound has been given in Anna R. Karlin, Shayan Oveis Gharan, Robbie Weber: A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings. Later the base of the ...
domotorp's user avatar
  • 14k
9 votes

Counting words accepted by a regular grammar

I think this is a hard counting problem, see this paper: Counting the size of regular sequences of given length is #P-complete: S. Kannan, Z. Sweedyk, and S. R. Mahaney. Counting and random generation ...
Miklós István's user avatar
9 votes
Accepted

VC dimension of polynomials over tropical semirings?

I've realized that the answer to my question is - yes: the VC dimension of degree $\leq d$ polynomials on $n$ variables over any tropical semiring is at most a constant times $n^2\log(n+d)$. This can ...
Stasys's user avatar
  • 6,765
8 votes

Can the "mutual independence" condition in the Lovász local lemma be weakened?

The Lopsided Lovasz Local Lemma relaxes the mutual independence condition to negative dependence. We assume we have events $A_1, \ldots, A_n$, with a lopsidependency graph $G$ defined on $[n]$ s.t. ...
Sasho Nikolov's user avatar
8 votes

Average-case analogue of Small-bias Spaces

Below I show how to explicity construct an average-case $\varepsilon$-biased space on $n$ bits of size $O(1/\varepsilon)$. In contrast, the best worst-case $\varepsilon$-biased spaces on $n$ bits ...
Thomas's user avatar
  • 2,803
8 votes
Accepted

Complexity of permanent verification

At the very least, the problem is "hard for the polynomial hierarchy" in the following sense. Let $PermVerify$ be the problem specified. Then $$PH \subseteq P^{\#P} \subseteq NP^{PermVerify}$...
Ryan Williams's user avatar
8 votes

Algorithm to check whether a given set is Sidon

Probably OP's problem has no sub-quadratic algorithm, as it is 3-SUM-hard, per [1]: Corollary 1.2 [1]. Under the 3-SUM hypothesis, for all $\delta > 0$, determining whether a given set of $n$ ...
Neal Young's user avatar
  • 10.8k
7 votes
Accepted

Implementation of Wilf-Zeilberger and related methods

It is implemented in Maxima (http://maxima.sourceforge.net/docs/manual/de/maxima_77.html#SEC400), to which Sage has interface. A few dozens of examples (ranging from very easy to very difficult) I ...
Vladimir Dotsenko's user avatar
7 votes

Pairwise comparison of bit vectors

This problem is sometimes called Subset Containment and it is computationally equivalent to: given $n$ sets $S_1,\ldots,S_n \subseteq [d]$, are there $i \neq j$ such that $S_i \cap S_j = \varnothing$? ...
Ryan Williams's user avatar
7 votes

Applications of Christol theorem

There are lots of applications to transcendence in finite characteristic. Christol's theorem makes it possible to give proofs of theorems about transcendence of formal power series using the tools of ...
Jeffrey Shallit's user avatar
7 votes
Accepted

Stable order on binary strings

No. Given any linear ordering of the $n$-bit strings, find a sequence of at most $n+1$ strings going from the first string in the ordering to the last string in the ordering by single-bit changes per ...
David Eppstein's user avatar
7 votes
Accepted

On the coloring number of small graphs with small cliques

Uniformly random $k^2$-vertex graphs have clique size $O(\log k)$, well under $k$, and independent set size also $O(\log k)$, implying that their chromatic number is $\Omega(k^2/\log k)$. As for $k^2$...
David Eppstein's user avatar
7 votes
Accepted

Does Horn SAT (Horn formula in CNF) have an integral polytope?

EDIT: Strengthened Theorem 2. The answer to the problem as posed is no, unless P=NP: Theorem 1. Unless P=NP, there is no LP polytope for Horn-SAT that has only integer extreme points and is ...
Neal Young's user avatar
  • 10.8k
7 votes
Accepted

How can we compute the VC dimension of a finite class of sets?

In 1996 Papadimitriou and Yannakakis noted that there exists an $n^{O(\log n)}$ brute-force algorithm (where $n$ is the size of the input) for computing VC-dimension of a 0-1 matrix by checking all ...
Lev Reyzin's user avatar
  • 12k
6 votes

The complexity of determining if a fixed graph is a minor of another

There are old results showing that linear minor testing is possible for some specific graphs H, basically by looking at back-edge patterns in depth-first search, with significant effort for each H, ...
Michael Fellows's user avatar
6 votes

How many tautologies are there?

This is an extended comment to complement Ryan's answer, which deals with the thresholds where the number of clauses becomes large enough that the instance is almost surely unsatisfiable. One can also ...
András Salamon's user avatar
6 votes

Can the "mutual independence" condition in the Lovász local lemma be weakened?

The formulation on p.70 of the 4th edition of The Probabilistic Method by Alon and Spencer is along the lines you state.
kodlu's user avatar
  • 2,070
6 votes
Accepted

Number of local maxima in MAX-2-SAT

One can get a $n \choose n/2$ lower bound by considering the $n$ variable formula that for every pair $x$, $y$, of variables contains the clauses $(x \vee y)$ and $(\neg x \vee \neg y)$. The total ...
daniello's user avatar
  • 3,266
6 votes
Accepted

Enumerating all simply typed lambda terms of a given type

This question has been considered several times in the academic community, from the practical: Yakushev & Jeuring, Enumerating Well-Typed Terms Generically Fetsher & al, Making Random ...
cody's user avatar
  • 13.9k
6 votes
Accepted

Was this complexity measure studied before?

What you call the "revealing complexity" is sometimes called the (deterministic) query complexity of exact learning with membership queries. Exact learning refers to the fact that you have to ...
Robin Kothari's user avatar
6 votes
Accepted

Reference: Cancellability of the Dyck congruence

Your assertion is wrong, the congruence $\equiv$ is not cancellable from the right: for instance $\bar a a \bar a \equiv \bar a$, but $\bar a a \not\equiv 1$. By the way the quotient $\Sigma^*/{\...
J.-E. Pin's user avatar
  • 4,831

Only top scored, non community-wiki answers of a minimum length are eligible