Fact-checked by Grok 2 weeks ago

Search problem

In , particularly and algorithms, a search problem is a computational problem that requires finding a sequence of actions to reach a goal state from an initial state within a defined state space. It formalizes tasks such as pathfinding, planning, and puzzle solving by specifying key components: an initial state, a set of possible actions applicable to states, a transition model that determines the resulting state after an action, a goal test to identify goal states, and optionally a path cost function to evaluate solution quality. Search problems serve as the foundation for various search algorithms, which explore the state space systematically or heuristically to find optimal or feasible . They are central to applications in , game AI, and optimization, where the structure enables analysis of efficiency and completeness.

Definition and Formalism

Core Definition

In , a search problem is a type of computational problem where, given an input instance x \in \{0,1\}^*, the task is to find a corresponding y \in \{0,1\}^* (typically of length polynomial in |x|) that satisfies a specified , or determine that no such solution exists. This contrasts with decision problems, which only require determining existence via a yes/no answer, by demanding the explicit output of the solution itself. Search problems are fundamental to understanding the practical , particularly in contexts where is easy but is hard. The formulation emphasizes efficient verifiability: for problems in the class FNP, there exists a polynomial-time that, given x and a candidate y, checks whether (x, y) satisfies the . This structure underpins many NP-hard challenges, where solving the search version efficiently would imply P = . The concept developed in the 1970s alongside the study of , with early examples drawn from . Search problems can be partial (solutions may not exist for all inputs) or total (solutions always exist), influencing subclasses like TFNP for total functions in FNP. Unlike optimization problems that seek the best among many, basic search problems focus on finding any valid , though extensions often incorporate quality measures.

Formal Components

A search problem is formally defined by a R \subseteq \{0,1\}^* \times \{0,1\}^* that is efficiently computable (decidable in polynomial time), along with a p bounding the solution length. For input x, a is any y with |y| \leq p(|x|) such that (x, y) \in R; if no such y exists, the problem may require outputting an indicator of non-existence. The input x represents the problem instance, encoded as a binary string, while the solution y is the output witness, also binary, encoding the required information (e.g., a satisfying assignment). The relation R encodes the validity condition, often via a verifier function V(x, y) that runs in polynomial time and accepts if (x, y) \in R. For FNP problems, this verifier is deterministic and polynomial-time. The bound p ensures solutions remain feasible in size, preventing trivial inflation. In cases where solutions always exist ( search problems), the output is guaranteed; otherwise, algorithms must handle non-solution cases, often via the decision version in . Reductions between search and decision problems, such as self-reducibility, allow leveraging oracles for solution construction. For example, in the search version of SAT, x is a , y is a variable , and R checks under that . This framework avoids assumptions of or full inherent in other models, focusing instead on worst-case computational resources for finding and verification.

Representation and Modeling

Search problems in are formally represented by a R \subseteq \{0,1\}^* \times \{0,1\}^* that is computable in polynomial time by a deterministic . For an input instance x \in \{0,1\}^n, a y satisfies (x, y) \in R and has length |y| \leq p(n) for some p. The R encodes the problem's structure, such as verifying a satisfying assignment for a Boolean formula in SAT or a valid coloring for a graph in the graph coloring problem.

State Space

The state space for a search problem refers to the domain of possible instances x and the corresponding solution space for each x, which is the set of strings y \in \{0,1\}^{p(n)} such that (x, y) \in R. This solution space has exponential size $2^{p(n)}, reflecting the inherent computational challenge of exhaustive search. In practice, for concrete problems, the state space is modeled more compactly; for example, in SAT, states can represent partial assignments to variables, with the full space being $2^m for m variables, but only satisfying ones are valid solutions. The effective exploration of this space relies on the problem's structure, such as sparsity of solutions or self-reducibility, to avoid enumerating the entire exponential domain. A key aspect is the solution density or the expected number of valid y per x, analogous to a in search trees derived from self-reducibility. For NP-hard search problems, the state space's size underscores why polynomial-time solutions are unlikely unless P = NP. Challenges like the "search explosion" arise when attempting to enumerate or sample from large state spaces, similar to but distinct from AI contexts, emphasizing theoretical limits over practical enumeration. For instance, in the search version of 3-SAT, the state space of assignments grows as $2^n for n variables, with verification ensuring only valid ones are accepted.

Actions and Transition Model

Modeling the solution process for search problems often uses self-reducibility, where the search version reduces to polynomially many queries to the decision version. Here, the "state space" is partial solutions, and "actions" correspond to extending the partial solution by setting the next bit or . For a s (a partial ), the actions are assigning 0 or 1 to the next unset , leading to successor states s' via a deterministic : T(s, a) = s', where a \in \{0,1\} appends the value to s. The process continues until a full y is obtained or inconsistency is detected via decision calls. In self-reducible problems like SAT, the transition model is total for applicable actions but may prune branches if a partial renders the unsatisfiable, as checked by the . The generates at most two children per ( 2), forming a of depth equal to the number of variables. This model is reversible, as unsetting a variable returns to the parent , enabling techniques like recursive querying. For , actions might assign colors to vertices sequentially, with transitions enforcing adjacency constraints via verification. Such modeling highlights how decision oracles facilitate search without explicit enumeration, central to classes like FNP.

Types and Variations

Deterministic vs. Nondeterministic

In , search problems are classified as deterministic or nondeterministic based on the computational resources required to find a y for an input x such that (x, y) \in R, where R is the defining relation. Deterministic search problems belong to the FP (function P), consisting of those solvable by a deterministic in polynomial time. These problems allow efficient computation of solutions without nondeterministic choices, assuming the relation R permits direct polynomial-time resolution. A classic example is the uniform cost search analogue in , such as computing the shortest path in an unweighted using , which runs in polynomial time O(|V| + |E|) for sparse graphs. Such problems are in P for their decision versions and extend naturally to search via deterministic algorithms. Nondeterministic search problems, in contrast, fall into the class FNP, the function analogue of NP, where a solution y (of polynomial length) can be verified in polynomial time given x, but finding y may require nondeterministic computation if the problem is hard. Membership in FNP means there exists a polynomial-time verifier for R, but solving the search version might not be feasible deterministically unless P = NP. The search version of the problem (SAT), requiring a satisfying for a formula if one exists, exemplifies an FNP-complete problem; its decision version is NP-complete, and self-reducibility allows solving the search problem via polynomially many oracle calls to the decision problem. This distinction underscores that while is efficient, generation often relies on nondeterminism or in the worst case, highlighting the core challenges in . The boundary between and FNP captures the essence of efficient solvability: problems in yield practical algorithms for exact solutions, whereas FNP problems drive research into approximations and heuristics when exact solutions are intractable. Reductions between search and decision problems facilitate studying these classes, with implications for whether NP search problems can be derandomized or approximated.

Total vs. Partial Search Problems

Search problems in FNP can be further varied as partial or total based on whether solutions are guaranteed to exist for every instance. Partial search problems, the general case in FNP, may have instances with no solution y such that (x, y) \in R; the task is to find y if it exists or report none. Factoring large integers—finding non-trivial factors of a —is a partial FNP problem, as some numbers (primes) have no such factors, and its hardness underpins like . These problems correspond closely to NP decision versions, where "no" instances are possible. Total search problems, captured by the class TFNP, are a subclass of FNP where a solution is guaranteed for every input x, eliminating the need to check for existence and focusing purely on computation. TFNP includes problems with combinatorial guarantees, such as parity arguments ensuring solutions in certain structures. A prominent subclass is PPAD (polynomial parity arguments), which addresses fixed-point problems in directed graphs with indegree/outdegree at most 1, where a source-sink pair is known, and another must exist by . Finding a Nash equilibrium in a two-player game is PPAD-complete, as shown by reductions from ; solutions can be verified in polynomial time, but no polynomial-time is known as of 2025. Other TFNP subclasses include PPA (polynomial parity arguments for undirected graphs) and PLS (polynomial local search) for optimization landscapes with local minima. This total/partial distinction emphasizes structural promises: partial problems allow "no" answers and relate to , while total problems like those in TFNP avoid checks but remain hard due to the need to locate solutions efficiently. into TFNP subclasses explores whether they contain problems or require exponential time, informing fields like and .

Solution Methods

Search Algorithms Overview

In , algorithms for search problems aim to compute a y such that (x, y) \in R for a given input x, where R is the defining . For general FNP search problems, exact solutions are not known to be computable in polynomial time unless P = . A basic approach is brute-force : generate all possible y of length polynomial in |x| and verify each against R, which requires exponential time in the worst case due to the size of the search . Many natural NP search problems are self-reducible, allowing the search version to be solved via polynomially many queries to a decision for the corresponding NP problem. In self-reducibility, the solution is constructed incrementally: for problems like the search-SAT (finding a satisfying ), fix bits of the assignment one by one by querying the decision on whether a solution exists for the current prefix with the next bit set to 0; if affirmative, set it to 0, else to 1. This requires O(|x|) oracle calls and polynomial time otherwise, reducing search to decision. Similar techniques apply to and other NP-complete search problems. If the decision problem is in P, the search is solvable in . For total search problems in TFNP, where a solution is guaranteed to exist, subclasses have specialized methods. In PPAD, encompassing fixed-point problems like computing equilibria in games, algorithms such as the Lemke-Howson method can find solutions for two-player games, though general PPAD-complete problems resist efficient solving. When exact solutions are intractable, algorithms provide near-solutions, such as approximate equilibria within a small , computable in time for certain parameters. Heuristics and practical solvers, like DPLL-based SAT solvers (e.g., MiniSat), are used for real-world instances despite worst-case hardness.

Evaluation Metrics

Algorithms for search problems are evaluated based on measures, solution guarantees, and practical performance. Time complexity classifies solvability, with for polynomial-time search functions and for brute-force methods. For oracle reductions, query complexity counts decision calls, polynomial in self-reducible cases. evaluates memory, crucial for bounded-resource models like LOGSPACE analogs for search. For approximation and optimization-oriented search problems, the quantifies how close the output is to optimal (e.g., within factor \rho), defining classes like PTAS (polynomial-time approximation schemes). Randomized algorithms are assessed by success probability (e.g., vs. ) and expected runtime, relevant for classes like BPP^NP. Hardness results, such as inapproximability from theorems, set limits on achievable ratios without P= implications. Solution quality metrics, like the value of the objective function relative to the optimum C^*, inform utility in applications. These evaluations drive research into efficient solvers and theoretical barriers.

Applications and Examples

Pathfinding and Navigation

Search problems in computational complexity often arise in graph-theoretic settings, where the input is a and the goal is to find a structure satisfying a relation, such as a path or tour. A prominent example is the search version of the traveling salesman problem (TSP), where given a complete weighted G = (V, E) with edge weights representing distances, the task is to find a Hamiltonian cycle (tour visiting each exactly once and returning to the start) of minimum total weight, if one exists with weight below a threshold. This is an FNP search problem, as solutions (tours) can be verified in polynomial time, but finding the optimal is NP-hard. TSP underpins applications in and route optimization, where exact solutions are intractable for large instances (e.g., thousands of cities), leading to algorithms or heuristics in practice. Another key example is the : given a G, find a visiting each exactly once, or determine none exists. This search problem is NP-complete in its decision version and belongs to FNP, with applications in scheduling (e.g., ordering tasks with precedence constraints) and network design (e.g., sequencing routes in communication networks). Unlike polynomial-time solvable shortest-path problems (e.g., via in P), Hamiltonian path highlights the hardness of exact "navigation" in complex graphs, motivating reductions from other NP problems. In navigation-like scenarios, such as , the search problem generalizes to the (VRP), where multiple vehicles must serve customers from a depot while minimizing total distance. The relation R defines valid routes satisfying capacity and time constraints; finding such routes is FNP-hard, with real-world use in and , where combinatorial explosion limits exact solutions to small instances (e.g., <50 customers).

Puzzle and Game Solving

Combinatorial puzzles often formalize as search problems in FNP, requiring a (solution y) satisfying constraints for input puzzle x. The satisfiability (SAT) problem exemplifies this: given a Boolean formula φ in , find an to variables making φ true, if possible. Here, R(φ, a) holds if a is a satisfying assignment, verifiable in polynomial time. SAT search is complete for FNP under parsimonious reductions and models puzzle-solving like logic grid puzzles or Sudoku (reducible to SAT), with applications in (e.g., checking designs for bugs) and AI . As of 2025, SAT solvers handle industrial instances with millions of clauses using heuristics, but worst-case exponential time underscores P vs. NP implications. Graph coloring extends this to puzzles like : given graph G and integer k, find a k-coloring c: V → {1,...,k} such that no adjacent vertices share colors. The 3-coloring search problem is FNP-complete, used in scheduling (assigning resources without conflicts) and in compilers. Solutions exist for bipartite graphs (k=2, in P), but general k=3 is hard, illustrating how puzzle solvability ties to complexity classes. In , search problems capture strategic reasoning. The problem, in PPAD ⊆ TFNP, requires finding a mixed-strategy profile (probabilities over actions) for a finite game where no player benefits from unilateral deviation. For input game matrix x, output y such that R(x,y) (equilibrium condition) holds; solutions always exist by Nash's theorem, but computing approximate equilibria is PPAD-complete. Applications include auction design, , and , where finding equilibria aids in predicting outcomes in economic models or network formation. As of 2025, no polynomial-time algorithm exists, with quantum approaches explored but unproven. Another TFNP example is : given composite N, find nontrivial factors p,q such that N = p·q. Verifiable in polynomial time, it's total (always solvable) and believed hard, forming the basis of cryptography for secure communication (e.g., ). Quantum algorithms like Shor's (1994) solve it in polynomial time on quantum computers, but as of 2025, no large-scale quantum threat exists, preserving classical hardness assumptions.

Complexity Analysis

Computational Complexity

Search problems in theory are analyzed through function complexity classes that extend decision classes like . The class FNP includes search problems where, given an input x and proposed solution y, there exists a polynomial-time verifier confirming (x, y) \in R. This mirrors but requires constructing y rather than deciding existence. If the corresponding (existence of y) is in , the search problem is in FP, solvable in polynomial time by a deterministic . A key subclass is TFNP, comprising total search problems in FNP where a solution is guaranteed for every input, based on combinatorial principles ensuring existence (e.g., via fixed-point theorems). TFNP has natural subclasses capturing specific totality arguments: PPAD for polynomial-time problems related to directed graphs with unequal in/out-degrees (e.g., finding Brouwer fixed points or approximate Nash equilibria in games); PPA for parity arguments in undirected graphs; and others like and PLS for potential maximization. These classes are believed incomparable, with no known complete problems under standard assumptions, highlighting the nuanced hardness within TFNP. Hardness for search problems often follows from decision versions via . A search problem is NP-hard if every NP decision problem reduces to it in polynomial time, implying P = NP if solvable in polynomial time. For instance, the search-SAT problem (finding a satisfying assignment) is NP-hard by parsimonious reductions from decision-SAT. Many NP search problems are self-reducible, allowing solution via polynomially many queries to the decision : for SAT, fix variables one by one, checking satisfiability after each. This technique extends to problems like . Search problems can also be complete for higher classes, such as PSPACE, where the Quantified Boolean Formulas (QBF) search variant requires finding satisfying assignments to alternating quantifier formulas, hard even with polynomial space.

Practical Challenges

The intractability of NP-hard and TFNP-complete search problems poses challenges in applications requiring exact solutions, such as (e.g., as a search problem) and optimization (e.g., TSP tour finding). To address this, approximation algorithms seek solutions within a guaranteed factor of optimality; for example, Christofides' 1.5-approximation for metric TSP, though the general case resists constant-factor approximation unless P = . Parameterized complexity fixes parameters beyond input size (e.g., in graph problems), yielding fixed-parameter tractable (FPT) algorithms like O(2^w n) for on graphs of treewidth w, where n is input size. These mitigate hardness for restricted instances common in practice, such as logistics routing or . Proving hardness for search problems often requires novel reductions, as totality in TFNP complicates standard NP techniques; for PPAD, reductions from End-of-the-Line preserve approximate solutions. Recent results (as of 2023) show fine-grained hardness, linking PPAD to algebraic problems like finding short vector lattices, impacting . Challenges include distinguishing average-case from worst-case hardness, with random self-reducibility enabling derandomization for some problems. In real-world deployment, hybrid approaches combine exact solvers for small instances with heuristics, but verifying approximation ratios remains computationally intensive.

References

  1. [1]
    [PDF] 1 Computational Problems - Stanford CS Theory
    Apr 29, 2010 · In this course we will deal with four types of computational problems: decision prob- lems, search problems, optimization problems, and counting ...
  2. [2]
    Computational Complexity Theory (Stanford Encyclopedia of Philosophy)
    Summary of each segment:
  3. [3]
    [PDF] 3 SOLVING PROBLEMS BY SEARCHING
    The 8-puzzle was one of the earliest heuristic search problems. As mentioned ... lishment of search algorithms as the primary weapons in the armory of 1960s AI ...
  4. [4]
    [PDF] Report on a general problem-solving program.
    This paper reports on a computer program, called GPS-I for General Problem Solving Program I. Construction and investigation of this program is part of a ...
  5. [5]
    [PDF] STEPS TOWARD ARTIFICIAL INTELLIGENCE Marvin Minsky Dept ...
    This paper emphasizes the class of activities in which a general-purpose computer, complete with a library of basic programs, is further programmed to perform ...
  6. [6]
    [PDF] Artificial Intelligence: A Modern Approach - Engineering People Site
    We explain the role of learning as extending the reach of the designer into unknown environments, and we show how that role constrains agent design, favoring ...
  7. [7]
    The Fifteen Puzzle—A New Approach through Hybridizing Three ...
    Automatically solving the Fifteen Puzzle is very challenging because the state space for the Fifteen Puzzle contains about 16! /2≈1013 states [2]. The Fifteen ...
  8. [8]
    [PDF] 3 solving problems by - Artificial Intelligence: A Modern Approach
    Define the necessary functions to implement the search problem, including a successor function that takes a vertex as input and returns the set of vertices ...
  9. [9]
    [PDF] On the Reversibility of Actions in Planning - KR Proceedings
    Checking whether action effects can be undone is an impor- tant question for determining, for instance, whether a plan- ning task has dead-ends.
  10. [10]
    [PDF] STRIPS: A New Approach to the Application of .Theorem Proving to ...
    ABSTRACT. We describe a new problem solver called STRIPS that attempts to find a sequence of operators in a spcce of world models to transform a given ...
  11. [11]
    [PDF] Fundamentals of Artificial Intelligence Chapter 04: Beyond Classical ...
    Oct 7, 2022 · Online Search: Deadends. Inevitability of Deadends. Online search may face deadends (e.g., with irreversible actions). No algorithm can avoid ...<|control11|><|separator|>
  12. [12]
    [PDF] A Formal Basis for the Heuristic Determination of Minimum Cost Paths
    1967. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. PETER E. HART, MEMBER, IEEE, NILS J. NILSSON, MEMBER, IEEE, AND BERTRAM RAPHAEL.
  13. [13]
    [PDF] dijkstra-routing-1959.pdf
    Problem 1. Construct the tree of minimum total length between the # nodes. (A tree is a graph with one and only one path between every two nodes.) In the ...
  14. [14]
    [PDF] Complete Solution of the Eight-Puzzle and the Benefit of Node ...
    ... Manhattan distance were analyzed and an improvement in Manhattan distance heuristic is implemented. ... The pathology of heuristic search in the 8-puzzle · Rok ...
  15. [15]
    Graph Search vs. Tree-Like Search | Baeldung on Computer Science
    Mar 18, 2024 · Graph search avoids repeating states, while tree-like search may repeat them. Graph search is more memory-demanding, and tree-like search can ...
  16. [16]
    [PDF] CS 188 Introduction to Artificial Intelligence Spring 2024 Note 2
    Aug 26, 2023 · Optimality - BFS is generally not optimal because it simply does not take costs into consideration ... Completeness - Uniform cost search is ...
  17. [17]
    Depth-first iterative-deepening: An optimal admissible tree search
    A depth-first iterative-deepening algorithm is shown to be asymptotically optimal along all three dimensions for exponential tree searches.Missing: original | Show results with:original
  18. [18]
    Best First Search (Informed Search) - GeeksforGeeks
    Mar 20, 2025 · Best First Search is a heuristic algorithm that selects the most promising node for expansion using an evaluation function, using a priority ...
  19. [19]
    1.5 Local Search | Introduction to Artificial Intelligence
    The hill-climbing search algorithm (or steepest-ascent) moves from the current state towards the neighboring state that increases the objective value the most.
  20. [20]
    [PDF] A Formal Basis for the Heuristic Determination of Minimum Cost Paths
    Our algorithm prescribes how to use special knowledge e.g., the knowledge that the shortest road route between any pair of cities cannot be less than the ...
  21. [21]
    View of Anytime Heuristic Search
    We refer to this strategy asanytime heuristic search. Anytime algorithms are useful forproblem-solving under varying or uncertain time constraints because ...
  22. [22]
    Learning Heuristics For Grid-Based Pathfinding via Transformers
    Dec 22, 2022 · Instance-independent heuristics for grid graphs, e.g. Manhattan distance, do not take the obstacles into account and, thus, the search led ...Missing: actions | Show results with:actions
  23. [23]
    https://ieeexplore.ieee.org/document/9231637
  24. [24]
    [PDF] Learning Heuristics for Grid-Based Pathfinding via Transformers
    Instance-independent heuristics for grid graphs, e.g. Manhattan distance, do not take the ob- stacles into account, and thus the search led by such heuristics.<|separator|>
  25. [25]
    Shortest Path Algorithms: An Evaluation Using Real Road Networks
    In this paper, we provide an objective evaluation of 15 shortest path algorithms using a variety of real road networks.
  26. [26]
    https://ieeexplore.ieee.org/document/10871658
  27. [27]
    Route Planning Algorithms for Fleets of Connected Vehicles - MDPI
    In this paper, we present a study of this kind. Specifically, we first describe the main features of a real-world information system employing semi-autonomous ...2. Architecture: The Emerge... · 3. Computational Problems... · 4. Implementation And...
  28. [28]
    (PDF) Shortest Path with Dynamic Weight Implementation using ...
    Aug 6, 2025 · Shortest path algorithms have been long applied to solve daily problems by selecting the most feasible route with minimum cost or time.
  29. [29]
    [PDF] Complete Solution of the Eight-Puzzle and the Benefit of Node ...
    We generated all 9!/2 solvable tile configurations and computed all optimal solutions for all problem instances. We used Korfs IDA* algorithm (for a description ...
  30. [30]
    15 Puzzle -- from Wolfram MathWorld
    ... puzzle cannot be solved. While odd permutations of the puzzle are impossible to solve (Johnson 1879), all even permutations are solvable (Story 1879).
  31. [31]
    [PDF] A Modern Treatment of the 15 Puzzle
    American Journal of Mathematics in 1879 by W. W. Johnson [7] and W. E. Story. [13]. Johnson's article is an explanation of why odd permutations of the puzzle ...
  32. [32]
    [PDF] Lecture 9: Games I
    In the game tree, we will now use an upward-pointing triangle to denote states where the player is maxi- mizing over actions (we call them max nodes). • At max ...
  33. [33]
    An analysis of alpha-beta pruning - ScienceDirect.com
    The alpha-beta technique is used for searching game trees. This paper analyzes its behavior, correctness, and historical context.Missing: original | Show results with:original
  34. [34]
    Tower of Hanoi -- from Wolfram MathWorld
    The tower of Hanoi puzzle asks for the minimum number of moves required to move the stack from one rod to another, where moves are allowed only if they place ...
  35. [35]
    [PDF] Contents 1 The Tower of Hanoi
    Then, we'll find a closed-form expression for the minimum number of moves required, and prove that the closed-form and recurrent expressions are equivalent. 1.1 ...
  36. [36]
    [PDF] John von Neumann's Conception of the Minimax Theorem
    The first purpose of this paper is to tell the history of John von Neumann's devel- opment of the minimax theorem for two-person zero-sum games from his ...
  37. [37]
    Mastering the game of Go with deep neural networks and tree search
    Jan 27, 2016 · Using this search algorithm, our program AlphaGo achieved a 99.8% winning rate against other Go programs, and defeated the human European Go ...
  38. [38]
    [PDF] Lecture 2: Uninformed search methods Search in AI
    – Exponential time complexity: O(bd) (why?) This is the same for all uninformed search methods. – Exponential memory requirements! O(bd) (why?) This is not ...
  39. [39]
    Artificial Intelligence: A Modern Approach, 4th US ed.
    Artificial Intelligence: A Modern Approach, 4th US ed. by Stuart Russell and Peter Norvig. The authoritative, most-used AI textbook, adopted by over 1500 ...AI Instructor's Resource Page · Full Table of Contents for AI · Global Edition · 1500
  40. [40]
    Depth First Search (DFS) for Artificial Intelligence - GeeksforGeeks
    Jul 23, 2025 · Implicit Space Complexity. For an implicit search in a graph, DFS's space complexity can be represented as follows: O(bd). where: b ...
  41. [41]
    [PDF] Uninformed Search - cs.wisc.edu
    ○ Time and space complexity: O(bd) (i.e., exponential). – d is the depth of the solution. – b is the branching factor at each non-leaf node. ○ Very slow to ...
  42. [42]
    [PDF] PSPACE-Completeness of Sliding-Block Puzzles and Other ...
    In this paper, we prove that the Warehouseman's Problem and sliding-block puzzles are PSPACE-hard even for 1 × 2 rectangles (dominoes) packed in a rectangle. ...
  43. [43]
    Proof that traveling salesman problem is NP Hard - GeeksforGeeks
    Jul 15, 2025 · Therefore, any instance of the Travelling salesman problem can be reduced to an instance of the hamiltonian cycle problem. Thus, the TSP is NP- ...<|control11|><|separator|>
  44. [44]
    [PDF] Neural Network Heuristics for Classical Planning: A Study of ...
    The remainder of this paper evaluates hyperparameters in our framework, and the overall competitive performance of the result- ing learned heuristic functions.
  45. [45]
    [PDF] Solving Time-Dependent Planning Problems - IJCAI
    [Boddy and Dean, 1989], an extended version of this paper. The algorithm works by assuming initially that all the travel time for the locations will be used ...