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
48 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 ...
user716881's user avatar
-1 votes
1 answer
34 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 ...
Tuan's user avatar
  • 1
0 votes
0 answers
51 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 ...
sharkeater123's user avatar
0 votes
0 answers
18 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?
Biswashree Dey's user avatar
0 votes
1 answer
94 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 ...
Loic Stoic's user avatar
2 votes
1 answer
57 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 ...
geckovsrhino's user avatar
0 votes
0 answers
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 ...
Loic Stoic's user avatar
2 votes
0 answers
40 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 ...
Loic Stoic's user avatar
1 vote
1 answer
103 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 ...
wavosa's user avatar
  • 111
1 vote
1 answer
160 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 ...
Anters Bear's user avatar
1 vote
0 answers
83 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 ...
requiemman's user avatar
1 vote
0 answers
53 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, ...
Ixion's user avatar
  • 111
2 votes
1 answer
61 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 ...
Douw Marx's user avatar
1 vote
1 answer
29 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 ...
Jonas Kölker's user avatar
1 vote
1 answer
146 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 ...
user206904's user avatar
0 votes
1 answer
287 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 ...
user918212's user avatar
1 vote
1 answer
116 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, $\...
Xavier Taylor's user avatar
3 votes
1 answer
46 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'...
user150391's user avatar
1 vote
1 answer
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 ...
Pawan Nirpal's user avatar
3 votes
1 answer
93 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 ...
Biology nerd's user avatar
1 vote
2 answers
685 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
182 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 ...
CforLinux 's user avatar
0 votes
0 answers
100 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: ...
user3238415's user avatar
2 votes
1 answer
226 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 ...
user2373145's user avatar
1 vote
0 answers
35 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? ...
Ofir Gordon's user avatar
1 vote
1 answer
324 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 ...
yuval's user avatar
  • 49
1 vote
0 answers
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 ...
EvaMGG's user avatar
  • 167
3 votes
1 answer
109 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 ...
EvaMGG's user avatar
  • 167
0 votes
1 answer
298 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 ...
Meep's user avatar
  • 123
0 votes
1 answer
1k 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. ...
pac234's user avatar
  • 81
1 vote
1 answer
190 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: ...
ihavenoidea's user avatar
0 votes
1 answer
648 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 \...
Fransebas's user avatar
  • 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, ...
dx_over_dt's user avatar
2 votes
1 answer
445 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 ...
Ali Mirzaee's user avatar
11 votes
1 answer
5k 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 ...
219CID's user avatar
  • 211
2 votes
1 answer
35 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 ...
Ernie's 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 ...
A-Android UCG's user avatar
3 votes
0 answers
502 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 ...
Martin Thoma's user avatar
  • 2,360
1 vote
1 answer
38 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 ...
user56834's user avatar
  • 3,692
1 vote
1 answer
72 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 ...
KyleCraig's user avatar
0 votes
0 answers
73 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 ...
Nicekiller231's user avatar
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 ...
Water's user avatar
  • 163
2 votes
1 answer
185 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 ...
pcon's user avatar
  • 23
-1 votes
1 answer
93 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_{...
mymemesarespiciest's user avatar
3 votes
3 answers
419 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?
108880's user avatar
  • 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: ...
Alan Evangelista's user avatar
2 votes
0 answers
41 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 ...
flamingo_stark's user avatar
0 votes
2 answers
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 ...
fallingriptide's user avatar
0 votes
0 answers
225 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 ...
investigate311's user avatar
1 vote
1 answer
320 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 ...
DIB98's user avatar
  • 13