28 votes
Accepted

Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

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+...
  • 13.7k
27 votes
Accepted

Oracle Construction for Grover's Algorithm

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: ...
  • 1,468
17 votes

Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

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 ...
16 votes
Accepted

Complexity of the search version of 2-SAT assuming $\mathsf{L = NL}$

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 ...
14 votes
Accepted

Above #P and counting search problems

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 ...
  • 4,584
9 votes

How to efficiently find a loop between two nodes in a directed graph?

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), ...
  • 5,732
8 votes
Accepted

Find a string with minimal edit distance from a set of given strings

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 votes
Accepted

Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?

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 (...
4 votes
Accepted

Approximation Ratio of Local search for $k-$center problem

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 ...
  • 8,471
4 votes
Accepted

Does PPAD really capture the notion of finding another unbalanced vertex?

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.
  • 13.7k
4 votes

Does PPAD really capture the notion of finding another unbalanced vertex?

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 ...
4 votes
Accepted

Is generalized pigeonhole search known to be no harder than PPP?

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$, ...
  • 13.7k
3 votes

Above #P and counting search problems

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 ...
  • 31
3 votes
Accepted

Minmax vs Maxmin

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 ...
3 votes
Accepted

Literature reference for search-BPP

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 ...
2 votes
Accepted

Biased binary search?

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,783
2 votes

How to find a non-zero point of a non-zero polynomial of low degree?

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$ ...
2 votes

Is any computational problem a search problem?

The linked PDF, "Handout 2 for Stanford University — CS254: Computational Complexity", defines four types of "computational problems": Decision problems Search problems Optimization problems ...
  • 123
1 vote

Find an approximate argmax using only approximate max queries

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\}...
  • 7,090
1 vote

What is the largest distance that still guarantees a linear time distance search?

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 ...
  • 10.5k
1 vote

Oracle Construction for Grover's Algorithm

You can also get a solution which uses only one ancillary qubit (but relies on NOT gates with multiple controls), by getting your input to algebraic normal form (e.g. with Mathematicas ...
1 vote

Binary Search with Errors

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 ...
  • 13.7k
1 vote

A search problem and no algorithm for it

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

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