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.
145
questions
2
votes
1
answer
27
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 ...
- 21
0
votes
0
answers
10
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 ...
- 71
2
votes
0
answers
37
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 ...
- 71
1
vote
1
answer
42
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
138
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
0
votes
0
answers
15
views
Constraint Satisfaction Problem on 8-puzzle
In the 8-puzzle problem, how can I put constraints on the movement of the blank?
If zijk represents in the (i, j)th cell, number k is present.
Domain, i, j E {1,2,3}, k E {1,2,...,8}
Constraint(s) are:...
- 26
1
vote
0
answers
33
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
50
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
27
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
0
votes
0
answers
189
views
Understanding heuristic function (Berkeley AI Project 1)
Cheers, I am playing around with Berkeley's AI Project 1 (Pacman) (link here) and I am trying to find a good heuristic function for the foodHeuristic function (Question 6).
While playing around with ...
1
vote
1
answer
24
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 ...
- 699
1
vote
1
answer
72
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 ...
- 310
0
votes
1
answer
134
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 ...
- 271
1
vote
1
answer
56
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
27
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
20
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
61
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
224
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
160
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
89
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:
...
2
votes
1
answer
152
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 ...
- 183
1
vote
0
answers
27
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
205
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
33
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 ...
- 165
3
votes
1
answer
83
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 ...
- 165
0
votes
1
answer
104
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
347
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
142
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:
...
- 145
0
votes
1
answer
509
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
617
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
243
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
4k
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
32
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
337
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,340
1
vote
1
answer
35
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 ...
- 3,472
1
vote
1
answer
69
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
70
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
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 ...
- 163
2
votes
1
answer
143
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
60
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
365
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
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:
...
- 257
2
votes
0
answers
34
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 ...
0
votes
2
answers
1k
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 ...
- 131
0
votes
0
answers
122
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
1
answer
290
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 ...
- 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, ...
- 31
1
vote
1
answer
241
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 ...
- 13
3
votes
1
answer
36
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 ...
- 261