29
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,498
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.9k
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 ...
- 36.9k
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,772
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.
- 20.8k
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 (...
- 18.1k
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 ...
- 9,595
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.9k
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
...
- 16.9k
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 ...
- 16.9k
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 ...
- 2,500
3
votes
Accepted
Is Levin's Universal Search valid for the integer factorization problem while using the AKS test?
In a practical sense, Levin search is not useful. It has an enormous constant factor (exponential in the length/size of the optimal factoring algorithm). This makes it of little use in practice.
In ...
- 11.7k
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,803
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$ ...
- 66
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,595
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 ...
- 11.7k
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 ...
- 11
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.9k
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 ...
- 773
Only top scored, non community-wiki answers of a minimum length are eligible