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,772
19 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,595
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
13 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
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
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,772
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.3k
11 votes

What are some examples of decidable Nautral Problems outside of EEXP?

Let me give a few examples in the form of decision procedures for natural first-order theories. By a result of Berman [1], Presburger arithmetic $\mathrm{Th}(\mathbb N,+)$ (or $\mathrm{Th}(\mathbb Z,+,...
Emil Jeřábek's user avatar
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
9 votes
Accepted

Is DFA language inclusion decidable in quasi-linear time?

EDIT: the question has an answer by Michael Wehar. A better than quadratic running time contradicts the strong exponential time hypothesis. https://cstheory.stackexchange.com/a/29166/2367 ORIGINAL ...
Hermann Gruber'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,598
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,598
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
Accepted

Most Matrices are Rigid

For simplicity, let us first consider the case $\mathbb{F}=\mathbb{F}_2$. Every non-rigid matrix can be specified by a rank-$r$ matrix $L$ and a matrix $S$ of total sparsity $s$. Since every low-rank ...
Alex Golovnev'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
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

Petri net termination

Testing whether a Petri net $\mathcal{N} = (P, T, F)$ does not terminate from a marking $M_0$ can be decided by testing whether there exist a firing sequence $\sigma$ and markings $M, M'$ such that $...
Michael Blondin's user avatar
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

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