# Tag Info

27

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, Sublattices of the polynomial time degrees, Inform. & Control 65(1):63-84, 1985).

20

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 revisions, second revisions, new counter-examples, further revisions, further counter-examples, and so on. It would be much better, if the authors were able to ...

17

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.org/abs/2107.02748

15

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 complexity classes that we know of. There are other sorts of "collapses" though that I think should be pointed out. Most importantly, I think, is the &...

15

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 mechanics while integration is art", they're not inviting you to formalize "mechanics" and "art" and prove the statement, they're trying to convey a general ...

13

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&sciodt=0,5 I'd be also interested to know of any stronger collapses than this. Edit (8/24): OK, I thought of some potentially stronger collapse, which ...

12

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-complete language has a poly-time group action with few orbits, PH collapses. For, with this additional assumption about sampleability, the standard $\mathsf{coAM}$ ...

12

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^\epsilon})$. Indeed, fix an arbitrary EXP-complete problem $L$, and assume that it is computable in time $2^{n^c}$. Let $d>c/\epsilon$, and consider the problem ...

12

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 between all these things. [Warning: while I believe I've gotten the definitions right, some of the things below reflect my personal preferences - I've tried to be ...

11

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 cubic graphs By Brooks' theorem, every cubic graph (except $K_4$) is 3-colorable and hence 3-partite.

11

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 Large Integers on an Actual Computer?, likely written with similar motivation to yours.

10

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.at/scholar?oi=bibs&cluster=4944920843669159892&btnI=1&hl=de (Schöpp, U. (2008). A formalised lower bound on undirected graph reachability. In Logic ...

9

$\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 that any barely superpolynomially expanded version of $C$ is not in $\mr{P/poly}$. Let me say that $f\colon\mathbb N\to\mathbb N$ is a superpolynomial bound if ...

8

$\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 generally that if $S$ is in $\mr{FP}^{\mr{SAT}[q(n)]}$, then SAT is solvable in time $\mr{poly}(n2^{q(n)})$. In particular, assuming the exponential time ...

8

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 of size $O(\log n)$. at each step, you read a new letter $a\in\Sigma$ of your stream, and you are allowed to modify your memory $m$ you then have to say whether ...

7

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 $\mathbb{Z}_{p_1^{k_1}} \oplus \dotsb \oplus \mathbb{Z}_{p_\ell^{k_\ell}}$, where $\ell \leq \log_2|R|$. Now, if $R$ is only given to you by generators and ...

7

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 past position is forbidden. This is the rule used for instance in China and western countries. It is simple to state, but could bring some difficulties to ...

7

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 magnitude (e.g. Bender et al, "Two Simplified Algorithms for Maintaining Order in a List", ESA 2002, https://erikdemaine.org/papers/DietzSleator_ESA2002/) with ...

6

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 in characteristic 2 (so not VNP-complete unless VP=VNP). (In contrast, the Hamiltonian Cycle polynomial is VNP-complete in all characteristics.) The ...

6

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$. You say above that you can compute this by repeated squaring modulo $m$, and that this needs $O(\log r)$ multiplications. This is true, and it's certainly ...

6

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 above, the question as actually stated has a trivially true answer for all functions, that is, $f(n)=O(g(n))$ is equivalent to $g(n)=\Omega(f(n))$ immediately ...

6

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 membership problem is to actually find a word (if any) in $A,B$ that equals $C$. Its complexity may depend on whether you want to allow $A^{-1}, B^{-1}$ in your word (...

6

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 working in the RAM model with cells of size logarithmic in the maximal size of the window, and that all the operations regarding the automaton are constant time. ...

6

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. At start, we have an empty word and then we receive updates taking one of the following forms: Insert a letter at the beginning of the word Insert a letter at ...

6

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 or 48, with 8 being possible only for corner cuties and 12 only being possible for edge-center cubies with N odd. Divide the cubies into orbits, then generate a ...

5

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 a given $\pi_1$-OBDD $F_1$ into an equivalent $\pi_2$-OBDD $F_2$ by using syntactic rules. If you have a bound $B$ on the representation of $F_1$ by $\pi_2$-...

5

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.

5

This problem is NP-hard. Although it may be possible to find some canonical form for string isomorphism, say, in quasi-poly time, without upsetting our current guesses as to how the complexity world looks, finding the lexicographically least isomorphic string is NP-hard. This is precisely the content of Proposition 3.1 here. In fact, they show it remains NP-...

5

If I understood it well, (1) is also NP-complete, a possible reduction is from SUBSET SUM: Given a set of $m$ positive integers $A = \{a_1, ..., a_m\}$, and a positive integer $B$, is there a subset of $A' \subseteq A$ a such that $\sum_{a_i \in A'} a_i$ You simply pick $n = (m+1)$ and build your set in this way: add $a_1, a_2, , ..., a_m$ add $m$ zeros ...

5

I think of the following argument: if we can check whether two sequences have equal Kolmogorov complexity we can write a program that enumerates all sequences of length $\le N$ and divides them into equivalence classes. We know that $K(x) \le |x|$. So, we have at most $N$ equivalence classes of sequences. One of this classes should be of size at least \$2^{...

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