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.4k
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....
- 26.7k
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,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 ...
- 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 ...
- 1,419
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&...
- 26.7k
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.4k
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^\...
- 15.6k
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 ...
- 36.4k
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,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 ...
- 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....
- 613
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 ...
- 15.6k
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 ...
- 15.6k
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,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 ...
- 15.6k
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.4k
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,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 ...
- 50.6k
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 ...
- 5,614
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.4k
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 $.
...
- 287
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 ...
- 15.6k
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.4k
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
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
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 ...
- 2,059
Only top scored, non community-wiki answers of a minimum length are eligible