The search-problem tag has no wiki summary.
13
votes
4answers
285 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
283 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
385 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 ...
11
votes
1answer
207 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 ...
0
votes
0answers
129 views
Optimal search path in a chessboard grid [closed]
Suppose we are given the $t \times t$-chessboard, where $t \geq 1$. Suppose we start at the top left corner with the king. The king searches the chessboard for a treasure that is hidden at a cell of ...
3
votes
0answers
109 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 ...
2
votes
0answers
63 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 ...
-2
votes
1answer
177 views
how to do binary search in one lie model？ [closed]
the question is like this: there is a sorted list of n numbers. Given x, find a number which is equal to x in the sorted list. Here we assume that x is indeed in the list. There is an oracle that can ...
2
votes
1answer
173 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 ...
21
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
3answers
423 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 ...
