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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
59 views

Can a Turing machine quickly move to any position of a large string?

Note this question was originally asked on Theoretical CS Stack Exchange, but it is not a research level question so it is being closed, and I am asking here instead. Suppose we simulated a Turing ...
user avatar
  • 119
1 vote
1 answer
19 views

Efficient search of a large set of documents to find documents that only contain a particular set of words

Say I have a set of documents $D = \{d_1, d_2, \dots, d_n\}$ in some natural language. Each document $d_i$ consists of a subset of words from a word pool $W = \{w_1, w_2, \dots, w_k\}$. For example, $\...
user avatar
3 votes
1 answer
25 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'...
user avatar
1 vote
1 answer
19 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 ...
user avatar
0 votes
0 answers
18 views

A star with a heuristic that is "almost admissible"

Let $h$ be a heuristic such that for all $s\in S$, barring $m$ states , $0\leq h(x) \leq h^*(x)$. Those $m$ states are not known in advance. Suggest a way to use $A^*$ (perhaps with some modifications)...
user avatar
  • 133
3 votes
1 answer
41 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 ...
user avatar
0 votes
0 answers
18 views

Cosine vs Manhattan to measure Text Similarity after doc2vec Embedding

I have a list of documents and made doc2vec embedding to them using BERT model so now they are stored as vectors in Elasticsearch database. I want to apply semantic search given a query from the user ...
user avatar
1 vote
2 answers
62 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). ...
user avatar
0 votes
0 answers
117 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 ...
user avatar
0 votes
0 answers
46 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: ...
user avatar
2 votes
1 answer
100 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 ...
user avatar
1 vote
0 answers
19 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? ...
user avatar
1 vote
1 answer
142 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 ...
user avatar
  • 49
1 vote
0 answers
31 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 ...
user avatar
  • 165
3 votes
1 answer
75 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 ...
user avatar
  • 165
0 votes
1 answer
45 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 ...
user avatar
  • 123
0 votes
1 answer
187 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. ...
user avatar
  • 83
1 vote
1 answer
95 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: ...
user avatar
0 votes
1 answer
365 views

3Sum Why this O(nlogn) solution doesn't work?

I have been doing LeetCode and tackled the problem of the 3Sum and first I tried to do a O(nlogn) solution and after seeing the proposed solution I see that the solution is $O(n^2)$ or $O(n^2 \times \...
user avatar
1 vote
0 answers
350 views

Graph traversal problem touching every node exactly once

Is there a name for the problem: Suppose you have a connected, undirected graph; find a path that touches every node exactly once. This is basically the complement of the Hamiltonian Path problem, ...
user avatar
2 votes
1 answer
149 views

Definition and example of search problem

I searched the pages a lot about the search problem but didn't understand much, so please make it clearer for me. WIKIPEDIA: In computational complexity theory and computability theory, a search ...
user avatar
10 votes
1 answer
2k views

Algorithm to create dense style crossword puzzles

I am working on creating a program to generate dense American style crossword puzzles of grid sizes between 15x15 - 30x30. The database of words I'm using ranges between 20,000 and 100,000 words of ...
user avatar
  • 101
2 votes
1 answer
31 views

Recover a matrix with minimum number of queries

Alice has a matrix $A \in \{0,1\}^{n \times m}$ such that the sum of each row is $1$. Bob tries to find the indices of the ones (he knows that the sum of each row is $1$). The type of questions Bob ...
user avatar
  • 53
0 votes
0 answers
27 views

Transits directions search

Data Description : A database consisting of many Transits. Each transit has its own Path (both forward and backward), and each path has a set of Stops. Each stop consists of the position and the ...
user avatar
2 votes
0 answers
284 views

Should a prefix tree (trie) node store only a single character or a string?

I've just implemented a Trie and I thought it would be a good idea to store strings in the Trie nodes in contrast to storing single characters. Storing strings is for sure more space-efficient and ...
user avatar
  • 2,300
1 vote
1 answer
33 views

Do we understand when metaheuristics are optimal? (gradient descent & simulated annealing in particular)

Gradient descent sometimes works better than simulated annealing and vice versa. Are there conditions under which we can prove that, given perhaps a restriction on the set of allowed algorithms, one ...
user avatar
  • 3,464
1 vote
1 answer
65 views

Finding lost bottle (algorithm problem)

The question is as follows: A scientist creates a new compound, called compound A, that will explode 10 days after being mixed with compound B. This compound A was stored in a label-less bottle on ...
user avatar
0 votes
0 answers
68 views

How to maximize $f$ while minimizing $g$ at the same time?

Lately, I have been dealing with a problem that I didn't know how to name it to solve it properly. The problem is as follow: let's assume that we have a set of elements $A$. And, we have two ...
user avatar
2 votes
0 answers
32 views

A data structure for efficiently finding nodes relative to other (ex: if a node is earlier in a list than another node)

Suppose we have N elements, which we'll treat as a simple object. Is there a data structure I can use that will allow me to see which node appears earlier based on ...
user avatar
  • 163
2 votes
1 answer
117 views

Finding maximal cardinal independent set given oracle

The problem is given an oracle $O(G, k)$ that would say if graph G contains IS of size k devise an algorithm for finding independent set of max cardinality that makes poly number of calls to the ...
user avatar
  • 23
-1 votes
1 answer
55 views

What does the search problem imply about the decision problem?

Let $\Pi_{dec}$ be an NP-complete decision problem and let $\Pi_{opt}$ be its corresponding optimization problem. Assume $\Pi_{opt}$ can be solved in polynomial time. What does this imply for $\Pi_{...
user avatar
3 votes
3 answers
319 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?
user avatar
  • 27
9 votes
5 answers
15k 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: ...
user avatar
2 votes
0 answers
30 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 ...
user avatar
0 votes
2 answers
652 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 ...
user avatar
0 votes
0 answers
57 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 ...
user avatar
1 vote
1 answer
254 views

I am looking for an algorithm that can find the best possible combination of inputs, in order to determine the optimum output

So as the title poorly implies, I'm looking for an algorithm that can accomplish the following task (as an example): Given the inputs A(1:100), B(1:100), C(1:100), that can take on any value between 1 ...
user avatar
  • 13
3 votes
2 answers
101 views

Proving that a set of operations can't generate one integer from a given one

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, ...
user avatar
0 votes
1 answer
185 views

Efficient search for solving a Jigsaw Puzzle?

I believe that solving a Jigsaw puzzle is in general NP-complete based on the two questions linked below. However, I'd like to implement a heuristic algorithm that works well in practice. Let's ...
user avatar
  • 3
3 votes
1 answer
32 views

Hardness of FNP vs Choice of Verifiers

A (T)FNP problem is induced by a NP language, say $L$. Usually in the notion of verifers, we define $L=\{x:\exists y,V(x,y)=1\}$, where $V$ is a poly-time verifier. The function version would be ...
user avatar
1 vote
1 answer
127 views

Repeated String Match: need help to understand the maximum number of repeats needed to be looked at

There's this question on LeetCode (link): Given two strings A and B, find the minimum number of times ...
user avatar
2 votes
1 answer
2k views

Find an element in sorted 2D-array (matrix)

Given an $N\times N$ array, where elements are decreasing in every row and every column. What is the fastest way to find the $(i,j)$ of a given element if it exists in the array, or return no if it ...
user avatar
  • 31
2 votes
2 answers
267 views

Interesting logic problems

I've just began a course on logic and learned the following : De Morgan's laws Normal forms How to represent a logical formula (using or, and, not operators) using binary trees How to get the ...
user avatar
  • 63
1 vote
1 answer
204 views

Search on Conformant Problem: solution for subset of a belief state

I am having trouble understanding the following statement. I have understood why in a sensorless/conformant problem, if there exists a solution (a sequence of actions) for a belief state $b$, then it ...
user avatar
0 votes
0 answers
179 views

How to accomodate decision trees with infinite options

I know that once I have a graph or decision tree representation of a problem, there are many different ways I can get a computer to solve the problem. They're called search algorithms, and go by names ...
user avatar
  • 115
1 vote
0 answers
32 views

fastest way to find matching pattern

I have several series of integers (vectors) that could be plotted at equal distances apart: ...
user avatar
  • 327
1 vote
2 answers
668 views

Efficient way to find matching date ranges?

We have a set of problems involving date ranges - a pair of dates representing a start date and an end date. In some places, we have say 1000 of these and need to find the ones that overlap a separate ...
user avatar
  • 121
0 votes
1 answer
172 views

String Search - how to find the "most" accurate string?

Assume I have the following list of companies: Apple Big Apple Google Then I have this sample string: Big Apple is a company that is trying to be the next Google. Given the list of companies and ...
user avatar
1 vote
1 answer
405 views

reducing a decision problem to a local search problem

Lemma 4 in How easy is local search by Johnson, Papadimitriou, and Yannakakis, states: If a PLS problem is NP-hard then NP = P So assuming L is a PLS problem (polynomial local search problem) that ...
user avatar
  • 125
3 votes
2 answers
2k views

Finding a local peak in an array in O(log N)?

So I watched a couple of videos regarding this and the divide and conquer made sense to me. But I am still not convinced as to how recursing on the side with the larger number guarantees us the ...
user avatar