The tag has no wiki summary.

learn more… | top users | synonyms

11
votes
2answers
148 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
53 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
211 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 ...
0
votes
0answers
590 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
320 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
79 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
115 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
83 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
332 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
304 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
440 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
247 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
144 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
70 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
245 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 ...
23
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
454 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 ...