26

Here is a rough summary of the status based on a presentation given by Vardi at a Workshop on Finite and Algorithmic Model Theory (2012): It was observed that hard instances lie at the phase transition from under- to over-constrained region. The fundamental conjecture is that there is strong connection between phase-transitions and computational complexity ...


14

Yes, there has been a lot of work since Cheeseman, Kanefsky and Taylor's 1991 paper. Doing a search for reviews of phase transitions of NP-Complete problems will give you plenty of results. One such review is Hartmann and Weigt [1]. For a higher level introduciton, see Brian Hayes American Scientist articles [2] [3]. Cheesemen, Kanefsky and Taylor's ...


14

The number field sieve has never been analyzed rigorously. The complexity that you quote is merely heuristic. The only subexponential algorithm which has been analyzed rigorously is Dixon's factorization algorithm, which is very similar to the quadratic sieve. According to Wikipedia, Dixon's algorithm runs in time $e^{O(2\sqrt{2}\sqrt{\log n\log\log n})}$. ...


14

Probably not the best answer, but perhaps this is a useful starting point. If we wish to represent a non-negative integer, we can store it as a set of residues modulo sequential prime numbers starting from 2. In this form comparison is potentially hard, but multiplication and addition can be done pretty quickly. The product of the first $n$ primes is ...


11

One such algorithm for $\#3\operatorname{SAT}$ is due to Kutzkov.


9

I you’re looking for natural problems, you can compute many counting problems on planar graphs in time $\exp(\sqrt n)$ because of the planar separator theorem. For example, everything that can be expressed as a valuation of the Tutte polynomial [1]. Most of these problems remain #P-hard restricted to planar graphs, see Tutte Polynomial @ Wikipedia. [1] K. ...


9

The first approach can be formalized as follows. Let $P$ be an arbitrary set of $n$ points on the positive branch of the parabola $y=x^2$; that is, $$ P = \{ (t_1, t_1^2), (t_2, t_2^2), \dots, (t_n, t_n^2) \} $$ for some positive real numbers $t_1, t_2, \dots, t_n$. Without loss of generality, assume these points are indexed in increasing order: $0 < ...


8

There seem to be typos in what you wrote; I take it you're asking: is there a function $f \in NEXP$ such that for all polynomials $p$ and infinitely many $n$, no ACC0 circuit of $p(n)$ size can compute $f_n$ on more than $1-1/p(n)$ inputs of length $n$? As far as I know, this is open. But here is a possible path to doing it. We know that every $NEXP$-...


7

My personal (and biased) take is that asymptotic worst-case analysis is a historical stepping stone to more practically useful kinds of analysis. It therefore seems hard to justify to practitioners. Proving bounds for the worst case is often easier than proving bounds for even "nice" definitions of average case. Asymptotic analysis is also often much ...


6

In the past few months, a version of the number field sieve has been analyzed rigorously: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring Basically the worst-case running time is $L_n(1/3, 2.77)$ unconditionally and $L_n(1/3, (64/9)^{1/3})$ under GRH. This is not for the "classic" number field sieve, but a ...


4

Lower bounds and worst-case analysis don't usually go together. You don't say an algorithm will take at least exponential time in the worst case, therefore it's bad. You say it can take at most linear time in the worst case, and therefore is good. The former is only useful if you are going to run your algorithm on all possible inputs, and not merely an ...


3

Let $\ell$ be the length of the longest common substring. The number of longest common substrings $m$ is at most $$ m \leq \min(k^\ell,n-\ell+1). $$ Let $x = \log_k n$. If $\ell \leq x-1$ then $m \leq n/k$. Otherwise, $m \leq n-\log_k n+2$. One checks that the latter bound is always worse, and so $m \leq n-\log_k n+2$.


2

If Graph Isomorphism is randomly self-reducible in the sense of the question (clarified in the comments), then it could be solved in poly time. The reason is that there is in fact an average-case linear time algorithm for GI (even a canonical form) [BK]. For Group Isomorphism, this is not known. However, it's also somewhat of a funny question, because of ...


1

Assuming that the $c_{a,b}$ values appears in a nicely ordered way, you can use Horner's rule to evaluate the polynomial in $O(n^2)$ arithmetic operations. As mentioned by frogeyedpeas, you can't expect beating $n^2$ because it is the size of the input. Note that if you are interested by the number of bit operations then you need to multiply this by the ...


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