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 ...
- 6,985
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.
- 2,883
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$. ...
- 7,039
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 ...
- 18.2k
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 ...
- 9,697
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/...
- 8,923
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,...
- 24.9k
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 ...
- 14.1k
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 ...
- 161
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 ...
- 6,775
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. ...
- 18.2k
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 ...
- 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}$...
- 27.5k
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$ ...
- 10.9k
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 ...
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$? ...
- 27.5k
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 ...
- 6,985
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 ...
- 51.1k
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$...
- 51.1k
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 ...
- 10.9k
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 ...
- 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, ...
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.
- 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 ...
- 3,276
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 ...
- 14k
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 ...
- 13.8k
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^*/{\...
- 5,101
6
votes
Accepted
Distinguishability a set of permutations
Here are loose lower and upper bounds.
Fix $d \le n$ as in the post. Let $k^*$ denote the largest possible value of $k$ meeting the conditions in the post. We show that $k^* = \exp(\Theta(d\log d)$...
- 10.9k
6
votes
Pulling a graph across a partition
What you are looking for is known as Cutwidth. The problem is NP complete and quite well studied. For example it has a $O((\log n)^{3/2})$- approximation algorithm and is fixed parameter tractable ...
- 3,276
6
votes
Accepted
Does such a bipartite graph exist?
Theorem 1. For every $d$ and $k$, there is a graph with the desired properties.
I'll describe the construction in two stages.
First, construct a bipartite multi-graph $G_1=(L_1, R_1, E_1)$ where
$L_1=...
- 10.9k
Only top scored, non community-wiki answers of a minimum length are eligible