# Tag Info

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, ...
• 35.7k
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,712

### 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.3k

### 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
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,042
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.3k
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-...
• 35.7k
Accepted

• 35.7k
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 ...
• 7,653
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.2k

### 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 ...
• 35.7k

### 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$. ...
• 277
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 ...
• 14.8k
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 ...
• 35.7k

### 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

### 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 ...
• 685
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. ...
• 685
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
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 ...
• 1,855
Accepted

### Complexity of Computing Lexicographically Minimal Element of Orbit

This problem is $FP^{NP}$-complete, as shown here. It means that the lexicographical leader of the orbit is built in deterministic polynomial time with access to a $NP$-oracle.
• 550