27 votes
Accepted

Does Karp reducibility yield a total order?

Far from it. Indeed, any countable distributive lattice embeds as a sub-partial-order of $\leq_p$, even if we only consider those degrees in between two given fixed languages (K. Ambos-Spies, ...
Joshua Grochow's user avatar
20 votes

Status of PP-completeness of MAJ3SAT

Hopefully the following paper finally resolves this question: it says that MAJORITY 3SAT is in polynomial time. (And it proves a bunch of other unexpected results on related problems.) https://arxiv....
Ryan Williams's user avatar
20 votes
Accepted

Is there a counterexample to this work?

Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first ...
Gamow's user avatar
  • 5,742
16 votes
Accepted

What is a natural problem in theory of computation?

To be clear, it's not meant to be formalizable. It's not a theorem, it's an observation about the world -- it's okay if "natural" is subjective here. For analogy, if someone says "differentiation is ...
usul's user avatar
  • 7,175
15 votes

Collapses under the assumption that $NEXP\subseteq P/Poly$

A whole lot of fun things happen. Most of the ones I know of start with the IKW paper. There, the collapse $\textrm{NEXP} = \textrm{MA}$ is shown, and (I think) is the strongest literal collapse of ...
Andrew Morgan's user avatar
13 votes
Accepted

Collapses under the assumption that $NEXP\subseteq P/Poly$

I believe the strongest is that $NEXP = MA$. This was proved by Impagliazzo Kabanets and Wigderson. See https://scholar.google.com/scholar?cluster=17275091615053693892&hl=en&as_sdt=0,5&...
Ryan Williams's user avatar
12 votes
Accepted

Are There Highly Symmetric NP- or P-complete Languages?

For NP, this seems hard to construct. In particular, if you can also sample (nearly) uniform elements from your group - which is true for many natural ways of constructing groups - then if an NP-...
Joshua Grochow's user avatar
12 votes
Accepted

EXP-Complete Problems vs Subexponential Algorithms

Due to popular demand, I’m converting my comment to an answer. A simple padding argument shows that for every constant $\epsilon>0$, there exist EXP-complete problems in $\mathrm{DTIME}(2^{n^\...
Emil Jeřábek's user avatar
12 votes
Accepted

What exactly are the classes FP, FNP and TFNP?

Emil Jerabek's comment is a nice summary, but I wanted to point out that there are other classes with clearer definitions that capture more-or-less the same concept, and to clarify the relation ...
Joshua Grochow's user avatar
11 votes
Accepted

What is the complexity of vertex cover on k-partite graphs?

For bipartite graphs, vertex cover is polynomially solvable by routine techniques from matching theory. For $k$-partite graphs with $k\ge3$, we observe the following: Vertex cover is NP-complete on ...
Gamow's user avatar
  • 5,742
11 votes
Accepted

Complexity of the Schönhage–Strassen algorithm

What you are actually asking is for the performance of the Schönhage–Strassen algorithm in the unit cost RAM (rather than its bit complexity). This is covered in Fürer's paper How Fast Can We Multiply ...
Yuval Filmus's user avatar
  • 14.2k
10 votes

Formally Verified Complexity Theory

In the following paper my colleague Uli Schöpp presents a formal verification (in Coq) of a nontrivial result by Cook and Rackoff on the computational power of graph automata. https://scholar.google....
Martin Hofmann's user avatar
9 votes

P/Poly vs Uniform Complexity Classes

$\let\mr\mathrm$There are several results in the literature stating that a certain class $C$ satisfies $C\nsubseteq\mr{SIZE}(n^k)$ for any $k$, and usually it is straightforward to pad them to show ...
Emil Jeřábek's user avatar
8 votes
Accepted

Is the computation of a satisfying variable assignment for a Boolean formula $FP^{NP}$-hard?

$\let\mr\mathrm$Let me denote the problem as $S$. Gottlob and Fermüller state that if $S$ is solvable in $\mr{FP}^{\mr{SAT}[\log n]}$, then $\mr{P}=\mr{NP}$. However, the argument actually shows more ...
Emil Jeřábek's user avatar
8 votes

Constraints on sliding windows

It seems it would depend on your particular model, in particular what information you have access to. From what I infer, you are thinking of the following model: you have a memory $m$, for instance ...
Denis's user avatar
  • 8,473
8 votes
Accepted

Validity problem of intuitionistic two-variable logic

The two-variable fragment of intuitionistic first-order logic is undecidable, as proved in Roman Kontchakov, Agi Kurucz, and Michael Zakharyaschev: Undecidability of First-Order Intuitionistic and ...
Emil Jeřábek's user avatar
7 votes

Number of solutions for a system of linear equations over a finite ring

The answer to (1) is yes (regardless of the properties D.W. asked for in the comments), depending on how $R$ is given: First, note that since $R$ is finite, the abelian group $(R,+)$ is of the form $\...
Joshua Grochow's user avatar
7 votes
Accepted

The theoretical complexity of Go - The state of the art

The state of the art for the theoretical complexity of go is well summed up on Wikipedia, with relevant references. The main remaining open problem is for rules using a superko, i.e. repeating any ...
Denis's user avatar
  • 8,473
7 votes
Accepted

On the complexity of a "list" datastructure in the RAM model

It appears that all of these operations can be performed in time $O(\log n/\log\log n)$ on a RAM, by combining methods for maintaining a dynamic labeling of the list elements by integers of polynomial ...
David Eppstein's user avatar
7 votes

Is DFA language inclusion decidable in quasi-linear time?

The following blog post points to a paper that discusses this question. The answer is, a better than quadratic algorithm would yield improved running times for several notoriously hard computational ...
Hermann Gruber's user avatar
6 votes

How is the VP=VNP question in char 2 different from other char? What is the current frontier in regards to this question?

In terms of these complexity classes as a whole, not much is known that distinguishes characteristic 2 from other characteristics. The most frequently arising difference is that the permanent is easy ...
Joshua Grochow's user avatar
6 votes

Computational complexity of modular power towers (tetration)

Sorry if this answer doesn't tell anything nontrivial, but you don't seem to imply these results in the questionm. Consider first the problem of computing a modular exponentiation $ a^r \mod m $. ...
Zsbán Ambrus's user avatar
6 votes
Accepted

obvious property of big O, big Omega, and big Theta

EDIT: Now that I have fresh eyes in the morning, I see that I have thoroughly misread the question. The answer below applies to “if $f(n)\ne O(g(n))$, then $f(n)=\Omega(g(n))$”. As noted in comments ...
Emil Jeřábek's user avatar
6 votes
Accepted

What's the complexity of factoring over a set of generators (say in $GL_2$)?

This is usually called the (constructive) membership problem (rather than a "factorization" problem). The membership problem is to decide whether $C \in \langle A,B \rangle$; the constructive ...
Joshua Grochow's user avatar
6 votes

Formally Verified Complexity Theory

A nice example is Hugo Férée, Samuel Hym, Micaela Mayero, Jean-Yves Moyen, David Nowak: Formal proof of polynomial-time complexity with quasi-interpretations. CPP 2018: 146-157 Their abstract (my ...
Clément's user avatar
  • 161
6 votes

Constraints on sliding windows

Context Let $\mathcal{L}$ be a fixed regular language and let ($\mathcal{Q}, \Sigma, \delta, q_0, \mathcal{F})$ be an automaton recognizing $\mathcal{L}$. I will suppose in this post that we are ...
Louis's user avatar
  • 775
6 votes
Accepted

Constraints on sliding windows

Here is a second, simpler and more general answer that was obtained after discussing with a3nm. Problem We fix a regular language $\mathcal{L}$ and we are interested in the following word problem. ...
Louis's user avatar
  • 775
6 votes
Accepted

Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time

Well, the easy answer is that you don't traverse the graph of moves, you just generate a random group element directly. A non-face-center cubie in an NxNxN cube will have an orbit of size 8, 12, 24 ...
Craig's user avatar
  • 176
5 votes
Accepted

Equivalence for Constant-width Read-Once Branching Programs with Distinct Orders

In "Branching Programs and Binary Decision Diagrams" by Ingo Wegener [1] (very good, complete reference to check this kind of fact on branching programs), Section 5.7 deals with how you can transform ...
holf's user avatar
  • 2,059

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