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


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

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


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


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

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


5

In 1998, Michel X. Goemans gave an ICM talk, in which, he addressed this issue:"Semidefinite programs can be solved(or more precisely, approximated) in polynomial-time within any specific accuracy either by the ellipsoid algorithm or more efficiently through interior-point algorithms...The above algorithms produce a strictly feasible solution(or slightly ...


4

This seems to be exactly the type of question studied by Moses Ganardi and coauthors in recent years. In particular this paper and this extension prove nice trichotomies.


4

It roughly boils down to whether the problem definition could be circular: An artificial problem is one constructed to fill its class criteria. A natural problem does not rely on its method of construction to fill the class criteria. Ladner's construction is known to be NP-intermediate, provided NPI exists. Proving any candidate for NPI natural problems ...


3

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 emphasis): We present a Coq library that allows for readily proving that a function is computable in polynomial time. It is based on quasi-interpretations that, ...


2

In regards to (2), conditional super-linear lower bounds are known. A recent preprint by Afshani, Freksen, Kamma, and Larsen proves an $\Omega(n \log n)$ lower bound for the size of Boolean circuits computing integer multiplication, assuming a certain conjecture on network coding in undirected graphs. (See also this blog post and a follow-up post.) From the ...


1

There's a straightforward algorithm. For each edge $(u,v)$, compute the multiset of products of weights of paths of length 2 from $u$ to $v$: $$S_{u,v} = \{\text{wt}(u,t) \cdot \text{wt}(t,w) : (u,t) \in E \land (t,w) \in E\}.$$ These multisets can be computed in at most $O(|V| \cdot |E|)$ time. In practice it suffices to enumerate all edges $(u,v)$, ...


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