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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, $\...
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'...
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 ...
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 ...
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). ...
user avatar
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 ...
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 ...
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? ...
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: ...
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, ...
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 ...
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 ...
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 ...
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: ...
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 ...
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, ...
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 ...