28

These problems are polynomially equivalent. Indeed, suppose that you have an algorithm that can decide whether two graphs are isomorphic or not, and it claims that they are. Attach a clique of size $n+1$ to an arbitrary vertex of each graph. Test whether the resulting graphs are isomorphic or not. If they are, then we can conclude that there's an isomorphism ...


23

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to. For example, suppose you have a 3-sat problem: (¬x1 ∨ ¬x3 ∨ ¬x4) ∧ (x2 ∨ x3 ∨ ¬x4) ∧ (x1 ∨ ¬x2 ∨ x4) ∧ (x1 ∨ x3 ∨ x4) ∧ (¬x1 ∨ x2 ∨ ¬x3) Or, in table form with each row being a 3-clause, x meaning "this variable false", o ...


17

More specific to Babai's algorithm: yes, the algorithm not only finds an isomorphism, it finds generators of the automorphism group (and therefore effectively finds all isomorphisms) as part of the algorithm, that is, without the reduction of domotorp's answer. In terms of deciding existence of an isomorphism (resp., unknotting) vs actually finding one, the ...


16

Given a satisfiable 2-CNF $\phi$, you can compute a particular satisfying assignment $e$ by an NL-function (that is, there is an NL-predicate $P(\phi,i)$ that tells you whether $e(x_i)$ is true). One way to do that is described below. I will freely use the fact that NL is closed under $\mathrm{AC}^0$-reductions, hence NL-functions are closed under ...


14

If the function f is in #P, then given an input string x of some length N, the value f(x) is a nonnegative number bounded by $2^{poly(N)}$. (This follows from the definition, in terms of number of accepting paths of an NP verifier.) This means that many functions f lie outside of #P for uninteresting reasons---either because f is negative, or, in the case ...


9

This problem has been shown to be NP-complete in the following paper: S. Fortune, J. Hopcroft, J. Wyllie: "The directed subgraph homeomorphism problem" Theoretical Computer Science 10 (1980), pp. 111-121


8

Your problem is called the Median string problem. Nicolas and Rivals proved that the Median String problem (under the Levenshtein distance) is NP-complete even for binary strings.


7

I think you may be misunderstanding the sentence "Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent." This is not about reductions being inherent to self-reducibility (in the sense Goldreich uses it), but rather about Cook reductions being inherent to this notion, in the sense that they cannot be replaced by Karp reductions. ...


7

If crossover is excluded from genetic algorithms, they become something between the gradient descent and the simulated annealing. The main effect of crossover consists in the exchange of parts of different solutions. If an optimization task can be loosely decomposed into somewhat independent subtasks, and this decomposition is reflected in genes, then ...


5

Everything interesting happens in this paper happens within the 2D subspace generated by the two vectors $|s\rangle$ and $|w\rangle$. The vector $|r\rangle$ is a vector from this subspace orthogonal to $|w\rangle$, giving us the basis $|w\rangle, |r\rangle$, where the analysis will be very simple (using 2x2 matrices). The norm in the second question is ...


4

Local search (with a single swap) doesn't give you a good approximation factor in the worst case for $k$-center, as illustrated by the following example. Take a simplex in $\mathbb{R}^{k-1}$, and put $k$ points at each of the $k$ vertices, for a total of $k^2$ points. Note that between each pair of vertices of the simplex the distance is 1. The optimal ...


4

Please see the comments below by Emil Jeřábek, so I am not that sure anymore that the problem is harder. No, it is not known but it is harder than PPP :) Here I focus on the $M=2N+1$ case, so $t=3$, that is, we want $3$ inputs that map to the same output. In Papadimitriou's seminal paper "On the Complexity of the Parity Argument" he defined PPA-3 similarly ...


4

The problems have been proved to be equivalent (and thus PPAD-complete), see Section 8 in The Hairy Ball Problem is PPAD-Complete by Paul W. Goldberg and Alexandros Hollender.


4

This is an interesting question, and I can only give a partial answer. It is easy to see that the construction on p. 505 of Papadimitriou’s paper shows the equivalence of AUV with its special case MANY ENDS OF THE LINE (MEOL): Given a directed graph $G$ with in-degree and out-degree at most $1$ (represented by circuits as above), and a nonempty set $X$ ...


3

First of all, there is a lot of information in this related question: Max Min of function less than Min max of function. That said, the source of your problem is a confusion about which choices are available to each player when it is their turn. Consider the left-hand side of your first example: writing this in matrix form, each player gets to choose ...


3

In addition to the accepted answer, here is a recent paper (December '14) on the complexity of counting certain restricted models of Linear-time Temporal Logic. Higher, and more esoteric, complexity classes are present in the results shown: variants of the problem are $\#PSPACE$-complete, $\#EXPTIME$-complete, etc. The Complexity of Counting Models of ...


3

I’m not sure about the exact definition as given. However, the kind of search problems that has been studied the most in the literature are NP-search problems. In this context, there is no meaningful difference between “BPP-like”, “RP-like”, or “ZPP-like” randomized polynomial-time algorithms, as we can check the correctness of any purported solution in ...


2

Change the binary search procedure to pick a weighted midpoint at each time step: 1. Input: Search key K, sorted array A, probability distribution P. 2. Initialize m=0, M=n=len(A)=len(P). 3. Repeat: 4. Pick i with m <= i < M such that 5. sum(P[j] for m<=j<i) <= sum(P[j] for m<=j<M)/2 6. and 7. sum(P[j] for i<j&...


2

This does not directly answer your question, but if $f$ is $n$-variate, and is known to have partial degrees at most $D$ and at most $T$ terms, and $\mathbb{F}$ is known to contain an element $\omega$ of multiplicative order exceeding $D$, then we cannot have $f(\omega^i, \dots, \omega^i)=0$ for $i=0,1,\dots,2T-1$ by Prony's method / BCH decoding / Ben-Or ...


2

The linked PDF, "Handout 2 for Stanford University — CS254: Computational Complexity", defines four types of "computational problems": Decision problems Search problems Optimization problems Counting problems As the document notes at the beginning, it focuses on the first two: decision and search problems. In this course we will deal with four types of ...


1

Extended comment of an idea or two toward a lower bound. Let $B = \Theta(\log n)$, say (though the best choice may be different), and let $\{v_1,\dots,v_n\} = \{\frac{1}{n}B, \dots, \frac{n-1}{n}B, B\}$. Consider drawing the input by picking a permutation of these values uniformly at random. The idea should be that if we fix the indices of all values except ...


1

There's a straightforward algorithm for your original problem, based on a linear scan through the array with two pointers, one to $a$ and the other to the largest $b$ such that $|a-b|<c$. The running time will be linear in the number of pairs $a,b$ that need to be output. So, this answers your question in the positive: if $c$ is small enough that the ...


1

A good old trick is that it's sufficient to give an algorithm that achieves this with $O(\log n)$ expected number of coin flips and $99\%$ probability, as if we are exceeding the expected running time a lot, we can just output anything, using Markov's inequality this won't ruin our error much. And this we can do as follows. Always keep an active interval ...


1

You may have a look at the article "The Analysis of Evolutionary Algorithms — A Proof That Crossover Really Can Help" published in 2002 by Jansen and Wegener in the journal Algorithmica. This might not really answer your two questions, but at least it shows that your statement ("It seems to me that one can obtain similar results with algorithms that do not ...


1

As observed in Aaron Roth's answer, what you're describing does indeed appear to be PLS. In such cases, there are many, many alternative approaches under the heading of `metaheuristics'. A great introduction to the topic is "Essentials of Metaheuristics" by Sean Luke, but basically this includes techniques like simulated annealing, tabu search, genetic ...


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