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, ...
- 36.9k
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....
- 27.3k
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 ...
- 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 ...
- 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 ...
- 1,429
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&...
- 27.3k
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 ...
- 36.9k
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-...
- 36.9k
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^\...
- 16.9k
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 ...
- 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 ...
- 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,+,...
- 16.9k
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....
- 643
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 ...
- 16.9k
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 ...
- 5,840
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 ...
- 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 ...
- 16.9k
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 $\...
- 36.9k
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 ...
- 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 ...
- 50.9k
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 ...
- 2,247
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 ...
- 36.9k
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 ...
- 16.9k
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 ...
- 36.9k
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 ...
- 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 $...
- 2,552
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 ...
- 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. ...
- 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 ...
- 176
Only top scored, non community-wiki answers of a minimum length are eligible