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.
152 questions
3
votes
1
answer
109
views
Finding a word that minimizes the sum of squared Hamming distances in a data set of words
Suppose we have a set of words of common length randomly sampled from a dictionary of words; assume you have access to that dictionary. Let $d(x,y)$ be the Hamming distance between words $x$ and $y$. ...
- 143
2
votes
2
answers
63
views
In class P, does decidability implies searchability?
I'm studying a course on Intro to Computability, and I couldn't find an answer.
Often, we refer to problems in $\text{P}$ as problems that we can "efficiently search a solution for" (where ...
- 21
3
votes
1
answer
346
views
Minimum number of oracle call to solve Simon problem by a (NDTM) non-deterministic Turing machine?
Simon's problem is a computational problem used to demonstrate an oracle separation between BQP and BPP classes.
It is known that the minimum number of oracle calls to be made by the BQP machine is $\...
- 163
0
votes
1
answer
24
views
Concise definitions for different types of computational problems
It is very common to define a decision problem $L$ in the following way. Let $f \colon \Sigma^{*} \to \{0,1\}$. Then $L = \{x \in \Sigma^* \mid f(x) = 1\}$. Effectively, $L$ contains all instances $x \...
0
votes
6
answers
117
views
Efficient data structure for multidimensional lookup
I'm doing a search problem over 18-tuples of non-negative integers. Some tuples are GOOD and some tuples are BAD, and I'm trying to list all of the GOOD tuples exactly once.
It turns out that if a ...
- 778
0
votes
0
answers
26
views
What algorithm should be used to find the closest set of dates?
I have tried to outline my problem as structured as possible, here is a rough overview, I am trying to find the best matching stay for a hotel booking system. If someone inputs check in and checkout ...
- 101
2
votes
1
answer
88
views
Maximum of a tritonic array
I have found out how to find the maximum of a "bitonic" array. The problem is as follows.
An array is bitonic if it is comprised of an increasing or decreasing sequence of integers followed ...
- 121
-1
votes
1
answer
62
views
How to get the TSP using DP algorithm can use 40 vertices?
I`m currently doing my homework that solving TSP using DP algorithm or branch and bound algorithm or backtracking algorithm only to solve up to 40 vertices and I can solve up to 30 vertices when I try ...
- 1
0
votes
0
answers
74
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 ...
0
votes
2
answers
201
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 ...
- 263
2
votes
1
answer
75
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 ...
- 23
2
votes
0
answers
46
views
Quantum search with input as a classical circuit
Grover's algorithm assumes $U_f$ computing a function $f$ as an oracle input. But in practice, an oracle isn't given. Instead a circuit computing $f$ is given. So let's assume a reversible circuit, $C ...
- 263
1
vote
1
answer
138
views
Difference between function and search problems?
I am a bit confused on what the difference between a "function problem" and a "search problem" is.
The specific problem I have been studying is known as End-Of-The-Line:
Given two ...
- 111
1
vote
1
answer
172
views
Finding Optimal Configuration of Formula without trying every Permutation
I have a math problem I need to solve so I can complete an optimisation in a computer program. My initial approach was just to brute force all the possible permutations but it got out of hand quite ...
- 129
1
vote
0
answers
96
views
Is there a comprehensive list of searching algorithms for sorted (and possibly unsorted) arrays available anywhere?
Classic searching algorithms such as binary searching and dictionary searching search sorted arrays based on a given element and make estimations on their own. What I'm looking for is a list of more ...
- 11
1
vote
0
answers
66
views
Function problem vs decision problem
I am a mathematician novice with the theory of computer science. During the course I took, we dealt with decisional problems (introducing D, SD, coSD classes language side, and P, NP, coNP, EXP, DP, ...
- 111
2
votes
1
answer
71
views
Strategy for searching for elementary cellular automata (cyclic boundary conditions) that repeat
I am looking for elementary cellular automata rules and initial conditions that give rise to interesting cycles (Cyclic boundary conditions, such that the leftmost entry is the neighbour of the ...
- 23
1
vote
1
answer
32
views
Edit distance into a DCFL
I would like to generate helpful parser errors, telling the user how to fix their program.
Specifically I have a deterministic context-free language $L$, given in the form of an $LR(1)$ grammar. I ...
- 729
1
vote
1
answer
215
views
does local search's State-Flipping Algorithm always terminate?
I am looking at the state flipping algorithm, an algorithm that tries to find a stable configuration in a Hopfield network.
The algorithm simply flips the state of unsatisfied nodes as long as the the ...
- 320
0
votes
1
answer
369
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 ...
- 291
1
vote
1
answer
259
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, $\...
- 111
3
votes
1
answer
60
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'...
- 31
1
vote
1
answer
25
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 ...
- 219
3
votes
1
answer
103
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 ...
- 31
1
vote
2
answers
1k
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).
...
user138945
0
votes
0
answers
190
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 ...
- 261
0
votes
0
answers
120
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:
...
- 101
2
votes
1
answer
260
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 ...
- 201
1
vote
0
answers
40
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? ...
- 49
1
vote
1
answer
365
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 ...
- 49
1
vote
0
answers
35
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 ...
- 167
3
votes
1
answer
122
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 ...
- 167
0
votes
1
answer
444
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 ...
- 123
0
votes
1
answer
3k
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.
...
- 81
1
vote
1
answer
233
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:
...
- 155
0
votes
1
answer
731
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 \...
- 103
1
vote
0
answers
1k
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, ...
- 143
2
votes
1
answer
499
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 ...
- 21
11
votes
1
answer
6k
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 ...
- 211
2
votes
1
answer
37
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 ...
- 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 ...
- 101
3
votes
0
answers
590
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 ...
- 2,360
1
vote
1
answer
42
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 ...
- 4,122
1
vote
1
answer
75
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 ...
- 13
0
votes
0
answers
76
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 ...
2
votes
0
answers
38
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 ...
- 163
2
votes
1
answer
222
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 ...
- 23
-1
votes
1
answer
106
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_{...
3
votes
3
answers
438
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?
- 27
9
votes
5
answers
19k
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:
...
- 257