The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
123 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 ...
3
votes
3answers
193 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
67 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
106 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
79 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
318 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
298 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
421 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
227 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 ...
5
votes
0answers
132 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
66 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
206 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 ...
22
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
444 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 ...