Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [search-problem]

The tag has no usage guidance.

6
votes
0answers
264 views

Search in a sorted matrix

A matrix $M$ is sorted if $M_{i,j}\leq M_{i+1,j}$ and $M_{i,j}\leq M_{i,j+1}$. Consider the following problem. Search in a sorted matrix Given a $n\times m$ sorted matrix $M$, where $n\leq m$....
7
votes
1answer
101 views

Why is the “general notion of a reduction […] inherent to the notion of self-reducibility”?

While reading "Computational Complexity: A Conceptual Perspective" by Oded Goldreich, I have come across the following passage, which I simply cannot get my head around: Note that the general ...
3
votes
0answers
82 views

Critical Assignments vs Read-Once Branching Programs - Reference Request

Straight to the point: I'm looking for a reference for the fact that the complexity of a read-once branching program solving the search problem for an unsatisfiable formula $F$ is at least the ...
-1
votes
1answer
29 views

Algorithm in logarithmic time that finds a number with the help of a subarray that is not in the array

The question is as follows. Given: A sorted array A of n integers where A[n − 1] − A[0] ≥ n. Asked: Give an algorithm and the invariant of the algorithm that finds a number between A[0] and A[n - 1] ...
0
votes
0answers
25 views

Searchable finite field

Let $F$ be a large finite field, where the elements are strings of length $n$. We require, addition, multiplication, and division to be efficient (polynomial in $n$). We say that $F$ is searchable if ...
3
votes
1answer
126 views

Literature reference for search-BPP

I'm trying to find the first article/paper that the complexity class search-BPP appeared in. Search-BPP, as defined as follows (in [1]): A binary relation $R$ is in search-BPP if there is a ...
13
votes
2answers
537 views

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

I have a (hopefully simple, maybe dumb) question on Babai's landmark paper showing that $\mathsf{GI}$ is quasipolynomial. Babai showed how to produce a certificate that two graphs $G_i=(V_i,E_i)$ for ...
10
votes
1answer
290 views

Find an approximate argmax using only approximate max queries

Consider the following problem. There are $n$ unknown values $v_1, \cdots, v_n \in \mathbb{R}$. The task is to find the index of the largest one using only queries of the following form. A query ...
-1
votes
1answer
51 views

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

Suppose we have two sorted arrays A and B consisting of unique real numbers. We want to find all pairs of the form (a $\in$ A, b $\in$ B) such that, for some c $\in R+$, their absolute difference $\...
10
votes
1answer
3k views

Oracle Construction for Grover's Algorithm

In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's ...
1
vote
1answer
441 views

Is any computational problem a search problem? [closed]

I was looking for a formal and general definition of a computational problem (and major subclasses thereof e.g. decision, function and search problems). But, given the definitions I have found thus ...
12
votes
2answers
458 views

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

Complexity class PPAD was invented by Christos Papadimitriou in his seminal 1994 paper. The class is designed to capture the complexity of search problems where the existence of a solution is ...
6
votes
1answer
215 views

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

Input: a bunch of binary strings: x_0, x_1, ... , x_n Output: a binary string y that minimizes edit(x_0, y) + edit(x_1, y) + ... edit(x_n, y) where edit(x, y) denotes the levenshtein distance, i.e. ...
10
votes
1answer
252 views

Can a random oracle change which TFNP problems are strongly hard-on-average?

I've been thinking about the following question at various times since I saw this question on Cryptography. Question Let $R$ be a TFNP relation. ​ Can a random oracle help P/poly to break $R$ ...
1
vote
1answer
219 views

Minmax vs Maxmin

I'm reading this paper about building a combat simulator for 8 unit vs 8 unit mini combats in StarCraft: Brood War. The basic idea is to build a search tree simulating these small combats in order to ...
5
votes
1answer
193 views

Binary Search with Errors

Suppose I give you $n$ labelled coins $C_1, \cdots, C_n$ of unknown bias. I promise you that the coins have been sorted by bias (i.e. $\forall i~~\mathbb{P}[C_i=1]\leq\mathbb{P}[C_{i+1}=1]$) and at ...
2
votes
1answer
320 views

Is there a FNP problem that's NP-hard but not FNP-hard?

For the reductions, choose a class C such that [it's clear what FC means] and FC is not known to be able to solve the satisfaction search problem, and assume that FC indeed can't solve that search ...
7
votes
2answers
247 views

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

Given a circuit that computes a polynomial $P(x_1 \dots x_n)$ of low formal degree over some large field $\mathbb{F}$. Moreover, given a point $X \in \mathbb{F}^n$, such that $P(X) \neq 0$. Can one ...
0
votes
1answer
82 views

Efficiently picking free position from array with uniform probability.

For each array position it is known if position filled or not. How efficiently pick one free position with uniform probability? That task happen during implementation of AI by Monter-Carlo method ...
15
votes
1answer
395 views

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

If $\mathsf{L = NL}$, then there is a logspace algorithm that solves the decision version of 2-SAT. Is $\mathsf{L = NL}$ known to imply that there is a logspace algorithm to obtain a satisfying ...
13
votes
2answers
235 views

Above #P and counting search problems

I was reading the wikipedia article about the eight queens problem. It is stated that, there is no known formula for the exact number of solutions. After some searching, I found a paper named "On the ...
-2
votes
1answer
2k views

What is the applications of kmp algorithm? [closed]

KMP algorithm works best when there is/are self matching(s) of pattern string that we want to search for. Usually it doesn't happen unless pattern is long enough. So where is the KMP application in ...
6
votes
1answer
239 views

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

Consider the TFNP search problem Given a positive integer $t$ in unary, positive integers $M$ and $N$ (in binary), and a function from $\{0\hspace{.02 in},\hspace{-0.04 in}1,\hspace{-0.03 in}2\...
0
votes
0answers
2k views

Most efficient algorithm to search an unsorted array with a very precise data structure

(I apologize in advance if this question sounds a bit practical, but I suspect it might have an interesting theoretical aspect.) I have a (large) array of data, not completely sorted, but with which ...
5
votes
3answers
818 views

The use of crossovers in Genetic Algorithm

My questions concern the use of crossovers in genetic algorithms. The three basic ingredients of genetic algorithms are: selection mutation crossover If we think of genetic algorithm acting on ...
3
votes
1answer
92 views

Questions about Farhi's pre-Adiabatic paper

I have been going through Eddie Farhi's 6-pages long pre-Adiabatic paper, An Analog Analogue of a Digital Quantum Computation. I guess I understand most of the math and physics but I am struggling ...
-4
votes
1answer
199 views

What exactly is a search space? [closed]

I am new to CS so excuse my question if it seems very rudimentary. I just want to make sure I understand the terminology 100% correct as I go along. Is a "search space" the total amount of all the ...
3
votes
0answers
90 views

Constant time search for rod segment

(I tried to ask at SO but maybe this has more to do with the CS theory.) Suppose I have a rod which I cut to pieces. Given a point on the original rod, is there a way to find out which piece it ...
15
votes
4answers
371 views

Worst number of questions needed to learn a monotonic predicate over a poset

Consider $(X, \leq)$ a finite poset over $n$ items, and $P$ an unknown monotonic predicate over $X$ (i.e., for any $x$, $y \in X$, if $P(x)$ and $x \leq y$ then $P(y)$). I can evaluate $P$ by ...
4
votes
2answers
321 views

Searching for the first item satisfying property with penalty for every test

The problem in terms of a step function on integers: A step function of integers is $0$ until $s$ (the "item" in question) and then $1$. That is, $s$ is the first integer that satisfies the property $...
13
votes
2answers
495 views

Does existence of a total $\mathsf{NP}$ search problem not solvable in polytime imply $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$?

It easy to see that if $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$ then there are total $\mathsf{NP}$ search problems which cannot be solved in polynomial time (create a total search problem by ...
12
votes
1answer
326 views

Minimal elements of a monotonic predicate over the powerset $2^{|n|}$

Consider a monotonic predicate $P$ over the powerset $2^{|n|}$ (ordered by inclusion). By "monotonic" I mean: $\forall x, y \in 2^{|n|}$ such that $x \subset y$, if $P(x)$ then $P(y)$. I am looking ...
6
votes
0answers
180 views

Tree search guided by a probabilistic oracle

I'm trying to find a solution for the following problem. I have a tree $T$ of branching factor $b$ and depth $d$. For the moment, I only care about the case where I restrict $b=2$, but I would be ...
3
votes
0answers
75 views

Load-balancing; Alternate methods of keeping track of nodes?

Reading various articles in the literature have given me only a few decent methods of keeping track of nodes before->after load-balancing them on a very large network. One popular method uses virtual-...
2
votes
1answer
407 views

Bloom filter for storage

I am reading about the Bloom filter, and I must say I am fascinated by the idea. I would like to know if it is possible to use it for storage. The problem with the Bloom filter is that, even if we ...
27
votes
5answers
3k views

Binary search generalizations for posets?

Suppose I have a poset "S" and a monotonic predicate "P" on S. I want to find one or all maximal elements of S satisfying P. EDIT: I'm interested in minimizing the number of evaluations of P. What ...
4
votes
4answers
616 views

A search problem and no algorithm for it

I would like to learn about the following search problem, in particular, which kind of algorithms exist for it. Suppose we have a huge search space $S$. For each element $s \in S$, we have the weight ...