# Questions tagged [search-problem]

A class of computational problems. Where decision problems call for a yes-or-no answer, search problems are looking for an object satisfying a certain property.

147 questions
Filter by
Sorted by
Tagged with
39 views

### Graph Search Algorithms that are practically fast on dense graphs

I'm trying to do some research on graph search algorithms that are practically fast on relatively dense graphs. Besides the common ones like A* or Dijkstra's, what are some graph search algorithms ...
17 views

### Zero Knowledge Protocol for Search Problem

Does anyone know any zero-knowledge protocol that addresses the search problem, i.e. finding the output to a query without revealing the query or any other output?
68 views

### Time complexity to convert a truth table to a boolean circuit

The SAT problem is often explained in terms of truth tables. Given some random boolean circuit, calculate its truth table; does there exist an output of $1$ in the truth table? But how about going the ...
50 views

### Finding the smallest subset s.t. all elements satisfy condition, using as few tests as possible

I'm having a hard time describing this problem without an example, so let's go with this: Say you have a program that is made up of many files. There are some files you could delete, and, while it ...
12 views

### Would proving that finding a satisfiable input is intractable prove that SAT is intractable? [duplicate]

With the SAT problem, there is a corresponding search variant. Given an arbitrary boolean expression, find a given input such that the output of the boolean expression is $1$. To my knowledge, this ...
40 views

37 views

### optimal search algorithm for finding parameters and thresholds

I have the following problem: There are $n$ variables $x_i$, $i=1...n$, each can take integer values from 1 to $m$. For every set of values I can run a test which has a binary outcome ('Pass' or 'Fail'...
1 vote
23 views

### Condition for detection of collision in an algorithmic problem

While solving This algorithm problem I was unable to come up with condition for the collision to occur ( other than the naive O(n^2) algorithm ) on reading the explanation they say Let’s deepen the ...
88 views

### Does padding with dummy bits allow an NP-problem to be solved in fast exponential time?

Take this example mentioned here: NP-hard problems with very fast exponential-time algorithms We can create such problem by padding assuming ETH‌. Take an NP-complete problem $L$ such that $L$ is ...
1 vote
543 views

### Difference Between k-center and k-mean/median

I know that k-mean/median is to find a set $F$ that minimize $$\sum_{i\in C}\min_{j \in F} d(i,j)$$ Where $C$ is set of clients and $F$ set of facilities. (For k-mean you just square the distance). ... 177 views

### Create a data structure with D-SUCCESSOR running in $O(1)$

Given an integer $d$, I need to devise a data structure $S$ with the following actions: BUILD(S): build the data structure $S$ from $n$ elements in $\Theta(n\lg{n})$ INSERT(S, k): insert a new ...
96 views

### How to efficiently search a list of data structures with filtering support

I'm working on a project where I need to create search functionality that can efficiently search a list of data structures like: ...
202 views

### How to find long trails in a multidigraph

I have a directed multigraph (a multigraph is a graph that can have more than one edge between any two nodes). In Wikipedia's terminology, this is a directed multigraph (edges without own identity). I ...
1 vote
34 views

### $W$-hierarchy and parameterized search problems

I have two related questions: What are the ways to prove that a certain problem is in $W[t]$ in the W-hierarchy for parametrized complexity, except using the straight definition of boolean circuits? ...
1 vote
298 views

### How to do binary search on a path in a binary heap

I am trying to solve this question: Let's say you have a binary heap and an index $i$, design an algorithm that finds if a number $x$ appears in the path between the root of the heap and $heap[i]$ in ...
1 vote
34 views

### Cyclic finite scheduling algorithm

I have a scheduling problem with the following specifications: A single machine is used. $n$ jobs $\mathbb{J} = \{J_1,...,J_n\}$ are available from the start $t = 0$. Each job can be executed several ...
98 views

### Why do we use DAG rather than trees to represent search space of a search problem?

I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on ...
238 views

### Are there search problems that cannot be written as decision problems?

I'm not sure whether the distinction between decision and search problems has a deeper significance or if it is just concerns the immediate answer to the problem. Of course, if you have a finite ...
618 views

### AI Search - State in the toy vacuum problem

I have been reading about AI search, specifically the toy vacuum cleaner problem and I would like to code an example of this but I am finding the description of the state hard to get my head around. ...
1 vote
176 views

### Number of sentences and sentential forms generated by a grammar

In this question, I'm considering only "finite grammars". A finite grammar can only produce a finite number of distinct sentences. The following grammar is finite in my definition: ...
613 views

405 views

### Does White never lose in Chess if Chess is solved?

If the machine has enough memory and speed as to compute all states of the Chess game in a reasonable time, can a player with the white pieces - operated by a machine - lose a game?
18k views

### Minimum number of tree cuts so that each pair of trees alternates between strictly decreasing and strictly increasing

A gardener considers aesthetically appealing gardens in which the tops of sequential physical trees (eg palm trees) are always sequentially going up and down, that is: ...
38 views

### Beam search in the context of Genetic Algorithm

As per Machine Learning, Tom M. Mitchell, Indian Edition, pp. 249-262, it is mentioned that "genetic algorithms employ a randomized beam search method to seek a maximally fit hypothesis". I have ...
2k views

### Fastest algorithm to find whether a list contains a word?

Given an unordered list of words, what's quickest way to test whether a certain word is in that list? I can't think of another way to do this other than just going through each element in the list ...
186 views

### Breadth-first traversal: difference between generation and expansion

The question here is to find a path from A(rad) to B(ucharest). I'll be using the initials of the cities in the picture instead of their full names. Some ground-rules: we're traversing in ...
1 vote
Given two numbers, $n$ and $m$, are there some mathematical methods of deducing $m$ from $n$ using limited number of elemantary operations? Example: 335 can be deduced from 2000 using division by 2, ...